Шешімі: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть две команды: 1) уменьшить число на 1; 2) заменить число на целую часть от деления числа на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 30 результатом является число 1, и при этом траектория вычислений содержит число 13? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 122 при исходном числе 10 траектория состоит из чисел 9, 4, 2.
Шешімін қадамдап көрсету
4 қадамТак как обе команды уменьшают число, траектория может содержать число 13 не более одного раза. Поэтому программы можно однозначно разделить на часть от 30 до 13 и часть от 13 до 1.
Подсчитаем количество способов попасть из 30 в 13. Возможны последовательные вычитания, а также переходы делением на 2 из чисел 30, 29, 28, 27 и 26. Динамическим подсчётом получаем 6 способов.
$$N_{30\to13}=6$$Пусть $f(n)$ — количество программ, переводящих число $n$ в 1. Тогда $f(1)=1$, а для $n>1$ выполняется рекуррентное соотношение $f(n)=f(n-1)+f(\lfloor n/2\rfloor)$.
$$f(13)=57$$Перемножаем количество нұсқа для двух независимых частей программы.
$$6\cdot57=342$$Где здесь ошибаются
Не учитывать переходы делением на 2 из чисел 26 и 27 в число 13.
Считать только одну последовательность команд и не использовать динамический подсчёт.
Сложить, а не перемножить количество способов для частей траектории до 13 и после 13.