Задача:
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
a. если сумма цифр двоичной записи чётная, то к этой записи справа дописывается 0, а два левых разряда заменяются на 10;
b. если сумма цифр двоичной записи нечётная, то к этой записи справа дописывается 1, а два левых разряда заменяются на 11.
Полученная таким образом запись является двоичной записью искомого числа R. Например, для исходного числа 6 = 1102 результатом является 10002 = 8, а для исходного числа 4 = 1002 результатом является 11012 = 13. Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее 50. В ответе запишите это число в десятичной системе счисления.
Решение:
R=51, 11 0011, справа дописана цифра 1, число единиц исходного числа Nв двоичной системе должно быть нечётным, следовательно первые два бита исходного числа N могли быть только 11.
(00 быть не может, т.к все нули перед единицей становятся незначащими и число N превращается в 1. Быть не может 01, первый бит становится незначащим. Быть не может 10, т.к. число единиц в N становится чётным, и справа должен дописываться 0)
Таким образом, число поданное на вход алгоритма: N=11001, число единиц нечётное, справа дописали 1, два левых разряда 11, заменили на 11. Это число 25 в десятичной системе счисления.
На выходе R=51, 11 0011.
N=25, R=51
Аналогично рассуждаем дальше. Пусть R=52, 11 0100. Справа дописан 0, число единиц в исходном числе Nдолжно быть чётным, два левых разряда должны были быть заменены на 10, а там 11. Следовательно, не существует такого N, для которого R=52.
Пусть R=53, 11 0101. Дописана 1, число единиц в исходном числе N должно быть нечётным, следовательно, первые два бита могут быть только 11, которые заменили на 11. Исходное число N=11 010, это N=26.
Пусть R=54, 11 0110. Дописан 0, значит число единиц исходного числа Nчётное.
Это возможно для N=11 011 (почему? См. выше, выделенное курсивом)
N=11 011, это N=27.
Пусть R=55, 11 0111. Число единиц в Nдолжно быть нечётным, N=10 011, это N=19.
Пусть R=56, 111000. Число единиц в N должно быть чётным, N=10 100, это N=20.
Пусть R=57, 11 1001. Число единиц в N должно быть нечётным, N=11 100, это N=28.
Далее при увеличении R, N – увеличивается.
Ответ:минимальное N=19, при этом в результате работы алгоритма получится R=55, большее 50.
Решение на Python:
s = bin(n)[2:] очередное выбранное число n преобразуется из десятичной системы счисления в двоичную, записывается в переменную s. Если не указать параметр [2:], то двоичное число будет выглядеть так: 0b11010, этот параметр вырезает технологические символы 0b.
Команда s = str(s) преобразует двоичное число s в строку s.
Команда s.count('1') подсчитывает число единиц (символов «1») в строке s
Если оно чётное, то из строки s вырезаются два первых символа s[2:] вместо них записывается "10", а в конец строки приклеивается '0'
В результате программа выводит на экран столбца чисел, в первом столбце исходное число N, во втором соответствующее значение R. Находим N =19 при минимальном R=55.