Задача к ЕГЭ по информатике на тему «задачи под вебы» №5

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

Источник: https://kpolyakov.spb.ru/

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

$F (0) = 1,$

F (n) = 1+ F (n − 1), если n > 0 и n нечётное, » class=»math» src=»/images/inform/quest/quest-7806-4.svg» width=»auto»> </p>
<p class= $F (n) = F(n∕2)$ в остальных случаях.

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

n = 1000000 * 500
# Инициализируем список f длиной n, заполняя его единицами
f = [1] * n
# Счетчик для подсчета количества значений f[i], равных 3
c = 0
for i in range(n):
    if i == 0:
# Для первого элемента списка устанавливаем значение равным 1
        f[i] = 1
    elif i % 2 != 0: # Если индекс i нечетный,
# устанавливаем f[i] равным 1 + f[i - 1]
        f[i] = 1 + f[i - 1]
    else: # Если индекс i четный,
# устанавливаем f[i] равным f[i // 2]
        f[i] = f[i // 2]
# Проверяем, равно ли значение f[i] тройке
    if f[i] == 3:
        c += 1 # Если да, увеличиваем счетчик c на 1
print(c)

Ответ: 406