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

  • Решение (программа на Python): полная программа: TARGET = 4

  • if x < TARGET: если перелет, то

  • def nProg( x, t ): x - текущее число, t - цель (target)

  • Т.к. предпоследняя команда +1, то 22 +1 +1 = 24, (11 +1) *2 = 24

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


    Скачать 0.94 Mb.
    НазваниеДинамическое программирование
    Дата21.11.2022
    Размер0.94 Mb.
    Формат файлаdoc
    Имя файлаege23 (2).doc
    ТипРешение
    #803927
    страница4 из 13
    1   2   3   4   5   6   7   8   9   ...   13

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


    Р-06. У исполнителя Удвоитель две команды, которым присвоены номера:

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

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

    Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Удвоитель – это последовательность команд. Сколько существует программ, преобразующих число 4 в число 24, предпоследней командой которых является команда «1»?

    Решение:

    1. итак, мы знаем предпоследнюю команду – 1, при этом последняя команда может быть любая – 1 или 2

    2. выходит, что нужно получить количество всех программ вида «*11» и «*12», где звёздочка обозначает любые команды

    3. если программа заканчивается на «11», то до выполнения цепочки «11» у нас было число

    24 – 1 – 1 = 22; поэтому нужно найти число программ для преобразования 4 в 22

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

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

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

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

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

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

    для чётных чисел, таких, что N/2  4

    1. составляем таблицу:

      N

      4

      5

      6

      7

      8

      9

      10

      11

      12

      13

      14

      15

      16

      17

      18

      19

      20

      21

      22



      1

      1

      1

      1

      2

      2

      3

      3

      4

      4

      5

      5

      7

      7

      9

      9

      12

      12

      15

    2. теперь рассматриваем случай, когда программа заканчивается на «12», это значит, что до выполнения цепочки «12» у нас было число (24/ 2) – 1 = 11; поэтому нужно найти число программ для преобразования 4 в 11, берём его из таблицы: 3

    3. ответ к задаче – сумма двух значений, выделенных жёлтым маркером: 15 + 3 = 18, поскольку мы рассмотрели все варианты программ, в которых предпоследняя команда – 1

    4. Ответ: 18.

    Решение (программа на Python):

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

    TARGET = 4

    def nProg( x ):

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

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

    if x < TARGET: # если перелет, то

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

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

    n = nProg( x - 1 )

    if x % 2 == 0:

    n += nProg( x // 2 )

    return n

    START = 24

    print( nProg( START//2-1 ) + nProg( START-1-1 ) )

    1. Ответ: 18.

    Решение (ещё один варианты программы на Python, Б.С. Михлин):

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

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

    if x == t:

    return 1

    if x > t:

    return 0

    # x < t - строим дерево:

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

    # Т.к. предпоследняя команда +1, то 22 +1 +1 = 24, (11 +1) *2 = 24

    print( nProg( 4, 22 ) + nProg( 4, 11 ) )

    1. Ответ: 18.
    1   2   3   4   5   6   7   8   9   ...   13


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