Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
-
Прибавить 1
-
Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя — это последовательность команд. Например, если в начальный момент на экране находится число 1, то программа 212 последовательно преобразует его в 2, 3, 6.
Сколько существует программ, которые преобразуют исходное число 1 в число 14, и при этом никакая команда не повторяется более двух раз подряд?
Решение:
Решение на Python:
def F(x, y, last, k):
if x > y:
return 0
if x == y:
return 1
s = 0
if last == 1:
if k < 2:
s += F(x + 1, y, 1, k + 1)
else:
s += F(x + 1, y, 1, 1)
if last == 2:
if k < 2:
s += F(x * 2, y, 2, k + 1)
else:
s += F(x * 2, y, 2, 1)
return s
print(F(1, 14, 0, 0))Ответ: 6
Ответ:
6