Задание №5 — Анализ простейших алгоритмов

#69839Задание №5ФИПИ

Анализ алгоритмов и исполнители

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:

1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то к этой записи дописываются три последние двоичные цифры;
б) если число N на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
Полученная таким образом запись является двоичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа 12 = 1100₂ результатом является число 1100100₂ = 100, а для исходного числа 4 = 100₂ это число 10011₂ = 19.
Укажите минимальное число R, большее 151, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.

Правильный ответ

163

Пояснение

Решение:

Алгоритм дописывает к двоичной записи числа $N$ либо два, либо три разряда. Если остаток от деления на 3 равен 1, приписывается $1 \cdot 3 = 3 = 11_2$ — два разряда, и тогда $R = 4N+3$ . Если остаток равен 2, приписывается $2 \cdot 3 = 6 = 110_2$ — три разряда, и $R = 8N+6$ . Если же $N$ кратно 3, приписываются три последние двоичные цифры самого $N$ , то есть $R = 8N + (N \bmod 8)$ .

Нам нужно наименьшее $R \gt 151$ . Заметим, что $151 = 10010111_2$ , а любое семиразрядное двоичное число не превосходит 127, поэтому у искомого $R$ не меньше восьми разрядов; девятиразрядные числа не меньше 256, так что достаточно разобрать восьмиразрядные $R$ .

Остаток 1: дописываются два разряда, значит $N$ шестиразрядное, $32 \le N \le 63$ , и $R = 4N+3$ . Из $R \gt 151$ получаем $N \gt 37$ ; ближайшее такое $N$ с остатком 1 — это $N = 40$ , оно даёт $R = 163$ .
Остаток 2: дописываются три разряда, значит $N$ пятиразрядное, $16 \le N \le 31$ , и $R = 8N+6$ . Числа с остатком 2 дают $N = 17 \Rightarrow R = 142$ , $N = 20 \Rightarrow R = 166$ ; первое подходящее значение — 166.
$N$ кратно 3 и пятиразрядное: $N = 18, 21, 24, 27, 30$ дают соответственно $R = 146, 173, 192, 219, 246$ ; первое подходящее — 173.

Наименьшее из чисел 163, 166 и 173 — это 163. Проверим: $N = 40 = 101000_2$ , остаток от деления 40 на 3 равен 1, значит дописываем $3 = 11_2$ и получаем $10100011_2 = 163$ .

Перебор подтверждает ответ:

def R(n):
    b = bin(n)[2:]
    if n % 3 == 0:
        return int(b + b[-3:], 2)          # дописали три последние цифры
    return int(b + bin(n % 3 * 3)[2:], 2)  # дописали остаток, умноженный на 3

print(min(R(n) for n in range(1, 1000) if R(n) > 151))

Ответ: 163