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

Динамическое программирование: задачи оптимизации

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

Болгова Н.А.

(№ 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))

(№ 4498) (М. Шагитов, КЕГЭ)

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

• Умножь на 5

2. Умножь на 3

3. Прибавь 45

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

=2, - счет команды «*3», m45 =5 ,_- счет команды «+45» def f(x, y, m5, m3, m45): print(f (1, 2970, 0, 0, 0)) " width="640"

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

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

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

=2, - счет команды «*3», m45 =5 ,_- счет команды «+45» def f(x, y, m5, m3, m45): if x = y: return x = = y and m5 and m3 = 2 and m45 == 5 print(f (1, 2970, 0, 0, 0)) " width="640"

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

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

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

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

=2, - счет команды «*3», m45 =5 ,_- счет команды «+45» def f(x, y, m5, m3, m45): if x = y: return x = = y and m5 and m3 = 2 and m45 == 5 print(f (1, 2970, 0, 0, 0)) " width="640"

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

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

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

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

=2, - счет команды «*3», m45 =5 ,_- счет команды «+45» 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)) " width="640"

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

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))

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

2 вариант

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 ))

Возможные ошибки!

(№ 4039)

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

1. Прибавь 3

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

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

a = set( ) def f(x, k): # x — число, k — кол-во команд if k == 13: a. add (x) else :

f(2, 0) print ( len (a) )

a = set( ) def f(x, k): # x — число, k — кол-во команд if k == 13: a. add (x) else :

f(x + 3, k + 1) f(x * 2 + 1, k + 1)

f(2, 0) print ( len (a) )

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

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

• Прибавь 2

2. Умножь на 3

3. Умножь на 4

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

Рекурсия :

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

Домашнее задание:

№ 4499 (Уровень: Средний) (ким 23, КЕГЭ)

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

1. Прибавь 3

2. Умножь на 2

3. Умножь на 7

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

ответ 52