Выдача денег минимальным числом купюр

@DiabloRossi · Регистрация: 09.02.2011

Студворк — интернет-сервис помощи студентам

Так, может кто сможет подсказать алгоритм
суть такая:
в банкомате лежат деньги разных номиналов.
нужно выдать деньги минимальным число купюр.
Вроде, если номиналы кратны друг другу, все просто.
Но в данном случае, они не кратны.
Итак, я имею ArrayList, в котором храню номиналы купюр. Как бы мне сделать так, чтобы все нормально считывалось?
просто если у в банкомате купюры номиналом 3, 4 и 5 рублей, а надо выдать 16, мой алгоритм скажет, что не может нацело выделить кол-во купюр, ибо считает по такому принципу:
16\5 = 3
16-15=1
1 остается.
Как я вижу это дело:
Сначала он вычленяет 3 купюры по 5 монет, потом проходит остаток ArrayList со следущего элемента и прикидывает, можно ли выдать остаток. Если нельзя-возвращается, добавляет пятерку и снова проходит со след. элемента.
Но реализовать не удается

@M128K145 · 03.11.2011, 23:46

Вот набросал

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int[] denomination = { 3, 4, 5 };
int sum = 16;
int i = 0, j, k = denomination.length;
while (k != 0 && denomination[--k] > sum)
   ;
j = k;
int tempSum, count;
do {
   if ((tempSum = sum % denomination[j]) >= denomination[0] || tempSum == 0) {
      count = sum / denomination[j];
      sum = tempSum;
   } else {
      count = sum / denomination[j] - 1;
      sum = tempSum + denomination[j];
   }
   System.out.println("Denomination: " + denomination[j] + "; count: " + count);
   while (j != 0 && denomination[--j] > sum)
      ;
} while (i < k && sum > 0);

Но он работает по жадному алгоритму, т.е. если есть несколько способов выдать, то он будет выдавать как можно больше максимальных по номиналу, т.е. например сумма 18, ее можно выдать как 3-5 + 1-3 или же 2-5 + 2-4, так вот он выдаст именно первый вариант

@DiabloRossi · 04.11.2011, 17:04 **[ТС]**

Я сам уже написал алгоритм, но все равно спасибо.
По идее тут надо юзать рекурсивный парсер, который будет постоянно проверять остаток на возможность разложения.
Примерно тоже самое написал)

@M128K145 · 04.11.2011, 17:33

DiabloRossi, ничего не надо парсить, а тем более использовать рекурсию. Линейный алгоритм

@Goal · 04.11.2011, 18:02

та да.. рекурсией делай..
допустим число 100, число - которое нужно забрать...

идет проверка 100 больше либо равно чем купюра 200?
нет-используем меньшую купюру
идет проверка 100 больше либо равно чем купюра 100?
да-выдаем и отнимаем..
и так с остатком делаем..
потом если число достигнет 0.. выйти из цыкла

@DiabloRossi · 05.11.2011, 00:19 **[ТС]**

Goal, то, что вы написали-это само собой разумеется)
только речь идет не о том, по вашему алгоритму у вас банкомат будет неверно работать, а именно:
в банкомате имеются купюры по 5, 3 и 2 рубля.
при запросе выдать 16 рублей банкомат выдаст 15 или не выдаст ничего, потому что он поделит 16\5, получит 3 купюры, и не будет знать, что сделать с рублем.

А мой алгоритм, который не рекурсивный, но примерно похожий делает вот так:
Сначала вычленяет максимум(если брать из этого же примера, то это 3 по 5) и вызывает метод класса, чтобы проверить остаток(в нашем случае 1 рубль).
Функция ищет, есть ли в банкомате купюры в рубль, если нет возвращает false, тогда основная функция возвращает в банкомат купюру в 5 рублей и снова вызывает метод, который пытается разложить 6 рублей(что у него прекрасно получается(3*2)). После чего он возвращает true и деньги выдаются.
Если делать без рекурсии, как у меня, то 16-то он правильно выдаст.
А вот 416 выдаст некорректно, а именно:
если в банкомате есть купюры номиналом 100, 5, 3, 2, то он сначала выдаст 4 сотни.
А потом вызовет метод, который в свою очередь не сможет разложить 16, ибо сам считает по-простому алгоритму разложения остатка. И в итоге выдаст пользователю 3*100 + 22*5 + 2*3 = 416

Вижу два варианта разрешения вопроса, сделать метод рекурсивным. Или же проходить по ArrayList, в котором содержатся(у меня) сколько каких купюр выдается и проверить кратность, т.е. если у нас есть n-ное кол-во купюр, которое можно заменить одной купюрой старшего номинала, то мы заменяем.

С точки зрения производительности второй вариант быстрее, т.к. никаких рекурсий и прочего.
С точки зрения логики, второй вариант тупой и преднозначен для быдлокодеров)

Я лично вообще не стал дописывать, оставил так) "Берите мелочью, господа"(с)

@M128K145 · 05.11.2011, 00:42

Сообщение от DiabloRossi

А вот 416 выдаст некорректно, а именно:
если в банкомате есть купюры номиналом 100, 5, 3, 2, то он сначала выдаст 4 сотни.
А потом вызовет метод, который в свою очередь не сможет разложить 16, ибо сам считает по-простому алгоритму разложения остатка. И в итоге выдаст пользователю 3*100 + 22*5 + 2*3 = 416

Чем не подходит мой код? Результат:

Code
1
2
3
Denomination: 100; count: 4
Denomination: 5; count: 2
Denomination: 3; count: 2

@d31m07y1988 · 12.04.2016, 15:24

M128K145, А если не получается найти комбинацию код так и продолжает крутиться в бесконечном цикле.

там в конце ошибке i<k а должно быть i<j

Добавлено через 1 час 17 минут
Так же алгоритм не выводит минимальное количество банкнот для операции, н-р при сумме 600.
На счету:
500 2
200 3
10 10

а результат должен быть
200 3

А этот алгоритм не выводит даже 500 - 1, 10 - 10

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@DiabloRossi 2 / 2 / 1 Регистрация: 09.02.2011 Сообщений: 49

	Выдача денег минимальным числом купюр 27.10.2011, 20:53. Показов 18301. Ответов 7 Метки нет (Все метки) Так, может кто сможет подсказать алгоритм суть такая: в банкомате лежат деньги разных номиналов. нужно выдать деньги минимальным число купюр. Вроде, если номиналы кратны друг другу, все просто. Но в данном случае, они не кратны. Итак, я имею ArrayList, в котором храню номиналы купюр. Как бы мне сделать так, чтобы все нормально считывалось? просто если у в банкомате купюры номиналом 3, 4 и 5 рублей, а надо выдать 16, мой алгоритм скажет, что не может нацело выделить кол-во купюр, ибо считает по такому принципу: 16\5 = 3 16-15=1 1 остается. Как я вижу это дело: Сначала он вычленяет 3 купюры по 5 монет, потом проходит остаток ArrayList со следущего элемента и прикидывает, можно ли выдать остаток. Если нельзя-возвращается, добавляет пятерку и снова проходит со след. элемента. Но реализовать не удается 0

@DiabloRossi 2 / 2 / 1 Регистрация: 09.02.2011 Сообщений: 49
	04.11.2011, 17:04 [ТС]
	Я сам уже написал алгоритм, но все равно спасибо. По идее тут надо юзать рекурсивный парсер, который будет постоянно проверять остаток на возможность разложения. Примерно тоже самое написал) 0

@M128K145 8384 / 3617 / 419 Регистрация: 03.07.2009 Сообщений: 10,709
	04.11.2011, 17:33
	DiabloRossi, ничего не надо парсить, а тем более использовать рекурсию. Линейный алгоритм 0

@Goal Футболист 533 / 435 / 142 Регистрация: 31.10.2011 Сообщений: 1,010
	04.11.2011, 18:02
	та да.. рекурсией делай.. допустим число 100, число - которое нужно забрать... идет проверка 100 больше либо равно чем купюра 200? нет-используем меньшую купюру идет проверка 100 больше либо равно чем купюра 100? да-выдаем и отнимаем.. и так с остатком делаем.. потом если число достигнет 0.. выйти из цыкла 0

@DiabloRossi 2 / 2 / 1 Регистрация: 09.02.2011 Сообщений: 49
	05.11.2011, 00:19 [ТС]
	Goal, то, что вы написали-это само собой разумеется) только речь идет не о том, по вашему алгоритму у вас банкомат будет неверно работать, а именно: в банкомате имеются купюры по 5, 3 и 2 рубля. при запросе выдать 16 рублей банкомат выдаст 15 или не выдаст ничего, потому что он поделит 16\5, получит 3 купюры, и не будет знать, что сделать с рублем. А мой алгоритм, который не рекурсивный, но примерно похожий делает вот так: Сначала вычленяет максимум(если брать из этого же примера, то это 3 по 5) и вызывает метод класса, чтобы проверить остаток(в нашем случае 1 рубль). Функция ищет, есть ли в банкомате купюры в рубль, если нет возвращает false, тогда основная функция возвращает в банкомат купюру в 5 рублей и снова вызывает метод, который пытается разложить 6 рублей(что у него прекрасно получается(32)). После чего он возвращает true и деньги выдаются. Если делать без рекурсии, как у меня, то 16-то он правильно выдаст. А вот 416 выдаст некорректно, а именно: если в банкомате есть купюры номиналом 100, 5, 3, 2, то он сначала выдаст 4 сотни. А потом вызовет метод, который в свою очередь не сможет разложить 16, ибо сам считает по-простому алгоритму разложения остатка. И в итоге выдаст пользователю 3100 + 225 + 23 = 416 Вижу два варианта разрешения вопроса, сделать метод рекурсивным. Или же проходить по ArrayList, в котором содержатся(у меня) сколько каких купюр выдается и проверить кратность, т.е. если у нас есть n-ное кол-во купюр, которое можно заменить одной купюрой старшего номинала, то мы заменяем. С точки зрения производительности второй вариант быстрее, т.к. никаких рекурсий и прочего. С точки зрения логики, второй вариант тупой и преднозначен для быдлокодеров) Я лично вообще не стал дописывать, оставил так) "Берите мелочью, господа"(с) 0

@d31m07y1988 0 / 0 / 0 Регистрация: 12.04.2016 Сообщений: 1
	12.04.2016, 15:24
	M128K145, А если не получается найти комбинацию код так и продолжает крутиться в бесконечном цикле. там в конце ошибке i<k а должно быть i<j Добавлено через 1 час 17 минут Так же алгоритм не выводит минимальное количество банкнот для операции, н-р при сумме 600. На счету: 500 2 200 3 10 10 а результат должен быть 200 3 А этот алгоритм не выводит даже 500 - 1, 10 - 10 0