Как решить эту задачу вручную? Алгоритм вычисления значения функции 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.
Как решить эту задачу вручную? Алгоритм вычисления значения функции 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.
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.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Данная рекурсивная функция фактически подсчитывает количество единиц в числе 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