Сколькими способами можно разменять 100 000 рублей на монеты 1, 2, 5 рублей?

Задача такова: сколькими способами можно разменять 100 000 рублей на монеты 1 2 5 рублей,то есть
нужно выписать количество решений уравнения:
1*x+2*y+5*z=100 000;

Объясните ,пожалуйста, алгоритм решения

0

Ну я придумал только так)
Но время...

0

Рекурсия же.
1) Есть только монеты по рублю. N рублей размениваются единственным способом.
2) Есть монеты по рублю и по два. Можно взять от 0 до N/2 монет по два рубля, остальную сумму добрать монетами по рублю Итого - 1+N/2 вариантов.
3) Появились монеты по пять рублей. Берем от 0 до N/5 пятирублевок. Оставшуюся сумму размениваем числом способов посчитанным в пункте 2.

2

floor(1+N/2), так как разменивать монетами по два рубля можно и нечётную сумму

0

Интересное решение (только для данных монет):

0

Классическая задача на динамическое программирование (термин "дин.прог" вообще-то не имеет отношение к созданию программного кода, ну это к слову).

Пусть мы знаем, сколькими способами можно разменять все суммы меньше N. Тогда найти число способов для N можно так - это столько же способов, сколько N-1 (сумма без монеты по копейке) плюс число способов для N-2 (сумма монет без монеты в две копейки) плюс число способов для N-5 (сумма без монеты в пять копеек). Значит, формула:

F(N) = F(N-1) + F(N-2) + F(N-5)

При этом начальные ограничения такие: F(N) = 0 при N < 0, F(0) = 1.

Реализовывать это можно рекурсией, но, как и для чисел Фиббоначи, не стоит. Лучше заводим массив на N элементов и считаем для каждого элемента от 1 до N. Считаться будет очень быстро, т.к. формула элементарна, сложность в точности O(N). Можно сэкономить память за счет быстродействия, заведя массив всего на 6 элементов, т.к. нам нужны только 5 предыдущих (тогда придется постоянно перезаписывать его значения), а можно даже двусвязный список, чтобы при добавлении нового элемента предыдущий первый быстро удалялся (вопрос, в том, что быстрее - перезаписать 5 элементов, или вставить-удалить 5 раз элемент в список) (для быстрой работы с концами - std::list или std::deque).

1

0

Можно через ДП, а можно по рабоче-крестьянски:
Добавлено через 2 минуты

Сообщение от andreysv floor(1+N/2), так как

за нас целочисленное деление постарается безо всякой флоры.

2

Сообщение от _Ivana за нас целочисленное деление постарается безо всякой флоры.

Да, потом уж заметил.

Миниатюры

 

0

Сообщение от Renji 1) Есть только монеты по рублю. N рублей размениваются единственным способом. 2) Есть монеты по рублю и по два. Можно взять от 0 до N/2 монет по два рубля, остальную сумму добрать монетами по рублю Итого - 1+N/2 вариантов. 3) Появились монеты по пять рублей. Берем от 0 до N/5 пятирублевок. Оставшуюся сумму размениваем числом способов посчитанным в пункте 2.

Сообщение от _Ivana можно по рабоче-крестьянски

Тоже довольно симпатичный вариант, легко обобщается с сохранением линейной сложности для любых трех монет 1, m, n (и, кажется, немного потруднее - для m, n, p). Быстрее, чем динпрог, и памяти не ест. Жаль, не масштабируется при росте числа монет.

0

Простите, не то вставил.

Миниатюры

 

0

Сообщение от Гром Тоже довольно симпатичный вариант, легко обобщается с сохранением линейной сложности для любых трех монет 1, m, n (и, кажется, немного потруднее - для m, n, p). Быстрее, чем динпрог, и памяти не ест. Жаль, не масштабируется при росте числа монет.

res+=1+(100000-z*5)/2 по сути сумма членов арифметической прогрессии плюс ошибки округления. Так что после некоторых шаманств решение должно свестись к константной сложности, после чего его можно расширять на четыре монеты.

0

тут не проходит динамика с f(n)=f(n-1)+f(n-2)+f(n-5) хотя бы по той причине, что
mass[1]=1;
mass[2]=2;
mass[3]=2;
mass[4]=3;
mass[5]=4;
mass[6]=5;

и mass[6]<>mass[1]+mass[5]+mass[4];

0