Динамическое программирование (рекурсия)

Динамическое прогр а ммирование

ЕГЭ, КИМ 23

учитель МБОУ СОШ с.Тербуны

Болгова Н.А.

КИМ -23 (П, 8 мин)

1 способ: ручная прокрутка

• 1. Прибавить 1
• 2. Умножить на 2

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

1 способ: ручная прокрутка

• 1. Прибавить 1
• 2. Умножить на 2

1 →10, 10→35, не содержит 17

1 способ: ручная прокрутка

• 1. Прибавить 1
• 2. Умножить на 2

1 →10= 14 пр

10→35, не содержит 17

2 способ: программирование

2 способ: программирование

Практика (глава 6/practice11-6bu (стр 20)

Уровень B.

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

• 1. прибавь 1
• 2. увеличь вторую с конца цифру на 1

Первая из них увеличивает число на экране на 1, вторая –

увеличивает на 1 число десятков. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется.

Напишите программу, которая определяет количество программ для преобразования числа A в число B с помощью этого

исполнителя. Числа A и B вводятся с клавиатуры.

Пример : A = 3, B = 65. Ответ: 28711.

Уровень В

• A = int(input("A=")) B = int(input("B=")) A, B = 3, 65

N = [0]*(B+1) N[A] = 1

minActive = 0

for i in range(A+1, B+1): N[i] = N[i-1]

if (i//10) % 10 != 9: N[i] += N[i-10]

print( "Количество программ: " , N[B] )

y or x // 10 % 10 == 9: return 0 if x return f(x + 1, y)+f(x + 10, y) print(f(3, 65)) " width="640"

def f(x,y):

if x == y:

return 1

if x y or x // 10 % 10 == 9:

return 0

if x

return f(x + 1, y)+f(x + 10, y)

print(f(3, 65))

Уровень C.

• У исполнителя Калькулятор есть три команды, которым присвоены номера:
• 1. прибавь 1
• 2. умножь на 2
• 3. умножь на 3
• Напишите программу, определяющую количество

программ, которые преобразуют исходное число A в число B, и при этом траектория вычислений содержит

число M C (25) и не содержит чисел X и Y (13, 39) ? Все

неизвестные значения вводятся с клавиатуры.

• Пример : A = 3, B = 135, С = 25, X = 13, Y = 39.
• Ответ: 4130.

•

47

Исполнитель А13S преобразует целое число, записанное на экране. У исполнителя три команды, каждой команде

присвоен номер:

• Прибавь 1
• Прибавь 3
• Прибавь предыдущее

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

исполнителя А13S – это последовательность команд.

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

• Прибавь 1

• Прибавь 3

• Прибавь предыдущее

def f(x,y):

………

if x

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

print(f(2, 10))

Углубленный уровень

(№ 5543) (М. Шагитов)

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

• Прибавь 2

• Умножь на 3
• Умножь на 4

Сколько существует различных программ, которые преобразуют число 1 в число 600 , и при этом траектория вычислений не содержит двух идущих подряд нечётных чисел .

y or ………: return 0 z = x return f(x + 2, y, z) + f(x * 3, y, z) + f(x * 4, y, z) print( 'к=' ,f(1, 600, 0)) " width="640"

Прогр а мма:

• def f(x, y, z):

#х – исходное число, у – результат, z- подряд

идущее число после х

if x == y:

return 1

if x y or ………:

return 0

z = x

return f(x + 2, y, z) + f(x * 3, y, z) + f(x * 4, y, z)

print( 'к=' ,f(1, 600, 0))

(№ 5465) (Е. Джобс)

Исполнитель преобразует число, записанное на экране. У

исполнителя есть две команды, которым присвоены номера:

• Вычти 3
• Раздели нацело на 2

Выполняя первую из них, исполнитель уменьшает число на экране на 3, выполняя вторую – делит число на экране на 2 нацело, отбрасывая остаток. Программой для

исполнителя называется последовательность команд.

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

(№ 5404) (Е. Джобс)

K = 34

Исполнитель преобразует число, записанное на экране. У

исполнителя есть две команды, которым присвоены номера:

• Сложи разряды числа

• Перемножь разряды числа

Выполняя первую из них, исполнитель складывает разряды числа и выводит соответствующее значение на экран. При выполнении второй команды находится произведение разрядов, которое выводится на экран. Программой для исполнителя называется

последовательность команд. Например, программа 221

примененная к числу 93 выполнится следующим образом: 9*3 = 27, 2*7 = 14, 1+4 = 5.

Найдите количество различных двузначных чисел, которые этот исполнитель моет преобразовать в число 8?

Прогр а мма:

def f(x, y):

… .

K = 34

k = 0

rezult = 8

for i in range( 10, 100): if f(i, rezult):

k += 1

print(k)

(№ 5404) (Е. Джобс)

K = 34

Исполнитель преобразует число, записанное на экране. У

исполнителя есть две команды, которым присвоены номера:

• Сложи разряды числа

• Перемножь разряды числа

Выполняя первую из них, исполнитель складывает разряды числа и выводит соответствующее значение на экран. При выполнении второй команды находится произведение разрядов, которое выводится на экран. Программой для исполнителя называется

последовательность команд. Например, программа 221

примененная к числу 93 выполнится следующим образом: 9*3 = 27, 2*7 = 14, 1+4 = 5.

Найдите количество различных двузначных чисел, которые этот исполнитель моет преобразовать в число 8?

(№ 5403) (А. Богданов)

K = 1025

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

номера:

• Прибавь 2

• Умножь на 2
• Возведи в квадрат

Сколько существует различных программ с нечётным числом команд , которые преобразуют исходное число 1 в число 100?

Подсказка: для единицы нужно исключить команду «Возведи в квадрат», т.к. этот процесс бесконечен и приведет к зацикливанию

y: return 0 if x == y and k % 2 == 1: return 1 if x != 1: return f(x+2, y, k+1)+f(x*2, y, k+1)+f(x**2, y, k+1) else: return f(x + 2, y, k + 1) + f(x * 2, y, k + 1) print(f(1, 100, 0)) " width="640"

Прогр а мма:

def f(x, y, k): if x y:

return 0

if x == y and k % 2 == 1: return 1

if x != 1:

return f(x+2, y, k+1)+f(x*2, y, k+1)+f(x**2, y, k+1) else:

return f(x + 2, y, k + 1) + f(x * 2, y, k + 1)

print(f(1, 100, 0))

(№ 5273) (М. Шагитов)

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

• Умножь на 5

• Умножь на 3
• Прибавь 45

Сколько существует различных программ, которые преобразуют исходное число 1 в число 2970, и при этом траектория вычислений не более 4 команд

«умножь на 5», не менее 2 команд «умножь на 3», и ровно 5 команд «прибавь 45»?

= 2 and m45 == 5 print(f(1,2970)) " width="640"

m5 = счет команды «*5», m3 = счет команды «*3», m45 = счет команды «+45»

def f(x, y, m5 = 0, m3 =0, m45 = 0): if x

return f(x * 5, y, m5 + 1, m3, m45) + f(x * 3, y, m5, m3 + 1, m45) + f(x + 45, y, m5, m3, m45 + 1)

else :

return x == y and m5 and m3 = 2 and m45

== 5

print(f(1,2970))

= y: return x == y and m5 and m3 = 2 and m45 == 5 return f(x*5,y,m5+1,m3,m45) + f(x*3, y,m5,m3+1,m45) + f(x + 45, y, m5, m3, m45 + 1) print(f(1, 2970, 0, 0, 0)) " width="640"

2 способ:

def f(x, y, m5, m3, m45):

if x = y:

return x == y and m5 and m3 = 2 and m45 == 5

return f(x*5,y,m5+1,m3,m45) + f(x*3, y,m5,m3+1,m45) +

f(x + 45, y, m5, m3, m45 + 1)

print(f(1, 2970, 0, 0, 0))

(№ 4039)

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

• Прибавь 3

• Умножь на 2 и прибавь 1

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

(№ 5544) (М. Шагитов)

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

номера :

• Прибавь 2

• Умножь на 3
• Умножь на 4

Сколько существует различных программ, которые

преобразуют исходное число 1 в число 600, и при этом траектория вычислений (включая начальное число)

содержит три подряд идущих числа, сумма которых кратна 11.

Рекурсия :

Основная программа: