Решение: Подсчёт программ исполнителя К17
Исполнитель К17 преобразует число, записанное на экране. Он выполняет команды: прибавить 1, прибавить 2 или умножить на 2. Сколько существует программ, которые преобразуют исходное число 3 в число 12 и траектория вычислений которых содержит оба числа 9 и 11? Траектория вычислений — это последовательность результатов выполнения всех команд программы.
Решение по шагам
5 шаговОбозначим через $f(n)$ количество программ, переводящих число 3 в число $n$. Для получения $n$ последней командой можно было получить $n-1$, получить $n-2$ или, если $n$ чётно, получить $n/2$.
$$f(n)=f(n-1)+f(n-2)+f(n/2)\quad\text{для чётного }n$$Последовательно вычисляем количество способов от 3 до 9: $f(3)=1$, $f(4)=1$, $f(5)=2$, $f(6)=4$, $f(7)=6$, $f(8)=11$, $f(9)=17$.
$$f(9)=f(8)+f(7)=11+6=17$$От 9 до 11 возможны две программы: дважды прибавить 1 или сначала прибавить 2, затем прибавить 1.
$$g(11)=2$$Из 11 в 12 можно перейти единственным способом — прибавить 1.
$$h(12)=1$$Так как траектория должна пройти через 9 и затем через 11, количества способов на трёх участках перемножаются.
$$17\cdot 2\cdot 1=34$$Где здесь ошибаются
Не учитывать команду «умножить на 2» при подсчёте способов достижения чётных чисел.
Складывать количества способов на участках вместо их перемножения.
Считать программы, содержащие только одно из чисел 9 и 11.