Информатика. ЕГЭ. Задание 16. Информатика. ЕГЭ. Поляков-6830

Информатика. ЕГЭ

Задание 16. Информатика. ЕГЭ. Поляков-6830

Просмотры: 118

Изменено: 1 февраля 2025

(А. Богданов) Обозначим частное от деления натурального числа $a$ на натуральное число $b$ как $a // b$, а остаток как $a\%b.$ Алгоритм вычисления функции $F(n),$ где $n$ — натуральное число, задан следующими соотношениями:

$F(n) = n,$ если $n < 2$;
$F(n) = F(n // 2) + F(n \% 2)$, если $n \geqslant 2$.

Определите количество значений $n < 2^{30}$, для которых функция $F(n) = 27$.

Решение:

Функция $F(n)$ вычисляет сумму цифр в двоичной записи числа $n$, или, что то же самое, количество единиц в бинарном представлении $n.$ Поэтому, количество значений $n < 2^{30}$, для которых функция $F(n) = 27$ это в точности количество чисел, в двоичной записи которых не больше $30$ цифр, причём $27$ из них — единицы. Т.е. это $$ C^{27}_{30} = \frac{30!}{27! \cdot 3!} = \frac{28 \cdot 29 \cdot 30}{6} = 4060.$$

Ответ: $4060$