Задание по информатике за 11 класс.

привет, садись 2

Для решения этой задачи можно использовать метод динамического программирования.

1) Для вычисления количества программ, преобразующих число 1 в число 20, можно использовать следующий алгоритм:

- Создаем массив dp, где dp[i] будет хранить количество программ, преобразующих число i в число 20.
- Инициализируем dp[1] = 0 (так как число 1 уже равно 20).
- Для каждого числа i от 2 до 20:
- Инициализируем dp[i] = 0.
- Перебираем все возможные команды:
- Если команда "прибавь 1" преобразует число i-1 в число i, то увеличиваем dp[i] на dp[i-1].
- Если команда "умножь на 2" преобразует число i/2 в число i, то увеличиваем dp[i] на dp[i/2].
- В итоге, dp[20] будет содержать количество программ, преобразующих число 1 в число 20.

2) Для вычисления количества программ, у которых в качестве промежуточного результата обязательно получается число 15, можно использовать аналогичный алгоритм, но с некоторыми изменениями:

- Создаем массив dp, где dp[i] будет хранить количество программ, преобразующих число i в число 15.
- Инициализируем dp[1] = 0 (так как число 1 не равно 15).
- Для каждого числа i от 2 до 15:
- Инициализируем dp[i] = 0.
- Перебираем все возможные команды:
- Если команда "прибавь 1" преобразует число i-1 в число i, то увеличиваем dp[i] на dp[i-1].
- Если команда "умножь на 2" преобразует число i/2 в число i, то увеличиваем dp[i] на dp[i/2].
- В итоге, dp[15] будет содержать количество программ, у которых в качестве промежуточного результата обязательно получается число 15.

3) Для вычисления количества программ, у которых в качестве промежуточного результата никогда не получается число 12, можно использовать аналогичный алгоритм, но с некоторыми изменениями:

- Создаем массив dp, где dp[i] будет хранить количество программ, преобразующих число i.
- Инициализируем dp[1] = 0 (так как число 1 уже равно 12).
- Для каждого числа i от 2 до 20:
- Инициализируем dp[i] = 0.
- Перебираем все возможные команды:
- Если команда "прибавь 1" преобразует число i-1 в число i и i-1 не равно 12, то увеличиваем dp[i] на dp[i-1].
- Если команда "умножь на 2" преобразует число i/2 в число i и i/2 не равно 12, то увеличиваем dp[i] на dp[i/2].
- В итоге, сумма всех элементов массива dp будет содержать количество программ, у которых в качестве промежуточного результата никогда не получается число 12.

Таким образом, для решения задачи необходимо реализовать алгоритм динамического программирования, описанный выше, и применить его для каждого из трех случаев.

Нервная работёнка