Задача 22
Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 20 и при этом траектория вычислений содержит число 10?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Все допустимые программы можно разбить на 2 части:
– переход от 1 до 10
– переход от 10 до 20
Составим рекуррентную формулу, по которой будем вычислять KN количество разных программ для получения числа N из начального числа.
Число N могло быть получено одной из двух операций:
– увеличением на 1 числа N-1 (для всех чисел):
– умножением на 2 числа N/2 (только для N, которые делятся на 2)
Для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды.
Решение задачи возможно реализовать двумя вариантами:
1. Записав рекурентные формулы для каждого числа найти количество программ для получения числа 10, затем обнуляем все рассчитанные KN, кроме K10. Вычисляем количество программ для числа 20 - K20.
2. Обозначим через Ka→b количеств возможных программ получения числа b из числа a. Очевидно, что Ka→b=Ka→c*Kc→b для любого c, такого что a < c < b, поэтому K1→20=K1→10*K10→20.
Рассмотрим первый вариант.
Составим рекурентные формулы для каждого числа начиная с 20 и заканчивая 1 (сверху вниз):
Далее вычисляем количество программ (до числа 10), подставляя известные значения в формулы (снизу вверх), :
Далее необходимо обнулить все KN меньше 10 и продолжить вычисления дальше.
Такми образом, количестко программ получения из числа 1 числа 20, при этом траектория вычислений содержит число 10, равно 28.
Рассмотрим второй вариант.
Для расчетов воспользуемся формулой поэтому K1→20=K1→10*K10→20.
Изначально вычислим количество программ (K1→10) получения из числа 1 числа 10 (по аналогии с предыдущим вариантом):
Аналогично вычислим количество программ (K10→20) получения из числа 10 числа 20 (для начального числа 10 количество программ равно 1):
Теперь найдем общее количество программ:
Данная задача также может быть решена при помощи таблицы.
Ответ: 28.
