Условие КЕГЭ: Тип 5 № 554 Условие Поляков: Тип 5 № 1729
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
Строится двоичная запись числа N.
К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Сколько различных чисел, принадлежащих отрезку [20; 50], могут появиться на экране в результате работы автомата?
Вариант 1: решение через строки
Комментарии к первому варианту решения задачи:
создаем множество set(), в которое будем добавлять полученные числа
пробегаем числа от 1 (т.к. N - натуральное число)
переводим число из двоичной записи в десятичную
выполняем 2 раза действие
остаток от деления суммы на 2 дописываем в конец числа (справа) (т.к. в двоичной записи содержатся только числа ‘1’ и ‘0’, то, чтобы получить сумму цифр такого числа, мы можем найти сумму единиц в этом числе)
переводим число из двоичной записи в десятичную
если число принадлежит отрезку [20; 50]
то добавляем во множество A через метод .add()