Исполнитель Щелчок преобразует число на экране. У исполнителя есть три команды:
1. Прибавить 1
2. Если число кратно 
, прибавить к нему это же число, умноженное на 
3. Умножить на 2
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числe 3 результатом является число 50, при этом программа содержит 20 команд, а траектория обязательно проходит через число 15?
Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 8, 14, 28.
Стоит сказать, что динамическое решение данной задачи более трудоемкое и занимает большее количество времени для исполнения. Поэтому рекомендуется использовать именно рекурсивную реализацию.
Решение 1 (Рекурсия)
def f(st, fn, flag, flag_number, count, end_count):
if st == fn and count == end_count and flag:
return 1
if st > fn or count > end_count:
return 0
if st == flag_number:
flag = True
x = f(st + 1, fn, flag, flag_number, count + 1, end_count)
y = f(st * 2, fn, flag, flag_number, count + 1, end_count)
z = f(st + st * 0.75, fn, flag, flag_number, count + 1, end_count) *
(st % 8 == 0)
return x + y + z
print(f(3, 50, False, 15, 0, 20))
Решение 2 (Динамика)
ans = []
ans.append((3, 0))
for operations in range(20):
can_get = []
for i in ans:
a, flag = i
if a + 1 == 15:
can_get.append((a + 1, 1))
else:
can_get.append((a + 1, flag))
if a % 8 == 0:
if int(a + a * 0.75) == 15:
can_get.append((int(a + a * 0.75), 1))
else:
can_get.append((int(a + a * 0.75), flag))
can_get.append((a * 2, flag))
ans = can_get
otv = 0
for i in ans:
a, flag = i
if (a == 50) and (flag):
otv += 1
print(otv)