705 НОМЕР - Решение задач (2/3)
Условие задачи
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу:
а) в конец числа (справа) дописывается 1, если число единиц в двоичной записи числа чётно, и 0, если число единиц нечётно.
б) к этой записи справа дописывается остаток от деления количества единиц на 2.
Полученная запись (на два разряда больше, чем запись N) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает 31 и может являться результатом работы алгоритма.
Алгоритм решения
1. Перебор чисел: Создать цикл for N in range(1, 10000): (диапазон обычно небольшой, можно увеличить при необходимости).
2. Перевод в систему счисления (СС): использовать функцию bin() для перевода в двоичную запись. Не забываем убрать префикс '0b' с помощью среза [2:].
3. Обработка: Считаем количество единиц в двоичной записи. Для этого используем метод s.count('1') — он возвращает количество вхождений символа '1' в строке.
Далее проверяем чётность количества единиц. Если оно чётное, то дописываем '1' справа, если нечётное — '0'. Соответственно проверка будет выглядеть следующим образом:
1 2 3 4
Затем выполняем шаг б): снова считаем количество единиц в уже обновлённой строке (после шага а добавился один разряд!) и дописываем остаток от деления на 2:
1 2
Важно: функция str() нужна, чтобы превратить число (0 или 1) в строку
4. Обратный перевод: Переводим итоговую строку обратно в десятичную систему: R = int(s, 2).
5. Условие и вывод: Проверяем условие if R > 31 и добавляем подходящие R в список. В конце выводим минимальное значение через min(results).
Почему нельзя использовать break? В отличие от задач на минимальное N, здесь мы ищем минимальное R. Меньшие N не обязательно дают меньшие R, поэтому нужно перебрать весь диапазон и собрать все возможные результаты, а затем выбрать наименьший.
Решение
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Ответ: 33
Решите задачи, чтобы усвоить материал
Решить в Личном КабинетеНа вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N не делится на 3, то к этой записи справа дописываются две её последние цифры, а слева – цифра 2;
б) если число N делится на 3, то сумма цифр троичной записи умножается на 5, переводится в троичную систему счисления и дописывается в конец числа.
Полученная таким образом запись является троичной записью искомого числа R.
Укажите число R, ближайшее к числу 1234, которое может быть получено в результате работы алгоритма.
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр троичной записи числа кратна 9, то к этой записи справа дописывается 1
б) если сумма цифр троичной записи числа не кратна 9, то к этой записи справа дописывается троичная запись остатка от деления суммы цифр записи на 9;
Полученная таким образом запись является троичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Укажите минимальное число R, которое может быть результатом работы данного алгоритма, при условии, что N больше 777.
В ответе запишите это число в десятичной системе счисления.