У исполнителя Калькулятор имеются три команды, которым присвоены номера:
1. Вычесть 1
2. Вычесть 3
3. Найти целую часть от деления на 2
Выполняя первую из них, исполнитель уменьшает число на экране на 1, выполняя вторую — уменьшает на 3, выполняя третью — делит на 2 нацело, отбрасывая остаток. Сколько существует программ, для которых при исходном числе 31 результатом является число 3, и при этом траектория вычислений не содержит числа 20 и 8 одновременно?
Приведём решение на языке Python.
from functools import cache
@cache
def Rr(m, f):
if m == 20 or m == 8:
f += 1
if f > 1 or m < 3:
return 0
if m == 3:
return 1
return Rr(m-1, f) + Rr(m-3, f) + Rr(m//2, f)
print(Rr(31, 0))
Ответ: 47315.
Приведём решение Ксении Ельцовой на языке Python.
def f(start,end,s):
if start == end:
if ',8,' in s and ',20,' in s:
return 0
else:
return 1
if start < end:
return 0
return f(start-1,end,s+str(start)+',')+f(start-3,end,s+str(start)+',')+f(start//2,end,s+str(start)+',')
print(f(31,3,','))