Задание 22 (презентация по типам задач к ЕГЭ)

Ege 22 ( повышенный уровень , время – 7 мин )

Тема: динамическое программирование

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

Что нужно знать :

• динамическое программирование – это способ решения сложных задач путем сведения их к более простым задачам того же типа

• с помощью динамического программирования решаются задачи, которые требуют полного перебора вариантов:

• «подсчитайте количество вариантов…» «как оптимально распределить…» «найдите оптимальный маршрут…»
• «подсчитайте количество вариантов…»
• «как оптимально распределить…»
• «найдите оптимальный маршрут…»

• динамическое программирование позволяет ускорить выполнение программы за счет использования дополнительной памяти; полный перебор не требуется, поскольку запоминаются решения всех задач с меньшими значениями параметров

Пример I:

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

1. прибавь 1

2. умножь на 3

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

Программа для Утроителя – это последовательность команд.

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

Решение

1. Для чисел 1 и 2, меньших, чем 3 , существует только 1 программа, состоящая только из команд сложения

2. Если число N не делится на 3 , то оно могло быть получено только

последней операцией сложения, поэтому

3. Для получения количества программ будем использовать рекуррентные формулы

если N не делится на 3

если N делится на 3

4. Заполним таблицу для всех значений от 1 до N:

если N не делится на 3

если N делится на 3

N

1

1

2

1

3

2

4

2

5

2

6

3

7

3

8

3

9

5

10

11

5

5

12

13

7

7

14

15

7

9

16

9

17

9

18

12

19

12

20

12

5. Видно, что количество вариантов меняется только в тех столбцах, где N делится на 3 , поэтому из всей таблицы можно оставить только эти столбцы:

N

1

1

3

2

6

3

9

5

12

7

15

9

18

20

12

12

Ответ: 12

21 могло быть получено одной из трёх операций сложения соответственно из чисел N-1 , N-2 и N-4 , поэтому 4. Заполним таблицу для всех значений от 21 до 30: N 21 22 1 1 23 24 2 25 3 26 6 27 10 28 18 31 29 55 30 96 Ответ: 96 " width="640"

Пример II:

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

1. прибавь 1 2. прибавь 2 3. прибавь 4

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

Решение

1. Видно, что при выполнении любой из команд число увеличивается (не может уменьшаться)

2. Все числа, меньше 21 , с помощью этого исполнителя получить нельзя, для них количество программ будет равно 0

3. Любое число N 21 могло быть получено одной из трёх операций сложения соответственно из чисел N-1 , N-2 и N-4 , поэтому

4. Заполним таблицу для всех значений от 21 до 30:

N

21

22

1

1

23

24

2

25

3

26

6

27

10

28

18

31

29

55

30

96

Ответ: 96

Пример III:

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

1. прибавь 1

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

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

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

Решение

при заданных командах очередное число N может быть получено двумя способами:

• увеличением на 1 (для всех чисел, больших начального числа);

• увеличением числа десятков на 1 (то есть, фактически командой «+ 10 ») – для всех чисел, больших или равных 25;

например, число 24 не может быть получено этой командой (14 + 10 = 24), потому что число 14 меньше, чем начальное значение 15

таким образом, рекуррентные формулы принимают вид

для всех чисел, меньших, чем 25

для чисел, больших или равных 25

15

16

1

17

1

1

18

19

1

20

1

21

1

22

1

23

1

1

24

25

1

26

2

27

3

28

4

5

Ответ: 5

Пример IV:

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

1. прибавь 1

2. увеличь две младшие цифры на 1

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

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

Решение

при заданных командах очередное число N может быть получено двумя способами:

• увеличением на 1 (для всех чисел, больших начального числа)

• увеличением обеих цифр на 1 в результате выполнения команды 2 (то есть, фактически командой «+11») – для всех чисел, больших или равных 23 + 11 = 34 , которые НЕ оканчиваются на 0 ;

• увеличением только младшей цифры на 1 в результате выполнения команды 2 (то есть, фактически командой «+1») – для всех чисел от 91 до 99 , но в нашем диапазоне ( 23 … 48 ) таких нет

• увеличением только старшей цифры на 1 в результате выполнения команды 2 (то есть, фактически командой «+10») – для всех чисел, больших 34 и имеющих 9 на конце; в нашем случае под этот вариант подходит только число 39

Тогда рекуррентные формулы принимают вид:

для всех чисел, меньших, чем 34 , а также для всех чисел, оканчивающихся на 0

для чисел, больших или равных 34 , кроме 39

Ответ: 26

для числа 39

далее заполняем таблицу:

N

23

K N

…

1

…

33

34

1

2

35

36

3

37

4

38

5

6

39

8

40

8

41

9

42

10

43

11

44

12

45

14

46

17

47

21

48

26

Пример V:

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

1. прибавь 1 2. прибавь 2 3. прибавь следующее

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

Решение

число N могло быть получено одной из трёх операций сложения:

• увеличением на 1 числа N-1;

• увеличением на 2 числа N-2;

• из некоторого числа X увеличением на X+1 (следующее число),

так что N = X + X + 1, откуда X = (N – 1) / 2;

а так могут быть получены только нечетные числа; поэтому

для нечётных чисел

для чётных чисел

для чётных чисел

для нечётных чисел

заполним таблицу для всех значений от 2 до 10

N

2

1

3

1

4

2

5

6

4

6

7

8

11

17

9

30

10

47

Ответ: 47

Пример VI:

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

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

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

Решение:

• число N могло быть получено одной из двух операций:

1). увеличением на 1 числа N-1;

2). умножением на 2 числа N/2 (только для N, которые делятся на 2);

для нечётных чисел

для чётных чисел

существует только одна пустая программа , не содержащая ни одной команды

• поскольку траектория должна проходить через число 10 , сначала выясняем, сколькими способами можно получить 10 из 1 , а затем будем считать, сколько есть способов получить 21 из 10

для нечётных чисел

для чётных чисел

N

1

2

1

3

2

4

2

5

4

4

6

7

6

8

6

9

10

10

10

14

второй этап – определяем таким же образом (и по таким же формулам!), сколько есть способов получить конечное число 21 из 10 , только левую часть таблицы (от 1 до 10) мы уже не рассматриваем:

N

10

11

14

12

14

13

14

14

14

14

15

14

16

17

14

14

18

19

14

14

20

28

21

28

Ответ: 28

Пример VII:

Вариант 1

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

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

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

Решение

• в задании две особые точки – числа 14 (через которое должна проходить траектория) и 25 (куда она попасть НЕ должна)

• составим рекуррентную формулу, по которой будем вычислять количество разных программ для получения числа N из начального числа :

число N могло быть получено одной из двух операций:

• увеличением на 1 числа N-1
• умножением на 2 числа N/2 (только для N, которые делятся на 2)

для начального числа 2 количество программ равно 1 (существует только одна пустая программа, не содержащая ни одной команды)

для нечётных чисел

Ответ: 13

для чётных чисел

3. составляем таблицу до первой особой точки – числа 14 :

N

2

1

3

4

1

2

5

2

6

3

7

3

8

5

9

5

10

7

11

7

12

10

13

10

14

13

4. заполняем вторую часть таблицы (до второй контрольной точки, 25 ) с этого числа заново, считая, что все ячейки для меньших чисел – нулевые

N

14

13

15

13

16

13

17

13

18

13

19

13

20

13

21

13

22

23

13

24

13

13

25

0

26

27

28

29

5. поскольку траектория не может проходить через 25 , для N = 25 принимаем K N = 0

6. дальше заполняем оставшиеся ячейки второй части таблицы обычным способом

Ответ: 13

N

14

13

15

13

16

13

17

18

13

19

13

13

20

13

21

22

13

13

23

13

24

13

25

0

26

0

27

0

28

13

29

13

Пример VIII:

Вариант 3

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

1. Прибавить 1 (увеличивает число на экране на 1)

2. Умножить на 2 (умножает его на 2)

Программа для исполнителя Удвоитель – это последовательность команд. Сколько существует программ , преобразующих число 4 в число 24 , предпоследней командой которых является команда « 1 » ?

Решение:

• По условию, предпоследняя команда должна быть № 1, при этом последняя команда может быть любая – №1 или №2. Т.е. нужно получить количество всех программ вида « *11 » и « *12 », где звёздочка обозначает любые команды

2. если программа заканчивается на « 11 », то до выполнения цепочки « 11 » было число 24 – 1 – 1 = 22 ; поэтому нужно найти число программ для преобразования 4 в 22

для нечётных чисел

для чётных чисел, таких, что N/2  4

3. заполняем таблицу:

для нечётных чисел

для чётных чисел, таких, что N/2  4

N

4

5

1

6

1

7

1

8

1

9

2

10

2

11

3

12

3

4

13

14

4

15

5

16

5

17

7

18

7

9

19

20

9

12

21

22

12

15

4. теперь рассматриваем случай, когда программа заканчивается на « 12 », это значит, что до выполнения цепочки « 12 » у нас было число ( 24/ 2) – 1 = 11 ; поэтому нужно найти число программ для преобразования 4 в 11 , берём его из таблицы: 3

5. ответ к задаче – сумма двух значений, выделенных жёлтым маркером: 15 + 3 = 18 , поскольку мы рассмотрели все варианты программ, в которых предпоследняя команда №1

Ответ: 18

ДЕМО-2017:

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

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

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

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

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

Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает его на 2.

Программа для исполнителя А16 – это последовательность команд.

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

преобразуют в число 12 и при этом траектория вычислений программы содержит число 10 ?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.

Например , для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.

для нечётных чисел

для чётных чисел

N

3

K N

4

1

1

5

2

6

4

7

6

8

11

9

17

10

30

11

12

30

60

Ответ: 60