Исполнитель Щелчок преобразует число на экране. У исполнителя есть три команды:
1. Прибавить 2, если число кратно 3
2. Прибавить 3, если число кратно 2
3. Прибавить 1, если число не кратно ни 2, ни 3
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числe 3 результатом является число 27, при этом программа содержит 12 команд, а траектория обязательно не проходит через число 22?
Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 3 траектория будет состоять из чисел 5, 6, 9.
Решение 1 (Рекурсия)
def f(st, fn, exit_number, count, end_count):
if st == fn and count == end_count:
return 1
if st > fn or count > end_count or st == exit_number:
return 0
x = f(st + 2, fn, exit_number, count + 1, end_count) * (st % 3 == 0)
y = f(st + 3, fn, exit_number, count + 1, end_count) * (st % 2 == 0)
z = f(st + 1, fn, exit_number, count + 1, end_count) * (st % 2 != 0
and st % 3 != 0)
return x + y + z
print(f(3, 27, 22, 0, 12))
Решение 2 (Динамика)
ans = []
ans.append(3)
for operations in range(12):
can_get = []
for i in ans:
if i == 22:
continue
if i % 3 == 0:
can_get.append(i + 2)
if i % 2 == 0:
can_get.append(i + 3)
if (i % 2 != 0) and (i % 3 != 0):
can_get.append(i + 1)
ans = can_get
print(ans.count(27))