Question

Исполнитель преобразует число на экране. Доступны три команды:

1. Прибавить 1.
2. Прибавить 2.
3. Умножить на 3.

Программа — это последовательность команд. Найти количество программ, которые исходное число 2 преобразуют в число 19, при условии, что траектория проходит через 9 и не проходит через 12.

Accepted Answer

650

Answer

Идея решения: разбить задачу на два независимых этапа — путь от 2 к 9 и путь от 9 к 19, затем перемножить количества траекторий. Используем динамическое программирование. Обозначим через $f(a, b)$ количество способов преобразовать число $a$ в число $b$ с помощью доступных команд, не посещая число 12. **Построение таблиц:** Для пути от 2 к 9: | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |---|---|---|---|---|---|---|---| | 1 | 1 | 2 | 3 | 6 | 9 | 15 | 25 | Для пути от 9 к 19 (исключая 12): | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | |---|----|----|----|----|----|----|----|----|----|----| | 1 | 1 | 2 | 0 | 2 | 2 | 4 | 6 | 10 | 16 | 26 | Значение для 12 равно 0, так как это число исключено из траектории. Итоговый ответ: $25 imes 26 = 650$. **Программное решение:** ```python def f(a, b): if a == b: return 1 if a > b or a == 12: return 0 return f(a + 1, b) + f(a + 2, b) + f(a * 3, b) print(f(2, 9) * f(9, 19)) ``` ```pascal function f(a, b: integer): integer; begin if a = b then f := 1 else if (a > b) or (a = 12) then f := 0 else f := f(a + 1, b) + f(a + 2, b) + f(a * 3, b) end; begin writeln(f(2, 9) * f(9, 19)) end. ``` ```cpp #include using namespace std; int f(int a, int b) { if (a == b) return 1; if (a > b || a == 12) return 0; return f(a + 1, b) + f(a + 2, b) + f(a * 3, b); } int main() { cout << (f(2, 9) * f(9, 19)) << endl; return 0; } ```

Задание №23Алгоритмы и исполнителиЕГЭ по информатике