Задача по математике Сколькими способами купюру в 50 рублей можно разменять монетами в 1 и 2 рубля?
Задача по математике Сколькими способами купюру в 50 рублей можно разменять монетами в 1 и 2 рубля?
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для решения этой задачи можно воспользоваться динамическим программированием.
Пусть dp[i] - количество способов разменять купюру в i рублей. Тогда dp[0] = 1 (так как разменять 0 рублей можно единственным образом - не разменять ничего), dp[1] = 1 (разменять 1 рубль можно одним способом - монетой в 1 рубль), dp[2] = 2 (разменять 2 рубля можно двумя способами - двумя монетами в 1 рубль или одной монетой в 2 рубля).
Далее заполним массив dp по формуле: dp[i] = dp[i - 1] + dp[i - 2]. Таким образом, получим количество способов разменять купюру в 50 рублей.
Код на Python:
dp = [0] * 51dp[0] = 1
dp[1] = 1
for i in range(2, 51):
dp[i] = dp[i - 1] + dp[i - 2]
print(dp[50])
Ответ: количество способов разменять купюру в 50 рублей монетами в 1 и 2 рубля - 20365011074.