ЕГЭ 23. Динамическое программирование
Задача 1. (классическая)
У исполнителя Удвоитель две команды, которым присвоены номера:
Программа для Удвоителя - это последовательность команд.
Сколько есть программ, которые число 1 преобразуют в число 25 ?
Начинаем рассматривать задачу с конца. Если число нечётное, то оно может быть получено только с помощью первой команды. Если число чётное, то оно может быть получено с помощью двух команд. Используем табличный метод.
Некоторое число i можно получить только двумя способами: либо c помощью первой команды, либо с помощью второй команды. Тогда количество программ для некоторого числа i будет складываться из двух чисел: количества программ для числа i-3 и количества программ для числа i / 2 (Если i - чётное).
|
Числа |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
+3 |
- |
- |
- |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
*2 |
- |
1 |
- |
2 |
- |
3 |
- |
4 |
- |
5 |
|
Кол-во |
1 |
1 |
0 |
2 |
1 |
0 |
2 |
3 |
0 |
3 |
|
Числа |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
|
+3 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
|
*2 |
- |
6 |
- |
7 |
- |
8 |
- |
9 |
- |
10 |
- |
11 |
- |
12 |
- |
|
Кол. |
3 |
0 |
3 |
5 |
0 |
6 |
5 |
0 |
6 |
8 |
0 |
9 |
8 |
0 |
9 |
В первой строке пишутся числа от 1 до 25 (до того числа, которое нужно получить).
Во второй строке пишутся числа, которые в сумме с 3 (тройкой) дают числа, написанные в первой строке. (Прим. начиная с 4, числа идут по порядку.)
В третьей строке пишутся числа, которые при умножении на 2 дают числа, написанные в первой строке. (Прим. числа так же идут по порядку через одну пустую ячейку.)
В четвёртой строке для единицы ставим 1. Для остальных ячеек: смотрим, какие числа участвуют во второй и третьей строке для конкретной ячейки. Затем, эти числа ищем в первой строке и пишем сумму количеств программ для этих чисел (Т.е. пишем сумму уже известных значений из четвёртой строки для этих чисел).
Таким образом, основная идея 23 задания из ЕГЭ по информатике заключается в том, что результат каждого шага опирается на результаты предыдущих шагов!
Ответ: 9