Шешімі: Программы с траекторией через 8
Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды: прибавить 2, умножить на 2 и прибавить 3. Программа для Вычислителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 1 в число 18 и при этом траектория вычислений программы содержит число 8? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Шешім по шагам
3 қадамТак как траектория должна содержать число 8, каждую программу можно однозначно разделить на участок от 1 до 8 и участок от 8 до 18.
$$N = N_{1\to 8}\cdot N_{8\to 18}$$Для каждого числа последовательно подсчитываем количество способов получить его с помощью команд «прибавить 2», «умножить на 2» и «прибавить 3», учитывая только допустимые переходы.
$$f(n)=f(n-2)+f\left(\frac{n}{2}\right)+f(n-3)$$После подсчёта количества программ на обоих участках и перемножения результатов получаем искомое число программ.
$$N_{1\to 8}\cdot N_{8\to 18}=80$$Где здесь ошибаются
Не учитывать условие о прохождении траектории через число 8.
Складывать, а не перемножать количества программ на двух участках.
Учитывать умножение на 2 только для нечётных чисел.