Решение: Подсчёт программ по траектории
Исполнитель Вычислитель преобразует число, записанное на экране. Команды исполнителя: прибавить 1, прибавить 2 и умножить на 2. Сколько существует программ, которые исходное число 4 преобразуют в число 15, если траектория вычислений программы содержит число 11? Траектория вычислений — это последовательность результатов выполнения всех команд программы.
Решение по шагам
5 шаговОбозначим через $f(n)$ количество программ, переводящих число 4 в число $n$. Для перехода в $n$ последней могла быть команда прибавления 1, прибавления 2 или умножения на 2.
$$f(n)=f(n-1)+f(n-2)+f(n/2)$$Последнее слагаемое учитывается только для чётных $n$. Получаем значения до числа 11:
$$f(4)=1,\ f(5)=1,\ f(6)=2,\ f(7)=3,\ f(8)=6,\ f(9)=9,\ f(10)=16,\ f(11)=25$$Значит, существует 25 программ, переводящих 4 в 11.
Теперь считаем количество программ от 11 до 15. Аналогично:
$$g(11)=1,\ g(12)=1,\ g(13)=2,\ g(14)=3,\ g(15)=5$$Любая программа, проходящая через 11, состоит из программы из 4 в 11 и программы из 11 в 15. Поэтому количества перемножаются.
$$25\cdot 5=125$$Где здесь ошибаются
Не разделяют программу на две части в точке прохождения через число 11.
Складывают количества программ вместо их перемножения.
Не учитывают команду умножения на 2 при подсчёте переходов в чётные числа.