Шешімі: Подсчёт программ исполнителя
Исполнитель Аллегро преобразует число на экране. Команды исполнителя: прибавить 1, прибавить 2, умножить на 3. Программа представляет собой последовательность команд. Траектория вычислений — последовательность результатов выполнения всех команд программы. Сколько существует программ, которые при исходном числе 4 получают результат 22, содержат в траектории число 10 и не содержат число 20?
Шешімін қадамдап көрсету
5 қадамОбозначим через $f(n)$ число программ, переводящих число 4 в число $n$. Для каждого числа учитываем последние команды: прибавление 1, прибавление 2 и умножение на 3.
$$f(n)=f(n-1)+f(n-2)+f(n/3), если n делится на 3$$Число программ, переводящих 4 в 10, равно 13.
После достижения 10 умножение на 3 сразу даёт число больше 22, поэтому до 22 используются только команды прибавить 1 и прибавить 2. Число путей из 10 в 22 равно числу последовательностей шагов 1 и 2: $233$.
Из них нужно исключить пути, проходящие через 20. Число путей из 10 в 20 равно $89$, а из 20 в 22 — $2$, поэтому таких путей $89 \cdot 2=178$.
Искомое число программ равно произведению числа путей до 10 и числа допустимых путей после 10.
$$13\cdot(233-178)=13\cdot55=715$$Где здесь ошибаются
Не исключают программы, траектория которых содержит число 20.
Считают программы, достигающие 22 без обязательного прохождения через 10.
Забывают, что траектория содержит результаты после выполнения команд, а не исходное число.