Условие задачи
На вход алгоритма подаётся натуральное число 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'. Соответственно проверка будет выглядеть следующим образом:
1234
Затем выполняем шаг б): снова считаем количество единиц в уже обновлённой строке (после шага а добавился один разряд!) и дописываем остаток от деления на 2:
12
Важно: функция str() нужна, чтобы превратить число (0 или 1) в строку
4. Обратный перевод: Переводим итоговую строку обратно в десятичную систему: R = int(s, 2).
5. Условие и вывод: Проверяем условие if R > 31 и добавляем подходящие R в список. В конце выводим минимальное значение через min(results).
Почему нельзя использовать break? В отличие от задач на минимальное N, здесь мы ищем минимальное R. Меньшие N не обязательно дают меньшие R, поэтому нужно перебрать весь диапазон и собрать все возможные результаты, а затем выбрать наименьший.
Решение
1234567891011121314
Ответ: 33
