Шешімі: Программы с траекторией через 9
Исполнитель преобразует число на экране. Команда 1 уменьшает число на 1, команда 2 заменяет число на целую часть от деления числа на 2. Сколько существует программ, для которых при исходном числе 30 результатом является число 1, а траектория вычислений содержит число 9? Траектория вычислений программы — последовательность результатов выполнения всех команд.
Шешім по шагам
4 қадамТак как обе команды уменьшают число, любая программа, траектория которой содержит 9, однозначно разбивается на путь от 30 до 9 и путь от 9 до 1.
Обозначим через $f(n)$ число программ перехода из $n$ в 9. Для $n>9$ выполняется рекуррентное соотношение $f(n)=f(n-1)+f(\lfloor n/2\rfloor)$, а $f(9)=1$. Последовательное вычисление даёт $f(30)=14$.
$$f(30)=14$$Обозначим через $g(n)$ число программ перехода из $n$ в 1. Для $n>1$: $g(n)=g(n-1)+g(\lfloor n/2\rfloor)$, $g(1)=1$. Получаем $g(9)=23$.
$$g(9)=23$$Общее число программ равно произведению числа способов добраться до 9 и числа способов пройти от 9 до 1.
$$14\cdot 23=322$$Где здесь ошибаются
Складывают, а не перемножают количество путей до 9 и после 9.
Используют обычное деление вместо целой части от деления на 2.
Қате считают число программ перехода из 9 в 1.