У исполнителя Калькулятор имеются три команды, которым присвоены номера:
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,','))
Приведём решение Юрия Красильникова на языке Python.
def f(s,e):
if s < e: return 0
if s == e: return 1
return f(s-1,e) + f(s-3,e) + f(s//2,e)
print(f(31,3) - f(31,20)*f(20,8)*f(8,3))
# из общего числа программ вычитаем число программ, которые содержат одновременно 20 и 8