|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
06.05.2011, 13:43 | #1 |
Регистрация: 06.05.2011
Сообщений: 5
|
Наименьшее кол-во купюр для размена С++
Товар стоит N рублей (N- натуральное число). Покупатель и кассир имеют неограниченное кол-во монет (купюр) различного достоинства (1,2,5,10,20,50,100,200,500,1000,50 00,10000,50000,100000 рублей). Предложить варианты расчета в которых используется минимальное кол-во монет (купюр).
Помогите с разработать алгоритм) Оригинальный текст задания в приложении |
06.05.2011, 14:44 | #2 |
Пользователь
Регистрация: 15.07.2010
Сообщений: 74
|
Используй Mod=% и целочисленное деление- делишь N на крупнейшую купюру , получаешь количество самых крупных купюр в N , потом остаток делишь на следующий по величине номинал и так до конца
|
06.05.2011, 18:55 | #3 |
Регистрация: 06.05.2011
Сообщений: 5
|
Этим способом я лишь подсчитаю каким набором купюр можно получить N
Моя же задача найти 1 или несколько вариантов размена с использованием МИНИМАЛЬНОГО количества купюр |
06.05.2011, 19:12 | #4 |
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,577
|
могу помочь за материальное вознаграждение
ICQ 395-546-218 |
06.05.2011, 19:20 | #5 |
Пользователь
Регистрация: 15.07.2010
Сообщений: 74
|
Sauruk. нет
Минимальным будет число при котором будет максимальное количество крупных купюр-так работает алгоритм |
06.05.2011, 19:36 | #6 |
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,577
|
Biggs
у вас что-то работает? предлагаю сначала проверить свой алгоритм, потом советовать. Контрпример: N = 600 купюры: 2, 200,500 очевидно, что самым оптимальным будет взять 3 купюры по 200. по алгоритму который предлагаете вы, мы сначала берем 1 купюру номиналом 500, остается 100 => набираем 50 купюр номиналом 2. Не надо советовать что попало |
06.05.2011, 19:43 | #7 |
Made In USSR!
Старожил
Регистрация: 01.09.2010
Сообщений: 3,657
|
"...В жизни я встречал друзей и врагов.В жизни много всего перевидал.Солнце тело мое жгло, ветер волосы трепал,но я смысла жизни так и не узнал..."
(c) Юрий Клинских aka "Хой" |
06.05.2011, 21:00 | #8 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Mad_Cat, ссылочка отличная.
Только попрошу всех заинтересовавшихся обратить внимание на один ОЧЕНЬ важный факт. В данном случае учитываются купюры УЧАСТВУЮЩИЕ в обмене с двух сторон. на рисунке хорошо видно, что, например, для N=9000 рублей понадобится всего ДВЕ купюры: 10000 и 1000 Покупатель даёт 10000 и ему дают сдачу 1000. записывается это 9000 = 10000 - 1000 p.s. а толковый алгоритм решения я пока не вижу... |
06.05.2011, 21:19 | #9 | |
Пользователь
Регистрация: 15.07.2010
Сообщений: 74
|
Цитата:
Но ,наверное , вы правы -надо все варианты считать |
|
06.05.2011, 21:39 | #10 | |
Регистрация: 06.05.2011
Сообщений: 5
|
Цитата:
|
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Программа для подсчета полного и эффективного кол-ва информации | wandering | Помощь студентам | 5 | 04.04.2010 19:56 |
макрос - подсчитать для каждой строки кол-во ячеек с «+», кол-во ячеек с «-» | Vadim_abs | Microsoft Office Excel | 36 | 14.07.2009 12:08 |
Найти кол-во целых чисел в первой последовательности и кол-во нечетных во второй. | DjDeniels-61 | Помощь студентам | 7 | 28.06.2009 13:04 |
Для вещественного массива А(20)вычислить наибольшее и наименьшее значения модуля раз-ти между сосед.эл-ми | faix | Помощь студентам | 2 | 14.11.2007 13:25 |