Предмет: Информатика, автор: nikitosik2222

Исполнитель Калькулятор преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1


2. Прибавить 3


Сколько существует программ, для которых при исходном числе 2 результатом является число 20 и при этом траектория вычислений содержит число 15 и не содержит число 10?

Ответы

Автор ответа: fctdgsygfdhngfxzgsac
0

Для розв'язання цієї задачі можна скористатися рекурсивним підходом та методом динамічного програмування. Створимо функцію, яка буде рахувати кількість способів досягнути певного числа з використанням заданих команд. Нехай 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.

Похожие вопросы
Предмет: Литература, автор: Sofya311217
А1. Среди предложенных списков выберите писателей, творчество которых относится к 1 половине XIX века: 1) Ф.М.Достоевский, Л.Н.Толстой, А.П.Чехов. 2) А.С.Пушкин, М.Ю.Лермонтов, Н.В.Гоголь. 3) М.И.Цветаева, О.З.Мандельштам, А.П.Платонов.
А2. Одним из направлений русской литературы XIX века был романтизм. Его основной чертой является: 1) Построение произведения на основе классических идеалов. 2) Внимание к чувствам и переживаниям героев. 3) Изображение конфликта между миром и человеком.

А3. Какое стихотворение А.С.Пушкина относится к философской лирике? 1) «Пророк» 2) «На холмах Грузии» 3) «Дар напрасный, дар случайный»

А4. Какой литературный критик написал статью «Луч света в темном царстве», посвященную драме А.Н.Островского «Гроза»? 1) Н. Добролюбов 2) Д. Писарев 3) Н. Страхов

А5. Кем по своим взглядам является Евгений Базаров – герой романа И.С. Тургенева «Отцы и дети»? 1) «Маленький человек» 2) «Лишний человек» 3) Нигилист

А6. Какое историческое событие отражено в поэме Н.А.Некрасова «Кому на Руси жить хорошо»? 1) Отечественная война 1812 г. 2) Отмена крепостного права 3) Октябрьская революция