Исполнитель Щелчок преобразует число на экране. У исполнителя есть три команды:
1. Прибавить 3
2. Умножить на 2
3. Приписать любую цифру от 0 до 9 справа (1 
10, или 1 
11, или 1 
12 и т.д.)
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числe 1 результатом является число 48, при этом команда 3 встречается в программе чаще чем команда 2? Примеры программ: 33312 — True, 312 — False
Стоит сказать, что динамическое решение получается довольно трудоемким и громоздким, поэтому рекомендуется использовать рекурсивную реализацию в данной задаче.
Решение 1 (Рекурсия)
def f(st, fn, count_2, count_3):
if st == fn and count_3 > count_2:
return True
if st > fn:
return False
x = f(st + 3, fn, count_2, count_3)
y = f(st * 2, fn, count_2 + 1, count_3)
z = [0] * 10
for i in range(10):
z[i] = f(st * 10 + i, fn, count_2, count_3 + 1)
return x + y + sum(z)
print(f(1, 48, 0, 0))
Решение 2 (Динамика)
ans = set()
ans.add((1, 0, 0)) # (куда пришли, сколько раз использовали вторую команду, раз использовали третью команду)
otv = 0
for operations in range(1000):
can_get = set()
for i in ans:
a, cnt_2, cnt_3 = i
if (a == 48) and (cnt_2 < cnt_3):
otv += 1
continue
if a + 3 <= 48:
can_get.add((a + 3, cnt_2, cnt_3))
if a * 2 <= 48:
can_get.add((a * 2, cnt_2 + 1, cnt_3))
for j in range(9):
new_numb = int(str(a) + str(j))
if new_numb <= 48:
can_get.add((new_numb, cnt_2, cnt_3 + 1))
if len(can_get) == 0:
break
ans = can_get
print(otv)