Подготовка к ЕГЭ "Динамическое программирование. Исполнитель Калькулятор"
материал для подготовки к егэ (гиа) по информатике и икт (11 класс) на тему

Слайд 1

Слайд 2

Назначение динамическое программирование – это способ решения сложных задач путем сведения их к более простым задачам того же типа с помощью динамического программирования решаются задачи, которые требуют полного перебора вариантов : «подсчитайте количество вариантов…» «как оптимально распределить…» «найдите оптимальный маршрут…»

Слайд 3

Задача У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 2 2. умножь на 3 Сколько есть программ, которые число 1 преобразуют в число 25 ?

Слайд 4

Решение ( 1 способ, составление графа)

Слайд 5

Решение 1 3 5 7 9 11 13 15 17 19 21 23 25 1 2 2 2 4 4 4 6 6 6 8 8 8 Ответ: 8 1. прибавь 2 2. умножь на 3 3=1+2; 3=1*3 Всего 2 пути 5=3+2; а в 3 Всего 2 пути 7=5+2; а в 5 Всего 2 пути 9=7+2; 9=3*3 В 7 два пути + в 3 два пути =4 11=9+2; а в 9 Всего 4 пути 13=11+2; а в 11 Всего 4 пути 15=13+2; 15=5*3 В 13 – 4 пути, в 5 - 2 пути= 6 19=17+2; а в 17 – 6 путей 17=15+2; а в 15 – 6 путей 21=19+2; 21=7*3, В 19 – 6 путей+ в 7 – 2 пути = 8 23=21+2; а в 21 – 8 путей 25=23+2; а в 23 – 8 путей

Слайд 6

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

Слайд 7

Решение ( 2 способ, составление таблицы) заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться) все числа, меньшие начального числа 21, с помощью этого исполнителя получить нельзя, для них количество программ будет равно 0 для начального числа 21 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; теперь рассмотрим общий случай решения любое число N > 21 могло быть получено одной из трёх операций сложения соответственно из чисел N-1, N-2 и N-4, поэтому

Слайд 8

Решение N 2 1 2 2 2 3 2 4 25 2 6 2 7 2 8 2 9 3 0 1 1 2 3 6 10 18 31 5 5 96 1. прибавь 1 2. прибавь 2 3. прибавь 4 Ответ: 96

Слайд 9

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

Слайд 10

Решение N 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 1 2 2 2 3 3 3 5 5 5 7 7 7 9 9 9 12 12 12 N 1 3 6 9 12 15 18 21 1 2 3 5 7 9 12 15 Заметим, что количество вариантов меняется только в тех столбцах, где N делится на 3, поэтому из всей таблицы можно оставить только эти столбцы: заданное число 20 попадает в последний интервал (от 18 до 21), поэтому … ответ – 12.

Слайд 11

Задание 3 У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 1 2. увеличь вторую с конца цифру на 1 Первая из них увеличивает число на экране на 1, вторая – увеличивает на 1 число десятков. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется. Программа для Калькулятора – это последовательность команд. Сколько есть программ, которые число 15 преобразуют в число 28?

Слайд 12

Решение 15 16 17 18 19 20 21 22 23 24 25 26 27 28 1 1 1 1 1 1 1 1 1 1 2 3 4 5 увеличение числа десятков на 1 (то есть, фактически командой «+10») – для всех чисел, больших или равных 25; например, число 24 не может быть получено этой командой (14 + 10 = 24), потому что число 14 меньше, чем начальное значение 15 Ответ: 5

Слайд 13

Решение N 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 1 2 2 2 3 3 3 5 5 5 7 7 7 9 9 9 12 12 12 N 1 3 6 9 12 15 18 21 1 2 3 5 7 9 12 15 Заметим, что количество вариантов меняется только в тех столбцах, где N делится на 3, поэтому из всей таблицы можно оставить только эти столбцы: заданное число 20 попадает в последний интервал (от 18 до 21), поэтому … Ответ – 12.