(№ 465) Исполнитель Калькулятор преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: .ПрИбавИТь 2 .Прибав...
Условие:
(№ 465) Исполнитель Калькулятор преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: .ПрИбавИТь 2 .Прибавить 2 Программа для исполнителя Калькулятор- это последовательность Команд. Сколько существует программ, Для которых при исходНом числе 3 результатом является число 18, предпоследней командой которых яЯВляется
Решение:
Для решения этой задачи можно использовать метод динамического программирования.
Пусть dp[i] - количество программ, которые приводят к числу i. Тогда dp[i] = dp[i-2] + dp[i-3], так как мы можем получить число i, либо прибавив 2 к числу i-2, либо прибавив 3 к числу i-3.
Исходя из условия задачи, нам нужно найти количество программ, для которых при исходном числе 3 результатом является число 18, предпоследней командой которых является прибавление 2.
Мы можем начать с числа 3 и последовательно вычислить dp[18]. При этом, чтобы предпоследней командой было прибавление 2, нам нужно вычислить dp[16].
Применяя формулу dp[i] = dp[i-2] + dp[i-3], мы можем последовательно вычислить значения dp[3], dp[4], ..., dp[18].
Таким образом, мы можем найти количество программ, удовлетворяющих условию задачи.