На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N
б) если число N
Полученная таким образом запись является двоичной записью искомого числа R.
Например, для исходного числа 510 = 1012 результатом является число 1011102 = 4610, а для исходного числа 910 = 10012 результатом является число 10010012 = 7310.
Укажите наибольшее число N, после обработки которого с помощью этого алгоритма получается число R,
Приведём решение на языке Python.
for i in range(100, 0, -1):
s = bin(i)[2:] # перевод в двоичную систему
s = str(s)
if i % 3 == 0:
s += s[-3:]
else:
s += bin(3*(i%3))[2:]
r = int(s, 2) # перевод в десятичную систему
if r < 100:
print(i)
break
Ответ: 22.
Приведём решение Евгения Джобса (аналитическое).
Для аналитического рассуждения имеем два случая.
Случай 1. Число
100 // 8 = 12 (// — целочисленное деление),
знаем, что 12 делится
1210 = 11002 → 11001002 → 10010.
Следовательно,
910 = 10012 = 10010012 = 7310.
Следовательно,
Случай 2. Число
Остаток
Дописывается три разряда, следовательно, число увеличивается по формуле 8 · x + 6. Значит, нужно взять число,
Остаток
Дописывается два разряда. Следовательно, число увеличивается по формуле 4 · х + 3. Найдем максимальное число, которое может удовлетворять условию:
100 // 4 = 25, 25 % 3 = 1 (остаток от деления),
тогда 25 · 4 + 3 = 103 (не подходит).
Берем предыдущее с таким же остатком: 22 · 4 + 3 = 91. Следовательно, 22 — наибольшее число, остаток от деления