ЕГЭ по информатике, задание 23
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера:
Прибавить значение старшего разряда.
Прибавить 3.
Сделать нечётным.
Первая команда увеличивает число на экране на величину первого разряда слева, вторая увеличивает это число на 3, третья переводит число
x в число 2x−1.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 42 результатом является число 89 и при этом траектория содержит число 73 и не содержит числа 81?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 7 траектория будет состоять из чисел 13, 14, 17.
Я написал прогу, но она не работает. Помогите, пожалуйста, если не трудно. Что не так здесь?
"Не так" то, что ты пытаешься решать задачу рекурсией и это крайне неэффективно. Такие задачи решаются динамическим программированием:
t = [0] * 90
t[42] = 1
for i in range(43, 90):
if i == 81: continue # не проходим через 81
t[i] = t[i - 3] # прибавить 3
if i % 2: t[i] += t[(i + 1) // 2] # сделать нечётным
a, b = i // 10, i % 10 # разряды числа
if a <= b: # результат прибавления старшего разряда не меняет старший разряд
t[i] += t[i - a]
elif a - b > 1: # результат прибавления старшего разряда увеличивает старший разряд
t[i] += t[i - a + 1]
if i == 73: # убираем траектории, не проходящие через 73
for j in range(42, 73): t[i] = 0
print(t[89]) def f(curr,end):
if curr>end or curr==81: return 0
if curr==end: return 1
if curr<end: return f((curr+(curr//10)),end)+f(curr+3,end)+f(2*curr-1,end)
print(f(42,73)*f(73,89)) забей, до егэ 2025 ещё как до китая
def f(a,b):
if a > b or a==81:
return 0
if a==b:
return 1
return f(a+(a//10),b)+f(a+3,b)+f(2*a-1,b)
print(f(42,73)*f(73,89))
def f(x,y):
if x==y:
return 1
if x>y or x==81:
return 0
if x<y:
return f(x+3,y)+f(x+(x//(10**(len(str(x))-1))),y)+f(2*x-1,y)
print(f(42,73)*f(73,89))
вот правильно решение через рекурсию