Повышенный уровень, время –7 мин)

Повышенный уровень, время –7 мин)

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

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

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

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

o «подсчитайте количество вариантов…»

o «как оптимально распределить…»

o «найдите оптимальный маршрут…»

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

Пример задания:

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

Прибавить 1

Умножить на 2

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

Решение:

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

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

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

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

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

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

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

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

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

N	2	3	4	5	6	7	8	9	10	11	12	13	14
	1	1	2	2	3	3	5	5	7	7	10	10	13

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

N	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29
	13	13	13	13	13	13	13	13	13	13	13	0

7) поскольку траектория не может проходить через 25, для N = 25 принимаем K_N = 0 (в таблице эта ячейка выделена красным цветом)

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

N	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29
	13	13	13	13	13	13	13	13	13	13	13	0	0	0	13	13

9) Ответ: 13.

Ещё пример задания:

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

Прибавить 1

Умножить на 2

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

Решение:

1) итак, мы знаем предпоследнюю команду – 1, при этом последняя команда может быть любая – 1 или 2

2) выходит, что нужно получить количество всех программ вида «*11» и «*12», где звёздочка обозначает любые команды

3) если программа заканчивается на «11», то до выполнения цепочки «11» у нас было число

24 – 1 – 1 = 22; поэтому нужно найти число программ для преобразования 4 в 22

4) для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через  обозначить количество разных программ для получения числа N из начального числа 1, то .

5) теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую  с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N

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

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

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

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

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

7) составляем таблицу:

N	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
	1	1	1	1	2	2	3	3	4	4	5	5	7	7	9	9	12	12	15

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

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

10) Ответ: 18.

Ещё пример задания:

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

Прибавить 1

Умножить на 2

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

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

Решение (вариант 1 ):

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

2) для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через  обозначить количество разных программ для получения числа N из начального числа 1, то .

3) теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую  с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N

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

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

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

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

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

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

6) заполняем таблицу от 1 до 10 по полученным формулам:

N	1	2	3	4	5	6	7	8	9	10
	1	2	2	4	4	6	6	10	1 0	14

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

N	10	11	12	13	14	15	16	17	18	19	20	21
	14	14	14	14	14	14	14	14	14	14	28	28

8) Ответ: 28.

Решение (вариант 2, А.Н. Носкин):

1) первый этап (п. 1-6) такой же, как и в первом варианте (см. выше);

2) на втором этапе используем такую идею: если мы знаем количество команд, с помощью которых из начального числа 1 можно получить 10 и определим количество команд, с помощью которых из 10 можно получить конечное значение 21, останется только перемножить эти два числа – это и будет ответ

3) составляем таблицу для получения 21 из 10, используя те же рекуррентные формулы:

N	10	11	12	13	14	15	16	17	18	19	20	21
	1	1	1	1	1	1	1	1	1	1	2	2

4) результат – 14 ´ 2 = 28

5) Ответ: 28.

Ещё пример задания:

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

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

Прибавь 1

Прибавь 2

Прибавь следующее

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

Прибавь 1

Прибавь 2

Прибавь 4

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

Прибавь 1

Умножь на 3

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

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

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

Прибавь 1

Прибавь 1

Прибавь 1

Умножь на 2

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

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

Прибавь 1

Умножь на 4

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

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

Прибавь 1

Умножь на 2

Умножь на 3

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

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

Прибавь 1

Умножь на 2

Умножь на 4

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

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

Прибавь 1

Умножь на 3

Умножь на 4

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

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

Прибавь 1

Прибавь 2

Умножь на 3

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

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

Прибавь 1

Прибавь 3

Умножь на 2

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

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

Прибавь 1

Прибавь 3

Умножь на 3

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

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

Прибавь 1

Прибавь 3

Умножь на 4

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

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

Прибавь 1

Прибавь 2

Умножь на 4

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

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

Прибавь 1

Умножь на 4

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

12) ( С.Э. Назаренко )  У исполнителя Калькулятор две команды, которым присвоены номера:

Прибавь 2

Умножь на 2

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

13)  ( С.Э. Назаренко ) У исполнителя Калькулятор две команды, которым присвоены номера:

Прибавь 1

Умножь на 3

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

14) ( С.Э. Назаренко ) У исполнителя Калькулятор две команды, которым присвоены номера:

Прибавь 3

Умножь на 3

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

15) ( С.Э. Назаренко ) У исполнителя Калькулятор три команды, которым присвоены номера:

Прибавь 1

Прибавь 3

Умножь на 2

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

16) ( Т.В. Белова ) У исполнителя Калькулятор три команды, которым присвоены номера:

Прибавь 1

Умножь на 2

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

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

17) ( Т.В. Белова ) У исполнителя Калькулятор три команды, которым присвоены номера:

Прибавь 1

Прибавь 3

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

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

18) ( Т.В. Белова ) У исполнителя Калькулятор три команды, которым присвоены номера:

Прибавь 1

Умножь на 2

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

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

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

Прибавь 1

Увеличь число десятков на 1

Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется.

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

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

Прибавь 1

Увеличь число десятков на 1

Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется.

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

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

Прибавь 1

Прибавь 1

Прибавь 1

Прибавь 1

Увеличь число десятков на 1

Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется.

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

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

Прибавь 2

Умножь на 2

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

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

Прибавь 3

Умножь на 2

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

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

Прибавь 1

Прибавь 3

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

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

Прибавь 1

Прибавь 3

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

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

Прибавь 1

Умножь на 2

Умножь на 3

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

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

Прибавь 2

Умножь на 3

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

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

Прибавь 2

Умножь на 3

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

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

Прибавь 1

Умножь на 1, 5

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

в 1, 5 раза, если число чётное. К нечётным числам вторая команда неприменима. Сколько есть программ, которые число 1 преобразуют в число 20?

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

Прибавь 1

Умножь на 1, 5

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

в 1, 5 раза, если число чётное. К нечётным числам вторая команда неприменима. Сколько есть программ, которые число 2 преобразуют в число 22?

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

Прибавь 1

Сделай чётное

Сделай нечётное

Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, третья переводит число x в число 2x + 1. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 2 преобразуют в число 16?

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

Прибавь 1

Сделай чётное

Сделай нечётное

Умножь на 10

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

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

Прибавь 1

Прибавь 2

Прибавь 5

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

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

Прибавь 1

Прибавь 3

Прибавь 6

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

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

Прибавь 2

Прибавь 3

Прибавь 5

Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 20 преобразуют в число 35?

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

Прибавь 1

Прибавь 4

Прибавь 5

Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 30 преобразуют в число 46?

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

Прибавь 2

Прибавь 4

Прибавь 5

Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 31 преобразуют в число 51?

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

Прибавь 1

Прибавь 2

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

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

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

Прибавить 1

Прибавить 2

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

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

Прибавить 1

Прибавить 3

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

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

Прибавить 1

Прибавить 2

Прибавить 3

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

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

Прибавить 1

Умножить на 2

Прибавить 3

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

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

Прибавить 1

Умножить на 2

Умножить на 3

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

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

Прибавь 1

Прибавь 3

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

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

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

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

Прибавь 1

Прибавь 2

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

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

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

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

Прибавь 2

Прибавь 3

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

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

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

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

Прибавь 1

Умножь на 2

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

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

Прибавь 1

Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает это число в 2 раза. Сколько существует программ, которые число 5 преобразуют в число 32 и в которых предпоследняя команда 1?

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

Прибавь 1

Прибавь 2

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

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

Прибавь 1

Прибавь 2

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

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

Прибавить 1

Умножить на 2

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

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

Прибавить 1

Умножить на 2

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

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

Прибавить 1

Умножить на 2

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

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

Прибавить 1

Умножить на 2

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

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

Прибавить 1

Умножить на 2

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

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

Прибавить 1

Умножить на 3

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

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

Прибавить 1

Умножить на 2

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

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

Прибавить 2

Умножить на 3

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

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

Прибавить 1

Умножить на 2

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

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

Прибавить 1

Умножить на 2

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

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

Прибавить 1

Умножить на 2

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

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

Прибавить 1

Прибавить 5

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

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

Прибавить 1

Прибавить 3

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

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

Прибавить 1

Прибавить 3

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

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

Прибавить 1

Умножить на 2

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

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

Прибавить 1

Умножить на 2

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

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

Прибавить 1

Прибавить 2

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

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

Прибавить 1

Прибавить 2

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

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

Прибавить 1

Прибавить 2

Умножить на 2

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

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

Прибавить 1

Прибавить 2

Умножить на 2

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

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

Прибавить 1

Прибавить 2

Умножить на 3

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

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

Прибавить 1

Прибавить 2

Умножить на 2

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

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

Прибавить 1

Прибавить 2

Умножить на 2

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

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

Прибавить 1

Прибавить 2

Умножить на 3

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

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

Прибавить 1

Прибавить 2

Умножить на 3

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

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

Прибавить 1

Умножить на 2

Умножить на 3

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

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

Прибавить 1

Умножить на 2

Умножить на 3

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

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

Прибавить 1

Сделай нечётное

Выполняя первую команду, исполнитель увеличивает число на 1, а выполняя вторую – из числа x получает число 2x + 1. Сколько существует программ, для которых при исходном числе 1 результатом является число 25 и при этом траектория вычислений не содержит число 21?

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

Прибавить 1

Сделай нечётное

Выполняя первую команду, исполнитель увеличивает число на 1, а выполняя вторую – из числа x получает число 2x + 1. Сколько существует программ, для которых при исходном числе 1 результатом является число 31 и при этом траектория вычислений не содержит число 25?

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

Прибавить 1

Прибавить 2

Прибавить 3

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

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

Прибавить 1

Прибавить 2

Прибавить 4

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

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

Прибавить 1

Умножить на 2

Умножить на 3

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

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

Прибавить 1

Умножить на 2

Умножить на 3

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

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

Прибавить 1

Прибавить 2

Умножить на 2

Программа для исполнителя К17 – это последовательность команд. Сколько существует таких программ, которые исходное число 3 преобразуют в число 13 и при этом траектория вычислений программы содержит число 9 и число 11?

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

Прибавить 1

Прибавить 3

Умножить на 2

Программа для исполнителя К17 – это последовательность команд. Сколько существует таких программ, которые исходное число 1 преобразуют в число 13 и при этом траектория вычислений программы содержит число 4 и число 9?

 

[1] Источники заданий:

1. Демонстрационные варианты ЕГЭ 2012-2016 гг.

2. Тренировочные работы МИОО.

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

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

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

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

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

o «подсчитайте количество вариантов…»

o «как оптимально распределить…»

o «найдите оптимальный маршрут…»

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

Пример задания:

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

Прибавить 1

Умножить на 2

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

Решение:

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

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

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

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

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

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

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

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

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

N	2	3	4	5	6	7	8	9	10	11	12	13	14
	1	1	2	2	3	3	5	5	7	7	10	10	13

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

N	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29
	13	13	13	13	13	13	13	13	13	13	13	0

7) поскольку траектория не может проходить через 25, для N = 25 принимаем K_N = 0 (в таблице эта ячейка выделена красным цветом)

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

N	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29
	13	13	13	13	13	13	13	13	13	13	13	0	0	0	13	13

9) Ответ: 13.

Ещё пример задания:

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

Прибавить 1

Умножить на 2

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

Решение:

1) итак, мы знаем предпоследнюю команду – 1, при этом последняя команда может быть любая – 1 или 2

2) выходит, что нужно получить количество всех программ вида «*11» и «*12», где звёздочка обозначает любые команды

3) если программа заканчивается на «11», то до выполнения цепочки «11» у нас было число

24 – 1 – 1 = 22; поэтому нужно найти число программ для преобразования 4 в 22

4) для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через  обозначить количество разных программ для получения числа N из начального числа 1, то .

5) теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую  с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N

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

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

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

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

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

7) составляем таблицу:

N	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
	1	1	1	1	2	2	3	3	4	4	5	5	7	7	9	9	12	12	15

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

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

10) Ответ: 18.

Ещё пример задания:

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

Прибавить 1

Умножить на 2

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

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

Решение (вариант 1 ):

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

2) для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через  обозначить количество разных программ для получения числа N из начального числа 1, то .

3) теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую  с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N

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

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

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

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

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

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

6) заполняем таблицу от 1 до 10 по полученным формулам:

N	1	2	3	4	5	6	7	8	9	10
	1	2	2	4	4	6	6	10	1 0	14

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

N	10	11	12	13	14	15	16	17	18	19	20	21
	14	14	14	14	14	14	14	14	14	14	28	28

8) Ответ: 28.

Решение (вариант 2, А.Н. Носкин):

1) первый этап (п. 1-6) такой же, как и в первом варианте (см. выше);

2) на втором этапе используем такую идею: если мы знаем количество команд, с помощью которых из начального числа 1 можно получить 10 и определим количество команд, с помощью которых из 10 можно получить конечное значение 21, останется только перемножить эти два числа – это и будет ответ

3) составляем таблицу для получения 21 из 10, используя те же рекуррентные формулы:

N	10	11	12	13	14	15	16	17	18	19	20	21
	1	1	1	1	1	1	1	1	1	1	2	2

4) результат – 14 ´ 2 = 28

5) Ответ: 28.

Ещё пример задания:

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

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

Прибавь 1

Прибавь 2

Прибавь следующее

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

12345Следующая ⇒

Поделиться: