Презентация "Динамическое программирование: задачи на оптимизацию" (КИМ 23 ЕГЭ)

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

ЕГЭ, КИМ 23 учитель МБОУ СОШ с.Тербуны

Болгова Н.А.

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

Умение анализировать ход исполнения алгоритма

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

Уровень B.

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

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

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

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

Пример : A = 3, B = 65.

Ответ: 28711.

y or x // 10 % 10 == 9: return 0 if x return f(x + 1, y)+f(x + 10, y) a = int(input()) b = int(input()) print(f(a,b)) " 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) a = int(input()) b = int(input()) print(f(a,b))

Уровень C.

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

• 1. прибавь 1
• 2. умножь на 2
• 3. умножь на 3

Напишите программу, определяющую количество программ, которые преобразуют исходное число 3 в число 135 , и при этом траектория вычислений содержит число 25 и не содержит чисел 13, 39 ?

• Ответ: 4130.

Урок 2

47

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

1. Прибавь 1

2. Прибавь 3

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

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

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

1. Прибавь 1 2. Прибавь 3 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) (М. Шагитов)

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

1. Прибавь 2

2. Умножь на 3

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) (Е. Джобс)

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

1. Вычти 3

2. Раздели нацело на 2

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

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

K = 34

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

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

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

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

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

Программа:

def f(x, y): ….

k = 0 rezult = 8 for i in range ( 10, 100 ): if f(i, rezult): k += 1 print(k)

K = 34

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

K = 34

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

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

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

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

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

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

K = 1025

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

• Прибавь 2

2. Умножь на 2

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

Сколько существует различных программ с нечётным числом команд , которые преобразуют исходное число 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

2. Умножь на 3

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)

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

1. Прибавь 3

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

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

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

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

• Прибавь 2

2. Умножь на 3

3. Умножь на 4

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

Рекурсия :

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