Top.Mail.Ru
Персональный сайт учителя информатики Звездиной Веры Алексеевны

Понятная информатика,

или Давайте учиться дружно!

Смотреть презентацию
Смотреть презентацию
Смотреть презентацию
Смотреть презентацию
Смотреть презентацию
Читать
Смотреть и скачать
Скачать презентацию

Динамическое программирование (рекуррентные соотношения)

(теория к урокам и ЕГЭ, задание 22).

Динамическое программирование – это способ или техника решения сложных задач путем приведения их к более простым подзадачам того же типа.

Динамическое программирование позволяет решать задачи, которые требуют полного перебора вариантов. Задание может звучать так:

  • «подсчитайте количество способов…»;

  • «как оптимально распределить…»;

  • «найдите оптимальный маршрут…».

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

 

Пример 1.

1.  У исполнителя Калькулятор две команды, которым присвоены номера:

     1. прибавь 1

     2. умножь на 4

Сколько есть программ, которые число 1 преобразуют в число 55?

Решение.

Обозначим через N текущее (получаемое) число, а через K(N) – количество различных программ для получения этого числа.

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

-  увеличением на 1 числа N-1 (предыдущего числа);

-  умножением на 4 числа N/4 (только для N, которые делятся на 4).

Тогда получаем следующие рекуррентные формулы:

K(N)= K(N-1)              -   для чисел, не кратных 4;

K(N) =K(N-1) +K(N/4) - для чисел, кратных 4.

Заполним таблицу получения чисел от 1 до 55, указывая в ней только кратные 4 числа, так как числа, лежащие в промежутке между ними всегда равны предыдущему значению для кратного числа:

Здесь при  N = 4 получаем K4=К3+К4/4= К3+К1=1+1=2;

                    N = 8 получаем K8=К7+К4/2= К4+К2 =2+1=3, и так далее.

А если посмотреть внимательно, то можно и сделать еще быстрее: так как числа кратны 4, то каждое увеличение выполняется по 4 раза (13 1, по 2, по 3…)

Ответ: 32

 

Пример 2.

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

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

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

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

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

Решение.

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

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

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

K(N) = K(N-1)    - для нечётных чисел

K(N) = K(N-1) + К(N/2) - для чётных чисел

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

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

Второй этап – определяем таким же образом (и по таким же формулам!), сколько есть способов получить конечное число 21 из 10, только левую часть таблицы (от 1 до 10) мы уже не рассматриваем:

На втором этапе можно использовать и такую идею: если мы знаем количество команд, с помощью которых из начального числа 1 можно получить 10 и определим количество команд, с помощью которых из 10 можно получить конечное значение 21, останется только перемножить эти два числа – это и будет ответ

Составляем таблицу для получения 21 из 10, используя те же рекуррентные формулы:

gallery/задание 22 - 2-0,8
gallery/задание 22 - 3-0,8
gallery/задание 22 - 4-0,8
gallery/задание 22 - 1

Результат : 14 * 2 = 28

Ответ: 28.

 

Пример 3.

Исполнитель М17 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

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

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

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

Первая команда увеличивает число на экране на 1, вторая – увеличивает его на 2, а третья – умножает его на 3. Программа для исполнителя М17 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 12 и при этом траектория вычислений содержит числа 8 и 10?

Решение.

Запишем рекуррентную формулу для вычисления K(N) – количества возможных программ для получения числа N из некоторого начального числа:

                  K(N) = K(N-1) +К(N-2),               если N не делится на 3

                  K(N) = K(N-1) +К(N-2) +К(N/3), если N делится на 3

 

Все допустимые программы можно разбить на 3 части:

– переход от 2 до 8

– переход от 8 до 10

– переход от 10 до 12

gallery/задание 22 - 5-0,8

Обозначим через К(a->b) количество возможных программ получения числа b из числа a

Очевидно, что  К(a->b) = К(a->c) * К(c->b) для любого c, такого что a < c < b

Поэтому К(2->12) = К(2->8) * К(8->10) * К(10->12)

Вычисляем эти значения отдельно стандартным способом по рекуррентным формулам п. 1:

gallery/задание 22 - 6

и перемножаем: 15 × 2 × 2 = 60

Ответ: 60.

 

Пример 4.

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

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

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

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

Решение.

В этом задании две особые точки – числа 14 (через которое должна проходить траектория) и 25 (а сюда она попасть НЕ должна)

Сначала, так же, как и в задачах, рассмотренных выше, составляем рекуррентную формулу, по которой будем вычислять количество K(N) обозначить количество разных программ для получения числа N из начального числа:

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

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

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

K(N) = K(N-1) -  для нечётных чисел

K(N) = K(N-1) + К(N/2) -  для чётных чисел

Для начального числа 2 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; K(1) = 1.

Составляем таблицу до первой особой точки – числа 14:

gallery/задание 22 - 7-0,8

Поскольку число 14 должно обязательно войти в траекторию, начинаем составлять вторую часть таблицы (до второй контрольной точки, 25) с этого числа заново, считая, что все ячейки для меньших чисел – нулевые

gallery/задание 22 - 8-0,8

Поскольку траектория не может проходить через 25, для N = 25 принимаем K(N) = 0 (в таблице эта ячейка выделена красным цветом)

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

gallery/задание 22 - 9-0,8

Ответ: 13.

© 2018–2019    Звездина Вера Алексеевна, v_zvezdina@mail.ru

SSL