На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: Rust
  
> ЕГЭ по информатике 2020, часть 1, № 22, динамическое программирование
    ЕГЭ по информатике 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)).

    K(1)K(2)K(3)K(4)K(5)K(6)K(7)K(8)K(9)K(10)
    123581321345589

    Итого 89 способов подняться на 10-ю ступеньку, на каждом шаге добавляя либо +1, либо +2 ступеньки.
    Сообщение отредактировано: swf -
      Решение.
      Вначале разберёмся с командой умножения на 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.

      Поэтому таблица выглядит так:
      K(4)K(5)K(6)K(7)K(8)K(9)
      1235813

      Итого 1 + 13 = 14 способов получения числа 9.

      Подзадача 2, получение числа 14 из числа 9
      Пусть мы уже находимся на 9-й ступеньке, неважно, как мы туда попали.
      К слову, это очень важное свойство нашей задачи! Нам не нужно помнить, как мы попали в текущее состояние. Если бы это было не так (система имела последействие), то задачу нельзя было бы решать методом динамического программирования.
      K(i) = K(i–2) + K(i–1), i >= 12.
      K(10) = 1, K(11) = 2.

      Таблица:

      K(10)K(11)K(12)K(13)K(14)
      12358

      Итого 8 способов набрать 14, начиная с 9 и используя команды +1 и +2.

      Теперь соединяем решения обеих подзадач в одно: с 3-й ступеньки попасть на 9-ю можно 14 способами, с 9-й ступеньки подняться на 14-ю можно 8 способами.
      Итого 14 * 8 = 112 способов (программ).

      Ответ: 112 .
      Сообщение отредактировано: swf -
      1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
      0 пользователей:


      Рейтинг@Mail.ru
      [ Script execution time: 0,0199 ]   [ 14 queries used ]   [ Generated: 28.07.21, 22:23 GMT ]