Шешімі: Подсчёт программ с числом 10
Исполнитель «Вычислитель» преобразует число, записанное на экране. У исполнителя есть три команды: 1) прибавить 1; 2) умножить на 2; 3) прибавить 3. Программа для «Вычислителя» — это последовательность команд. Сколько существует таких программ, которые преобразуют исходное число 3 в число 15 и при этом траектория вычислений программы содержит число 10? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 11, 22.
Шешім по шагам
5 қадамДля подсчёта числа программ, ведущих из 3 в заданное число, используем динамику: последний шаг может быть прибавлением 1, умножением на 2 или прибавлением 3.
$$f(n)=f(n-1)+f(n/2)+f(n-3)$$Вычисляя значения от 3 до 10, получаем: $f(3)=1$, $f(4)=1$, $f(5)=1$, $f(6)=3$, $f(7)=4$, $f(8)=6$, $f(9)=9$, $f(10)=14$.
Значит, существует $14$ способов попасть из 3 в 10.
Аналогично считаем количество способов из 10 в 15: $g(10)=1$, $g(11)=1$, $g(12)=1$, $g(13)=2$, $g(14)=3$, $g(15)=4$.
Любую программу, проходящую через 10, можно однозначно представить как программу из 3 в 10 и программу из 10 в 15.
$$14\cdot4=56$$Где здесь ошибаются
Не учитывают один из трёх нұсқа последней команды.
Складывают количество программ вместо перемножения.
Путают траекторию с последовательностью нөмір команд.