Исполнитель РазДваТри преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2...
Условие:
Решение:
Программ для исполнителя РазДваТри, которые преобразуют число на экране?
Для решения этой задачи можно использовать метод динамического программирования. Предположим, что нам нужно преобразовать число n на экране.
Создадим массив dp размером n+1, где dp[i] будет хранить количество программ, которые преобразуют число i на экране.
Инициализируем dp[0] = 1, так как единственная программа, которая может преобразовать число 0, это пустая программа.
Затем, для каждого числа i от 1 до n, мы будем обновлять значение dp[i] следующим образом:
dp[i] = dp[i-1] + dp[i/2] + dp[i/3]
Первое слагаемое dp[i-1] соответствует применению первой команды (прибавление 1), второе слагаемое dp[i/2] соответствует применению второй команды (умножение на 2), третье слагаемое dp[i/3]...
