Как решить эту задачу вручную? Ал­го­ритм вы­чис­ле­ния зна­че­ния функ­ции F(n), где n — целое не­от­ри­ца­тель­ное число, задан сле­ду­ю­щи­ми со­от­но­ше­ни­я­ми:
F(0) = 0;
F(n) = F(n − 1) + 1, если n нечётно;
F(n) = F(n / 2), если n > 0 и при этом n чётно.Ука­жи­те ко­ли­че­ство таких зна­че­ний n < 1 000 000 000, для ко­то­рых F(n) = 3.

Предыдущий
вопрос Следующий
вопрос

Данная рекурсивная функция фактически подсчитывает количество единиц в числе n в двоичном виде. Тогда необходимо найти количество чисел в заданном диапазоне, которые в двоичном виде имеют только две цифры «1». То есть, подходят числа вида 11, 101, 110, 1001, 1010, 1100 и т. д. Заметим также, что количество искомых чисел среди чисел, которые в двоичном виде состоит из двух знаков, равно 1, среди чисел, состоящих в двоичном виде из трёх знаков, равно 2, а среди чисел, состоящих в двоичном виде из четырёх знаков, равно 3, и т. д.

Число 1 000 000 000 в двоичном виде имеет 30 знаков. Максимальное подходящее число, для которого F(n) = 2 и состоящее в двоичном виде из 30 знаков — 1100..002 = 805 306 36810, что меньше границы заданного диапазона. Значит, чтобы подсчитать количество подходящих чисел n, имеющих в двоичном виде от 1 до 30 знаков и просуммировать количество найденных чисел для каждой разрядности.

Ответ: 435