23.05 Количество программ из A в B смешанное
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Геральт копит чеканные монеты, количество которых записано на экране.
У него есть варианты, которым присвоены номера:
1. Прибавить 5 монет, убив утопца,
2. Прибавить 10 монет, выполнив заказ на призрака,
3. Увеличить количество монет в 2 раза, сыграв в гвинт.
Первый вариант учеличивает количество монет на 5, второй — на 10, третий — умножает количество монет на 2. Программа для Геральта из Ривии — это последовательность вариантов.
Геральту нужно накопить 100 монет, чтобы выкупить Лютика из плена эльфов.
Сколько существует программ, для которых при исходном количестве монет 15 является результатом 100 монет. При этом траектория вычислений содержит любимое число Геральта — 50 и не содержит числа 25 и 40? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 12, 22, 44.
Составим формулы:
— если число не делится на 2.
— если число делится на 2.
Заметим, что количество программ будет меняться только на числах кратных 5. Заполним таблицу по данным формулам, учитывая условия траектории:
Лютик точно будет спасён!
Решение рекурсией
Определим функцию f(a, b), которая будет вызывать саму себя. Она подсчитает количество программ, преобразующих число a в b. Функция возвращает:
- 0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
- 1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
- сумму значений для трёх возможных переходов (+5, умножить на 2, +10), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.
# Функция для подсчета количества программ преобразования a -> b def f(c, m): if c > m or c == 25 or c == 40: # Если число стало больше нужного или 25 или 40 return 0 if c == m: # Если дошли до нужного числа return 1 return f(c + 5, m) + f(c + 10, m) + f(c * 2, m) # Количество путей до текущего числа print(f(15, 50) * f(50, 100)) # Найдем ответ по условию задачи. Умножение позволяет гарантированно учесть число 50 в подсчётах.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
