ЕГЭ–2026, информатика: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 16 № 47013 Добавить в вариант

Алгоритм вычисления значения функции 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. То есть, подходят числа вида 111, 1011, 1101, 1110 и так далее. Число 1 000 000 000 в двоичном виде имеет 30 знаков. То есть необходимо разместить три единицы среди 30 позиций всеми возможными способами. Воспользуемся формулой вычисления сочетаний из 30 позиций по 3:

$дробь: числитель: 30!, знаменатель: 27! умножить на 3! конец дроби = дробь: числитель: 28 умножить на 29 умножить на 30, знаменатель: 2 умножить на 3 конец дроби =4060.$

Ответ: 4060.

Приведём решение Бориса Савельева на языке Python.

cnt=0

for i in range (2,100):

for j in range (0,i):

for k in range (0,j):

if (2**i+2**j+2**k)<1000000000:

cnt+=1

print(cnt)

Аналоги к заданию № 46974: 47013 Все

Спрятать решение · Прототип задания · Помощь