Шешімі: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть три команды, обозначенные латинскими буквами: A — прибавить 1; B — умножить на 2; C — возвести в квадрат. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 20, при этом траектория вычислений не содержит числа 11? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 4 траектория будет состоять из чисел 16, 32, 33.
Шешім по шагам
4 қадамОбозначим через $f(n)$ количество программ, переводящих число 2 в число $n$ без попадания в 11. Для числа 2 имеем $f(2)=1$.
Число $n$ можно получить командой A из $n-1$, командой B из $n/2$ при чётном $n$ и командой C из $\sqrt{n}$, если $n$ является полным квадратом.
Так как число 11 не должно входить в траекторию, принимаем $f(11)=0$. Последовательные значения для чисел от 2 до 20: $1, 1, 3, 3, 4, 4, 7, 8, 11, 0, 4, 4, 8, 8, 18, 18, 26, 26, 37$.
Для числа 20 учитываются переходы из 19 и 10:
$$f(20)=f(19)+f(10)=26+11=37$$Где здесь ошибаются
Не учитывать команду C при получении полных квадратов.
Считать программы, проходящие через число 11.
Запретить число 11 только как конечный результат, а не как промежуточный.