ПРОГРАММИРОВАНИЕ 11 КЛАСС
На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Полученная запись переворачивается (записывается слева направо).
3. В полученной записи дублируется младший (правый) бит.
Полученная таким образом запись (в ней на один разряд больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Например, для числа 11 алгоритм будет выполняться следующим образом:
На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Складываются все цифры полученной двоичной записи. Если сумма получилась нечетной, справа к двоичной записи дописываются две единицы, иначе две единицы дописываются слева.
Полученная таким образом запись является двоичной записью искомого числа R.
Пример. Дано число N = 13. Алгоритм работает следующим образом:
1. Двоичная запись числа N: 13 = 1101.
2. Сумма цифр двоичной записи 3, число нечетное. Значит получается число 110111.
3. 1101112 = 5510.
Найдите наименьшее число N, для которого результат работы автомата больше, чем 102.
Задача состоит в том, чтобы найти наименьшее число \( N \), для которого результат работы алгоритма будет больше 102. Давайте разберём шаги алгоритма:
1. Строится двоичная запись числа \( N \).
2. Считается сумма цифр двоичной записи.
- Если сумма нечётная, справа к двоичной записи дописываются две единицы.
- Если сумма чётная, две единицы дописываются слева.
3. Преобразованная двоичная запись превращается обратно в десятичное число \( R \).
4. Необходимо найти наименьшее \( N \), для которого \( R > 102 \).
Алгоритм решения:
1. Перебираем числа \( N \) начиная с 1.
2. Для каждого числа:
- Строим двоичную запись.
- Считаем сумму цифр двоичной записи.
- Дописываем две единицы в зависимости от чётности суммы.
- Преобразуем обратно в десятичное число и проверяем, больше ли оно 102.
3. Как только найдено первое число \( N \), для которого результат больше 102, выводим его.
Реализуем это на Python:
def find_min_n():
n = 1
while True:
# Шаг 1: двоичная запись числа N
binary_n = bin(n)[2:]
# Шаг 2: сумма цифр двоичной записи
digit_sum = sum(int(bit) for bit in binary_n)
# Шаг 3: добавление двух единиц
if digit_sum % 2 == 1:
binary_r = binary_n + '11'
else:
binary_r = '11' + binary_n
# Шаг 4: перевод обратно в десятичное число
r = int(binary_r, 2)
# Проверка условия
if r > 102:
return n
# Переход к следующему числу
n += 1
# Найдём наименьшее N
result = find_min_n()
print(result)
Этот код перебирает числа, начиная с 1, и для каждого числа выполняет алгоритм. Как только найдено такое \( N \), для которого \( R > 102 \), программа выводит это число.
Запустив этот код, можно найти наименьшее \( N \).
17
