Шешімі: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У него есть две команды: 1) «Вычти 1» — уменьшает число на 1; 2) «Найди целую часть от деления на 2» — заменяет число целой частью от деления на 2. Программа является последовательностью команд. Сколько существует программ, для которых при исходном числе 30 результатом является число 1, если траектория вычислений содержит число 10? Траектория вычислений — последовательность результатов выполнения всех команд.
Шешімін қадамдап көрсету
4 қадамЧтобы траектория содержала число 10, программа состоит из пути от 30 до 10 и пути от 10 до 1. Эти части можно комбинировать независимо.
Обозначим через $f(n)$ число способов попасть из $n$ в 10. Используем рекуррентное соотношение $f(n)=f(n-1)+f(\lfloor n/2 \rfloor)$ и получаем $f(30)=12$.
Обозначим через $g(n)$ число способов попасть из $n$ в 1. По формуле $g(n)=g(n-1)+g(\lfloor n/2 \rfloor)$ получаем $g(10)=30$.
Перемножаем количество нұсқа двух независимых частей программы.
$$12 \cdot 30 = 360$$Где здесь ошибаются
Не учитывать, что число 10 должно встретиться именно в траектории.
Сложить, а не перемножить количество программ для двух частей пути.
Посчитать одинаковые последовательности команд как одну программу.