| Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.RU > ПОМОЩЬ ШКОЛЬНИКАМ > ЕГЭ по информатике 2020, часть 1, № 22 |
| Автор: swf 21.07.20, 17:38 | ||||||||||||||||||||
| ЕГЭ по информатике 2020, вариант Москва Часть 1, № 22 Динамическое программирование Задание взято с сайта http://kotolis.ru/realegeinf_2020 № 22 Условие. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на З 3. Прибавить 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 3, третья увеличивает на 2. Сколько существует программ, которые преобразуют исходное число 3 в число 14 и при этом траектория вычислении содержит число 9? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 10,30. ------------------------------------- Во первых строках хочу сказать: Господа школьники (репетиторы и прочие заинтересованные лица)! Читайте лекции Котова по динамическому программированию для школьников. Они есть в интернете, есть на этом форуме (в разделе Алгоритмы), вот они на яндекс-диске: https://yadi.sk/i/dfL27HNQZhLiaw Далее всё изложение будет идти согласно этой прекрасной книге. По сути, возьмём решение Примера 1 на стр. 6 (задача про лестницу) и приспособим его к задаче №22. Пример #1. Определить, сколькими различными способами можно подняться на 10-ю ступеньку лестницы, если за один шаг можно подниматься на следующую ступеньку или через одну. Пусть K(10)- количество способов подъема на 10 ступеньку. Определим подзадачу K(i) нашей задачи, как количество способов подъема на i-ю ступеньку. Исходя из условия задачи, на 10 ступеньку можно подняться непосредственно с 8-й и 9-й ступенек. Поэтому, если мы знаем количество способов подъема K(8) и K(9) на 8 и 9 ступеньки соответственно, то количество способов подъема на 10 ступеньку может быть определено как K(10) = K(8) + K(9). Аналогичное соотношение справедливо для любой ступеньки i, начиная с третьей, т.е. K(i) = K(i - 2) + K(i - 1). Осталось определить значения K(1) и K(2), которые равны: K(1) = 1, K(2) = 2. Следовательно, для решения задачи достаточно одномерной таблицы с 10 - ю элементами, для которой необходимо последовательно вычислить значения элементов таблицы согласно приведенным выше рекуррентным соотношениям. Сделаем это посредством последовательных вычислений. K[1] := 1; K[2] := 2; For i := 3 to 10 do K[i] := K[i - 1] + K[i - 2] Протрассируем предложенный алгоритм, вычисляя элементы одномерного массива. Способ подняться на первую ступеньку - один (K(1) = 1), способов подняться на вторую ступеньку - 2 (K(2) = 2). Каждый элемент массива, начиная с третьего, получается как сумма двух предыдущих элементов (K(i) = K(i - 2) + K(i - 1)).
Итого 89 способов подняться на 10-ю ступеньку, на каждом шаге добавляя либо +1, либо +2 ступеньки. |
| Автор: swf 21.07.20, 19:44 | ||||||||||||||||||||||
| Решение. Вначале разберёмся с командой умножения на 3, которой не было в задаче про лестницу. Её можно применить ровно один раз – получить 9 из 3. 3 * 4 = 12, перескакиваем через число 9, которое должно присутствовать в траектории. Запомним, что 9 можно получить из 3 1 способом с помощью команды 2. Получили задачу получения 14 из 3 с помощью команд +1 и +2, и чтобы в траектории была 9. Разделим эту задачу на две подзадачи. Подзадача 1, получение числа 9 из числа 3 Задача совершенно аналогична задаче про лестницу. Только там мы начинали с пола (0-й ступеньки), а здесь начинаем с 3-й ступеньки. K(i) = K(i–2) + K(i–1), i >= 6. K(4) = 1, K(5) = 2. Поэтому таблица выглядит так:
Итого 1 + 13 = 14 способов получения числа 9. Подзадача 2, получение числа 14 из числа 9 Пусть мы уже находимся на 9-й ступеньке, неважно, как мы туда попали. К слову, это очень важное свойство нашей задачи! Нам не нужно помнить, как мы попали в текущее состояние. Если бы это было не так (система имела последействие), то задачу нельзя было бы решать методом динамического программирования. K(i) = K(i–2) + K(i–1), i >= 12. K(10) = 1, K(11) = 2. Таблица:
Итого 8 способов набрать 14, начиная с 9 и используя команды +1 и +2. Теперь соединяем решения обеих подзадач в одно: с 3-й ступеньки попасть на 9-ю можно 14 способами, с 9-й ступеньки подняться на 14-ю можно 8 способами. Итого 14 * 8 = 112 способов (программ). Ответ: 112 . |