Динамическое программирование. Информатика Исполнитель Вычислитель преобразует число на экране компьютера. У него есть две команды:
Прибавь 1
Умножь на 3
Программа Вычислителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 18?
Динамическое программирование. Информатика Исполнитель Вычислитель преобразует число на экране компьютера. У него есть две команды:
Прибавь 1
Умножь на 3
Программа Вычислителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 18?
Прибавь 1
Умножь на 3
Программа Вычислителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 18?
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для решения этой задачи можно воспользоваться методом динамического программирования.
Заведем массив 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.