Задание 5

На вход алгоритма подаётся натуральное число N.

Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числа N.

2. Далее эта запись обрабатывается по следующему правилу:

a) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 10;

б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11.

Полученная таким образом запись является двоичной записью искомого числа R.

3. Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа 6₁₀ = 110₂ результатом является число 1000₂ = 8₁₀, а для исходного числа 4₁₀ = 100₂ это число 1101₂ = 13₁₀

Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее 16.

В ответе запишите это число в десятичной системе счисления.

Решение

🔹 Шаг 1. Перебор чисел и двоичная запись

for N in range(1, 20):
    s = f'{N:b}'
    print(N, '→', s)

📌 Результат: 1 → 1, 2 → 10, 3 → 11, 19 → 10011 и т.д.

🔹 Шаг 2. Проверка чётности числа единиц

for N in range(1, 20):
    s = f'{N:b}'
    if s.count('1') % 2 == 0:
        print(N, s, 'чётное число единиц')
    else:
        print(N, s, 'нечётное число единиц')

📌 Результат: 1 1 нечётное число единиц, 2 10 нечётное число единиц, 3 11 чётное число единиц, 19 10011 нечётное число единиц и т.д.

🔹 Шаг 3. Изменение двоичной строки

for N in range(1, 20):
    s = f'{N:b}'

    if s.count('1') % 2 == 0:
        s_new = '10' + s[2:] + '0'
        print(N, s, '→', s_new, '(заменили 2 старших разряда на 10, дописали 0)')
    else:
        s_new = '11' + s[2:] + '1'
        print(N, s, '→', s_new, '(заменили 2 старших разряда на 11, дописали 1)')

📌 Результат: 1 1 → 111 (заменили 2 старших разряда на 11, дописали 1), 2 10 → 111 (заменили 2 старших разряда на 11, дописали 1), 3 11 → 100 (заменили 2 старших разряда на 10, дописали 0), 19 10011 → 110111 (заменили 2 старших разряда на 11, дописали 1) и т.д.

🔹 Шаг 4. Перевод обратно в десятичное число

for N in range(1, 20):
    s = f'{N:b}'

    if s.count('1') % 2 == 0:
        s = '10' + s[2:] + '0'
    else:
        s = '11' + s[2:] + '1'

    R = int(s, 2)
    print(N, '→', s, '→', R)

📌 Результат: 1 → 111 → 7, 2 → 111 → 7, 3 → 100 → 4, 19 → 110111 → 55 и т.д.

🔹 Шаг 5. Поиск первого N, при котором R ≥ 16

Цель: собрать всё вместе и понять задачу целиком.

for N in range(1, 1000):
    s = f'{N:b}'
    if s.count('1') % 2 == 0:
        s = '10' + s[2:] + '0'
    else:
        s = '11' + s[2:] + '1'
    R = int(s, 2)
    if R >= 16:
        print(N)
        break

📌 Результат: минимальное значение N, при котором R ≥ 16.

Ответ: 8.