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

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

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

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

Результат : 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

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

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

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

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

и перемножаем: 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:

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

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

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

Ответ: 13.