Исполнитель Щелчок преобразует число на экране. У исполнителя есть три команды:
1. Поделить на 2, если число четное
2. Прибавить 1
3. Прибавить треть числа, если число кратно трем
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числe 1 результатом является число 60, при этом программа содержит 25 команд, при этом одно и то же число не может встречаться несколько раз в траектории вычислений исполнителя. Исполнителю также нельзя посещать начальное значение.
Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 122 при исходном числе 6 траектория будет состоять из чисел 3, 4, 5.
Решение 1
def f(st, fn, cmd, a):
if st in a or cmd > 25:
return 0
if st == fn and cmd == 25:
return 1
a.add(st)
x, y, z = 0, 0, 0
if st % 2 == 0:
x = f(st // 2, fn, cmd + 1, a.copy())
y = f(st + 1, fn, cmd + 1, a.copy())
if st % 3 == 0:
z = f(st + st // 3, fn, cmd + 1, a.copy())
return x + y + z
Решение 2
В соавторстве с марафонцем
Примечание: при добавлении в массив b элементов массива a используется символ *, чтобы добавить в массив именно элементы массива а, а не создать дополнительную вложенность массивов. Например: есть массив a = [1, 2, 3]. Если выполнить операцию b.append([a, 4]), то массив b = [[[1, 2, 3], 4]]. Если выполнить b.append([*a, 4]), то массив b = [[1, 2, 3, 4]].
paths = [[1]]
for i in range(25):
new_paths = []
for path in paths:
x = path[-1]
if x % 2 == 0:
if x // 2 not in path:
new_paths.append([*path, x//2])
if x % 3 == 0:
if x + x // 3 not in path:
new_paths.append([*path, x + x//3])
if x + 1 not in path:
new_paths.append([*path, x+1])
paths = new_paths.copy()
ans = 0
k = []
for path in paths:
if path[-1] == 60:
k.append(path)
ans += 1
print(ans)