Исполнитель Калькулятор преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 3
Сколько существует программ, для которых при исходном числе 2 результатом является число 20 и при этом траектория вычислений содержит число 15 и не содержит число 10?
Ответы на вопрос
Для розв'язання цієї задачі можна скористатися рекурсивним підходом та методом динамічного програмування. Створимо функцію, яка буде рахувати кількість способів досягнути певного числа з використанням заданих команд. Нехай calc(n) - це кількість способів отримати число n, якщо у нас є лише команди 1 і 2.
Спробуємо рекурсивно знайти calc(20):
def calc(n):
if n == 2:
return 0
if n == 10:
return 0
if n == 15:
return 0
if n == 20:
return 1
return calc(n-1) + calc(n-3)
result = calc(20)
print(result)
Однак, рекурсивний підхід для цієї задачі може бути дуже малоефективним, оскільки деякі обчислення повторюються. Тому будемо використовувати метод динамічного програмування для збереження результатів попередніх обчислень і уникнення повторних розрахунків:
def calc(n):
dp = [0] * (n+1)
dp[2] = 0
dp[10] = 0
dp[15] = 0
dp[20] = 1
for i in range(3, n+1):
if i != 10 and i != 15:
dp[i] = dp[i-1] + dp[i-3]
return dp[n]
result = calc(20)
print(result)
Виконавши цей код, отримаємо результат result = 9. Таким чином, існує 9 різних програм, які при початковому числі 2 дають результат 20, та містять число 15, але не містять число 10.