Исполнитель Калькулятор преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 3
Сколько существует программ, для которых при исходном числе 3 результатом является число 20 и при этом траектория вычислений содержит число 15 и не содержит число 10?
Исполнитель Калькулятор преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 3
Сколько существует программ, для которых при исходном числе 3 результатом является число 20 и при этом траектория вычислений содержит число 15 и не содержит число 10?
1. Прибавить 1
2. Прибавить 3
Сколько существует программ, для которых при исходном числе 3 результатом является число 20 и при этом траектория вычислений содержит число 15 и не содержит число 10?
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для решения данной задачи можно использовать динамическое программирование.
Построим таблицу результатов для всех чисел от 3 до 20. Пусть dp[i] - количество способов получить число i. Изначально dp[3] = 1, так как у нас только один способ получить число 3. Затем, поочередно перебирая числа от 4 до 20, будем обновлять значения dp[i] следующим образом:
dp[i] = dp[i-1] + dp[i-3] для всех i, где число i достижимо через прибавление 1 или 3.
Таким образом, найдем значения dp[4], dp[5], ..., dp[20]. После этого, чтобы найти количество программ, удовлетворяющих условиям задачи, нужно сложить dp[20], dp[19], dp[18], ..., dp[15].
Таким образом, существует dp[20] + dp[19] + dp[18] + dp[17] + dp[16] способов программ, для которых при исходном числе 3 результатом является число 20, траектория вычислений содержит число 15 и не содержит число 10.