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

Прибавь 1

Умножь на 3

Программа Вычислителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 18?

Предыдущий
вопрос Следующий
вопрос

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

Заведем массив dp[], где dp[i] будет хранить количество программ, для которых результатом является число i.

Изначально у нас dp[3] = 1, так как изначальное число - 3.

Затем переберем все числа от 3 до 18 и посчитаем количество программ для каждого числа, используя рекуррентную формулу:

dp[i] = dp[i-1] + dp[i/3], если i делится на 3 без остатка

dp[i] = dp[i-1], если i не делится на 3 без остатка

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