Задача к ЕГЭ по информатике на тему «одна функция» №23

Просмотров 8 Комментарии 0

(Статград) Алгоритм вычисления значения функции $F(n)$ , где $n$ – целое неотрицательное число, задан следующими соотношениями:

$F (0) = 0$

$F (n) = 1+ F (n − 1)$ если 0 » class=»math» width=»auto»> и $n$ нечётное

$F (n) = F(n∕2)$ в остальных случаях

Определите количество значений $n$ на отрезке [1, 1000000000], для которых $F (n) = 3$

Если внимательно посмотреть на перебор до 1000 например, то можно заметить, что у подходящих чисел ровно три единицы в 2 системе счисления. Значит эта рекурсия подсчитывает количество единиц в 2-сс.

Также мы знаем, что единицы в 2-сс появляются так: 2 умножаем на какую-то степень n и получаем единичку.

Например число 7: $22 + 21 + 20 = 4+ 2 +1$ . И в 2-сс выглядит как $1112$ . Как раз три единицы.

Также, чтобы получить единицы на трех разных местах мы должны возводить двойки в разные степени и складывать эти числа(как мы уже выяснили на числе 7).

ans = 0

for i in range(31):

    for j in range(i + 1, 31):

        for k in range(j + 1, 31):

            s = 2 ** i + 2 ** j + 2 ** k

            if 1 <= s <= 10 ** 9: ans += 1

print(ans)

Также можно увидеть, что ответ равен $C3 = 4060 30$ .

Все потому что $30 2$ больше миллиарда, но если поставить 3 первые единицы на позициях в 2-сс и остальные нули, то получим число меньше миллиарда.

Ответ: 4060