Заметим, что каждая программа может быть представлена последовательностью цифр, где каждая цифра может быть либо “1”, либо “2”. Длина программы равна количеству команд исполнителя.
Пусть исходное число равно N. Тогда в каждой программе возможно две команды, либо прибавить 1, либо приписать 3. Если выбрана первая команда, число увеличится на 1, станет равным N+1. Если выбрана вторая команда, число увеличится в 10 раз и прибавится 3, станет равным 10N+3.
Теперь рассмотрим, как получить число N+1, исходя из чисел N и 10N+3. Мы можем либо выбрать первую команду для числа N, либо выбрать вторую команду для числа 10N+3 и тогда получить число N+1. Получается, чтобы получить число N+1, у нас есть два возможных варианта: 1) увеличить число N на 1 2) увеличить число 10N+3 на 1 и затем удалить последнюю цифру То есть, чтобы получить число N+1, нам нужно знать количество программ, преобразующих числа N и 10N+1 (которые являются числами, равными N+1).
Итак, пусть f(N) – количество программ, преобразующих число N. Тогда мы можем записать рекуррентное соотношение: f(N+1) = f(N) + f(10N+1).
Для начальных условий, если N=1, то f(1) = 1(программа “1”), а если N=3, то f(3) = 1(программа “212”).
Теперь мы можем использовать это рекуррентное соотношение для вычисления количества программ, преобразующих исходное число N.
Шаги решения:
1) Инициализировать значения f(1) = 1 и f(3) = 1.
2) Используя рекуррентное соотношение f(N+1) = f(N) + f(10N+1), последовательно вычислить значения f(N), где N возрастает от 4 до искомого исходного числа.
3) Вывести значение f(N).