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

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

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

  • Решение (программа на Python, Б.С. Михлин): полная программа: Функция подсчета количества цепочек команд (программ).

  • x - текущее число, t - цель (target). def nProg( x, t ): if x == t: если цель достигнута, то

  • x return nProg( x+1, t ) + nProg( x*2, t ) print( nProg( 1, 10 ) * nProg( 10, 21 ) )

  • фыфы. Динамическое программирование


    Скачать 0.85 Mb.
    НазваниеДинамическое программирование
    Дата12.10.2021
    Размер0.85 Mb.
    Формат файлаdoc
    Имя файлаege23.doc
    ТипРешение
    #245984
    страница5 из 11
    1   2   3   4   5   6   7   8   9   10   11

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


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

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

    2. Умножить на 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);

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

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

    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.

    Решение (вариант 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.

    Решение (программа на Python, Б.С. Михлин):

    1. полная программа:

    # Функция подсчета количества цепочек команд (программ).

    # x - текущее число, t - цель (target).

    def nProg( x, t ):

    if x == t: # если цель достигнута, то

    return 1 # завершить функцию, посчитав цепочку (программу)

    if x > t: # если перелет, то

    return 0 # завершить функцию, не считая цепочку

    # x < t - продолжаем строить дерево:

    return nProg( x+1, t ) + nProg( x*2, t )

    print( nProg( 1, 10 ) * nProg( 10, 21 ) )

    1. Ответ: 28.
    1   2   3   4   5   6   7   8   9   10   11


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