Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N без ведущих нулей.
2. Подсчитывается количество единиц и количество нулей в полученной двоичной записи. Эти числа переводятся в двоичную систему и записываются друг за другом без использования ведущих нулей: сначала количество единиц, затем количество нулей.
3. Результатом работы алгоритма становится десятичная запись полученного числа R.
Пример. Дано число N = 17. Алгоритм работает следующим образом.
1. Строим двоичную запись: 1710 = 100012.
2. В полученном двоичном числе две единицы и три нуля. Переводим в двоичную систему: 210 = 102, 310 = 112. Записываем подряд: 1011.
3. Переводим в десятичную систему: 10112 = 1110.
Результат работы алгоритма R = 11.
Определите минимальное число N, для которого результатом работы данного алгоритма будет R = 214.
Приведём решение на языке Python.
cislo = bin(214)[2:]
one, zero, otv = [], [] , []
for i in range(len(cislo) - 1):
if cislo[i + 1] != '0':
one.append(int(cislo[:i + 1], 2))
zero.append(int(cislo[i+1:], 2))
for j in range(len(one)):
otv.append(int('1' + '0' * int(zero[j]) + '1'*int(one[j]-1),2))
print(min(otv))
Ответ: 134217759.
Приведём аналитическое решение Фёдора Грановского.
Переведем число 214 в двоичную систему: 21410 = 110101102. Данное двоичное число на два числа без ведущих нулей может быть разбито четырьмя способами: 1, 1010110; 110, 10110; 11010, 110; 110101, 10. Минимальное количество знаков — 28, в получаемом двоичном числе, будет при разбиении 1102 = 610, 101102 = 2210, то есть в результате получится число состоящее из шести единиц и двадцати двух нулей. Минимальное такое число: 10000000000000000000000000111112 = 227 + 31 = 13421775910.