Исполнитель Повторюша преобразует число, записанное на экране. У исполнителя есть шесть команд, которым присвоены номера:
1. Прибавить 1.
2. Прибавить 2.
3. Прибавить 3.
4. Умножить на 2.
5. Умножить на 3.
6. Умножить на 4.
Программа для исполнителя Повторюша – это последовательность команд. Сколько различных результатов можно получить из исходного числа 1 после выполнения программы, содержащей 10 команд, если известно, то можно использовать только те команды, номера которых отличаются на 1 от номера команды, сделанной на предыдущем шаге (на первом шаге можно использовать любую команду)?
a = [[1, ’0’]]
for i in range(10):
n = len(a)
for j in range(n):
l = a.pop(0)
# Список доступных команд
command = [[l[0] + 1, ’1’], [l[0] + 2, ’2’], [l[0] + 3, ’3’],
[l[0] * 2, ’4’], [l[0] * 3, ’5’], [l[0] * 4, ’6’]]
# Если первый ход - доступно все
if l[1] == ’0’:
for k in range(6):
a.append(command[k])
# Анализируем края (по одной команде можем только)
elif l[1] == ’1’:
a.append(command[1])
elif l[1] == ’6’:
a.append(command[4])
# Некрайние случаи
else:
# Если индекс на 1 меньше, и еще -1 от команды (влево)
a.append(command[int(l[1]) - 2])
# Индекс на 1 меньше, и еще +1 от команды (вправо)
a.append(command[int(l[1])])
a = set([j[0] for j in a])
print(len(a))
# Альтернативное решение:
s = set()
def f(a, h, c):
if h == 10:
s.add(a)
return
if c == 0:
f(a + 1, h + 1, 1)
f(a + 2, h + 1, 2)
f(a + 3, h + 1, 3)
f(a * 2, h + 1, 4)
f(a * 3, h + 1, 5)
f(a * 4, h + 1, 6)
elif c == 1:
f(a + 2, h + 1, 2)
elif c == 2:
f(a + 1, h + 1, 1)
f(a + 3, h + 1, 3)
elif c == 3:
f(a + 2, h + 1, 2)
f(a * 2, h + 1, 4)
elif c == 4:
f(a + 3, h + 1, 3)
f(a * 3, h + 1, 5)
elif c == 5:
f(a * 2, h + 1, 4)
f(a * 4, h + 1, 6)
elif c == 6:
f(a * 3, h + 1, 5)
f(1, 0, 0)
print(len(s))
Ответ: 445