Задание 23. Информатика. Демо 2024

Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:

  1. Прибавить \(1\)
  2. Умножить на \(2\)
  3. Возвести в квадрат
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе \(2\) результатом является число \(20\), при этом траектория вычислений не содержит числа \(11\)?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе \(4\) траектория будет состоять из чисел \( 16, \, 32, \, 33\).

Решение:

Python


def f(num, target):
    if num == target:
        return 1
    if num > target or num == 11:
        return 0
    return f(num+1, target) + f(2*num, target) + f(num**2, target)

print(f(2, 20))

Ответ: \(37\)