Pascal

Вопрос

Эмулятор банкомата

Заданы количества купюр след. достоинств:
1,3,5,10,20,50,100,500,1000,2000,5000.

Можно ли набрать из этих монет заданную сумму? Если можно, то указать как это сделать. Подскажите, как решить эту задачу?

Ответ

Если стоит задача набрать заданную сумму X и не учитывать того, что некоторых купюр может не оказаться, то задача становится немного проще.

Решение:

Пусть надо набрать сумму X рублей. Организуем следующий цикл:

Пока остаток не равен 0
1. Берем номинал купюры (Y), начиная с самой большой.
2. Ищем количество таких купюр, которое не превышает исходной суммы. N = X div Y.
3. Находим остаток, который заведомо меньше Y и который надо будет покрыть. R = X — N*Y
4. Переходим к пункту 1

Пример:

Пусть нужно найти набор купюр для суммы 12345 рублей.
X = 12345

1) Y = 5000, N = 2, R = 12345 — 2*5000 = 2345
2) Y = 2000, N = 1, R = 2345 — 2000 * 1 = 345
3) Y = 1000, N = 0, R = 345 — 1000*0 = 345
4) Y = 500, N = 0, R = 345 — 500*0 = 345
5) Y = 100, N = 3, R = 345 — 3* 100 = 45
6) Y = 50, N = 0, R = 45 — 0*50 = 45
7) Y = 20, N = 2, R = 45 — 2*20 = 5
8) Y = 10, N = 0, R = 5 — 10*0 = 5
9) Y = 5, N = 1, R = 5-1*5=0

Конец цикла.

Имеем: для набора суммы 12345 рублей нужно

5000 — 2
2000 — 1
1000 — 0
500 — 0
100 — 3
50 — 0
20 — 2
10 — 0
5 — 1

До остальных даже не дошло…

Так как можно представить например 50 = 2*20 + 10, то это не единственный алгоритм.

Из конференции Expert_FAQ