Исполнитель преобразует число на экране. У исполнителя есть...

Задание:

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

A. Прибавить 1
B. Умножить на 2
C. Возвести в квадрат

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

Решение (аналитическое)

Построим таблицу и для каждого числа определим, из какого меньшего числа можно прийти в текущее (первая строка для команды А, вторая - для В, третья – для С.

Теперь слева направо просуммируем значения в соответствующих ячейках, записав в качестве значения для 2 единицу, для 11 - 0.

Ответ: 37

Решение (программное)

Напишем рекурсивную функцию, которая будет увеличивать исходное число до тех пор, пока либо не придет в конечное значение, либо не превысит его, либо не придет в запрещенное значение
Если начальное значение при вызове равно конечному – мы нашли одну траекторию, если больше – не найдем траекторию, потому что из большего значения не сможем попасть в меньшее. Также возвращаем 0, когда доходим до значения 11, так как все такие траектории нас не интересуют по условию задачи.

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

print(f(2, 20)) 

Источник: Информатика с Джобсом | ЕГЭ