Е23.25 преобразуют исходное число 2 в число 90, и при этом траектория

Администратор

5 лет назад

Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 3
Первая команда увеличивает число на экране на 1, вторая умножает его на 3.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 2 в число 90, и при этом траектория вычислений содержит число 28?

Траектория вычислений – это последовательность результатов выполнения всех команд программы. Например, для программы 212 при исходном числе 4 траектория будет состоять из чисел 12, 13, 39.

Ответ:

Источник: СтатГрад Вариант ИН2110101 27.10.2021– задание №123

Показать решение...

Решение:

dp=[0]*93
dp[2]=1
for i in range(2,28):
    if i+1<=28:dp[i+1]+=dp[i]
    if i*3<=28:dp[i*3]+=dp[i]
for i in range(28,90):
    if i+1<=90:dp[i+1]+=dp[i]
    if i*3<=90:dp[i*3]+=dp[i]
print(dp[90])

dp=[0]*93

dp[2]=1

for i in range(2,28):

if i+1<=28:dp[i+1]+=dp[i]

if i*3<=28:dp[i*3]+=dp[i]

for i in range(28,90):

if i+1<=90:dp[i+1]+=dp[i]

if i*3<=90:dp[i*3]+=dp[i]

print(dp[90])

или

def f(x, y):
    if x > y:
        return 0
    if x == y:
        return 1
    if x < y:
        return f(x + 1, y) + f(x * 3, y)
print(f(2, 28) * f(28, 90))

def f(x, y):

if x > y:

return 0

if x == y:

return 1

if x < y:

return f(x + 1, y) + f(x * 3, y)

print(f(2, 28) * f(28, 90))

Ответ: 56