Главная страница
Навигация по странице:

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

    		•

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


    Скачать 466.5 Kb.
    НазваниеТема динамическое программирование
    АнкорШпраргалка егэ
    Дата02.03.2023
    Размер466.5 Kb.
    Формат файлаdoc
    Имя файлаege22.doc
    ТипЗадача
    #965635
    страница3 из 6
    1   2   3   4   5   6

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


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

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

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

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

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

    Решение:

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

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

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

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

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

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

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

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

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

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

      N
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10



      1
      2
      2
      4
      4
      6
      6
      10
      10
      14

    3. второй этап – определяем таким же образом (и по таким же формулам!), сколько есть способов получить конечное число 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

    4. Ответ: 28.
    1   2   3   4   5   6

    написать администратору сайта