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

  • 1. прибавь 1 2. прибавь 2 3. прибавь следующее

  • Решение (1 способ, составление таблицы)

  • Решение (программа на Python, Б.С. Михлин): полная программа: t = 10 цель (target)

  • def nProg( x )

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

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


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

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


    Р-04. Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя

    три команды, которым присвоены номера:

    1. прибавь 1

    2. прибавь 2

    3. прибавь следующее

    Первая из них увеличивает число на экране на 1, вторая увеличивает это число на 2, а третья прибавляет к числу на экране число, большее на 1 (к числу 3 прибавляется 4, к числу 9 прибавляется 10 и т. д.). Программа для исполнителя Калькулятор– это последовательность команд. Сколько есть программ, которые число 2 преобразуют в число 10?

    Решение (1 способ, составление таблицы):

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

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

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

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

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

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

    • из некоторого числа X увеличением на X+1 (следующее число), так что N = X + X + 1, откуда X = (N – 1) / 2; так могут быть получены только нечетные числа;

    поэтому

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

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

    1. остается по этой формуле заполнить таблицу для всех значений от 2 до 10:

      N

      2

      3

      4

      5

      6

      7

      8

      9

      10



      1

      1

      2

      4

      6

      11

      17

      30

      47

    2. Ответ:– 47.

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

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

    t = 10 # цель (target)

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

    # x - текущее число.

    def nProg( x ):

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

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

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

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

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

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

    print( nProg( 2 ) )

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


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