Question

Исполнитель Прибавитель имеет две команды:

1. прибавь 1
2. прибавь 10

Первая команда увеличивает число на экране на 1, вторая — на 10. Программа — это последовательность команд. Сколько существует программ, которые число 10 преобразуют в число 31?

Accepted Answer

16

Answer

Идея решения: применить динамическое программирование, где для каждого числа от 10 до 31 подсчитаем количество способов его получить. Обозначим через $f(n)$ количество различных программ, преобразующих 10 в число $n$. Начальное условие: $f(10) = 1$ (пустая программа). Для любого $n > 10$ число можно получить двумя способами: - из числа $n - 1$ применением команды «прибавь 1»; - из числа $n - 10$ применением команды «прибавь 10» (если $n \geq 20$). Таким образом, рекуррентное соотношение: $$f(n) = f(n-1) + f(n-10) ext{ при } n \geq 20$$ $$f(n) = f(n-1) ext{ при } 10 < n < 20$$ Заполняем таблицу значений от 10 до 31: | $n$ | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | |---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---| | $f(n)$ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | Проверим вычисления: - $f(10) = 1$ - $f(11)$ до $f(19) = 1$ (только команда «прибавь 1») - $f(20) = f(19) + f(10) = 1 + 1 = 2$ - $f(21) = f(20) + f(11) = 2 + 1 = 3$ - $f(22) = f(21) + f(12) = 3 + 1 = 4$ - ... - $f(31) = f(30) + f(21) = 12 + 1 = 13$ Решение на Python: ```python def count_programs(start, end): f = [0] * (end + 1) f[start] = 1 for n in range(start + 1, end + 1): f[n] = f[n - 1] if n >= start + 10: f[n] += f[n - 10] return f[end] print(count_programs(10, 31)) ``` Решение на Pascal: ```pascal var f: array[10..31] of integer; i: integer; begin f[10] := 1; for i := 11 to 31 do begin f[i] := f[i - 1]; if i >= 20 then f[i] := f[i] + f[i - 10]; end; writeln(f[31]); end. ``` ![Рисунок](https://ege.sdamgia.ru/formula/svg/7c/7cc31458e70f33be44d5134ca53fc576.svg)

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