ЕГЭ 23 Динамическое программирование

№18 У исполнителя Калькулятор три команды, которым присвоены номера:

1. прибавь 1

2. умножь на 2

3. возведи в квадрат

Сколько есть программ, которые число 2 преобразуют в число 27?

def f(n):

if n==27: return (1)

if n>27: return (0)

if n<27: return f(n+1)+f(n*2)+f(n*n)

print (f(2))

ответ 92

Пример №2. У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 2,

2. умножь на 5.

Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 5 раз.

Программа для Калькулятора — это последовательность команд.

Сколько есть программ, которые число 2 преобразуют в число 50?

def f(n):

if n==50: return (1)

if n>50: return (0)

if n<50: return f(n+2)+f(n*5)

print (f(2))

ответ 7

№19 У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 1

2. увеличь число десятков на 1

Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется.

Сколько есть программ, которые число 11 преобразуют в число 27?

def f(n):

if n==27: return (1)

if n>27: return (0)

if n<27: return f(n+1)+f((n %100//10+1)*10+(n%10))

print (f(11))

ответ 8

№34 У исполнителя Калькулятор три команды, которым присвоены номера:

1. прибавь 1

2. сделай чётное

3. сделай нечётное

Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, третья переводит число x в число 2x + 1. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 2 преобразуют в число 16?

def f(n):

if n==16: return (1)

if n>16: return (0)

if n<16: return f(n+1)+f(n *2)+ f(n *2+1)

print (f(2))

ответ 40

№41 У исполнителя Калькулятор три команды, которым присвоены номера:

1. прибавь 1

2. прибавь 2

3. прибавь предыдущее

Первая команда увеличивает число на экране на 1, вторая увеличивает это число на 2, третья прибавляет к числу на экране число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11 прибавляется 10 и т. д.). Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 2 преобразуют в число 9?

def f(n):

if n==9: return (1)

if n>9: return (0)

if n<9: return f(n+1)+f(n +2)+ f(n+(n -1))

print (f(2))

ответ 57

№43 Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 3

Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 20 и при этом траектория вычислений содержит число 12?

Задача разбивается на 2 этапа. Сначала считаем от 3 до 12. Затем от 12 до 20. Ответом будет произведение ответов первого и второго этапов.

def f(n):

if n==12: return (1)

if n>12: return (0)

if n<12: return f(n+1)+f(n +3)

print("первый ответ = ",f(3))

m=f(3)

def f(n):

if n==20: return (1)

if n>20: return (0)

if n<20: return f(n+1)+f(n +3)

print("второй ответ = ",f(12))

k=f(12)

print("итого = ",m*k)

ответ 247

№79 Исполнитель Июнь16 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

3. Умножить на 3

Сколько существует программ, для которых при исходном числе 2 результатом является число 25 и при этом траектория вычислений не содержит число 20?

def f(n):

if n==25: return (1)

if n==20 or n>25: return (0)

if n<25: return f(n+1)+f(n *2)+ f(n*3)

print (f(2))

ответ 34

№92 Исполнитель R17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 3

3. Умножить на 2

Программа для исполнителя R17 – это последовательность команд. Сколько существует таких программ, которые исходное число 3 преобразуют в число 20 и при этом траектория вычислений программы содержит число 9 и число 12?

Задача разбивается на 3 этапа. Сначала считаем от 3 до 9. Затем от 9 до 12. Затем от 12 до 20. Ответом будет произведение ответов первого, второго и третьего этапов.

def f(n):

if n==9: return (1)

if n>9: return (0)

if n<9: return f(n+1)+f(n +3) +f(n *2)

print("первый ответ = ",f(3))

m=f(3)

def f(n):

if n==12: return (1)

if n>12: return (0)

if n<12: return f(n+1)+f(n +3) +f(n *2)

print("второй ответ = ",f(9))

k=f(9)

def f(n):

if n==20: return (1)

if n>20: return (0)

if n<20: return f(n+1)+f(n +3) +f(n *2)

print("третий ответ = ",f(12))

p=f(12)

print ("итого = ",m*k*p)

ответ 234