ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм выдачи сдачи
12 сообщений из 12, страница 1 из 1
Алгоритм выдачи сдачи
    #36804726
Джеки Мхртчан
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Джеки Мхртчан
Гость
Требуется написать класс наследник DispenseAlgorithm, реализующий алгоритм расчета сдачи обеспечивающий равномерное расходование номиналов.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
public abstract class DispenseAlgorithm
{
       public abstract Dictionary<int, int> CalculateDispense(CassetteData[] data, int summ);
}

public class CassetteData
{
       public int UID { get; set; }
       public int Nominal { get; set; }
       public int Count { get; set; }

       public CassetteData() { }
}
Класс CassetteData – предоствляет информацию о наборе купюр определенного номила имеющуюся в данный момент времени, где Nominal – значени номинала купюры , а Count – их текушее кол-во, UID – уникальны идетификатор данного набора.
В метод CalculateDispense реализуемого класса передается информация о доступных на данный момент наборах купур (CassetteData{] data) и сумма(int summ) которую нужно выдать в качестве сдачи. Метод должен вернуть объект Dictionary<int, int> где ключ - уникальный идентификатор набора купюр, а значение – колво купюр данного набора требуемое к выдачи.
Желаемый результат: купюры выдаются таким образом, чтобы они заканчивались в как можно более равномерно на протежении нескольких сессий выдачи сдачи.
Пример:
Имеются наоборы:
автор1 10 руб 100 купюр
2 50 руб 100 купюр
3 100 руб 100 купюр

Нужно выдать 800 рублей.

Идеальный результат:
автор1 5 штук
2 5 штук
3 5 штук

Т.е. 800 = 10 * 5 + 50 * 5 + 100 * 5

Маложелательный результат:
автор1 0 купюр
2 0 купюр
3 8 купюр

Т.е. 800 = 10 * 0 + 50 * 0 + 100 * 8
...
Рейтинг: 0 / 0
22.08.2010, 01:37:33
| Ответить | Цитировать | Написать  
Алгоритм выдачи сдачи
    #36804754
alex_k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex_k
Участник
определить наибольшее число купюр в любой кассете.
затем циклом проходить все кассеты(от маленького к большому).
и с каждой кассеты брать купюру случайным образом:
if (rand()%max>Cass[i].Count)//берем купюру.
//и проверяем, не превысит ли она нужную сумму.

если по прошествии цикла нужная сумма не набрана, но хотя бы одна купюра взята - повторяем цикл.
если же сумма не набрана и ни одна купюра не взята - выдать нужную сумму невозможно.

это я сейчас за три минуты сочинил, ответственности не несу :)
...
Рейтинг: 0 / 0
22.08.2010, 06:35:47
| Ответить | Цитировать | Написать  
Алгоритм выдачи сдачи
    #36804755
alex_k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex_k
Участник
if (rand()%max < Cass[i].Count)
ошибочка вышла :)
...
Рейтинг: 0 / 0
22.08.2010, 06:36:57
| Ответить | Цитировать | Написать  
Алгоритм выдачи сдачи
    #36804768
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
Джеки Мхртчанкупюры выдаются таким образом, чтобы они заканчивались в как можно более равномерно на протежении нескольких сессий выдачи сдачи.
Очень неудачная формулировка.
Какие есть априорные сведения о выдаваемых суммах?

Вот, например, есть в кассе купюры 2х127 рублей и 150х1 рублю. Надо выдать 127 рублей.
Если просто решать задачу минимакса (максимизировать минимальное количество купюр одного номинала), то надо выдать 127х1 рублю, оставив 2х127 и 23х1. Но если известно, что с такой суммой нам просто "повезло" и дальше будут разные кривые суммы типа 11, 17 и т.п., то разумнее отдать 1х127 и оставить себе рублёвые для "более равномерного" расхода "на протяжении нескольких сессий".
...
Рейтинг: 0 / 0
22.08.2010, 08:03:15
| Ответить | Цитировать | Написать  
Алгоритм выдачи сдачи
    #36805107
Джеки Мхртчан
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Джеки Мхртчан
Гость
junior idiotДжеки Мхртчанкупюры выдаются таким образом, чтобы они заканчивались в как можно более равномерно на протежении нескольких сессий выдачи сдачи.
Очень неудачная формулировка.
Какие есть априорные сведения о выдаваемых суммах?

Вот, например, есть в кассе купюры 2х127 рублей и 150х1 рублю. Надо выдать 127 рублей.
Если просто решать задачу минимакса (максимизировать минимальное количество купюр одного номинала), то надо выдать 127х1 рублю, оставив 2х127 и 23х1. Но если известно, что с такой суммой нам просто "повезло" и дальше будут разные кривые суммы типа 11, 17 и т.п., то разумнее отдать 1х127 и оставить себе рублёвые для "более равномерного" расхода "на протяжении нескольких сессий".
Возможно, но условие именно такое
...
Рейтинг: 0 / 0
22.08.2010, 18:08:23
| Ответить | Цитировать | Написать  
Алгоритм выдачи сдачи
    #36805116
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
Так как нужно выдать 127 рублей при имеющихся 2 купюрах по 127 публей и 150 купюр по 1 рублю?
...
Рейтинг: 0 / 0
22.08.2010, 18:13:11
| Ответить | Цитировать | Написать  
Алгоритм выдачи сдачи
    #36805312
alex_k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex_k
Участник
если ставить целью максимально долгую возможность выдавать сдачу, то выдавать ее надо максимально крупными купюрами. потому что если закончатся мелкие - то не каждую сдачу выдашь, хотя сумма денег позволяет.
...
Рейтинг: 0 / 0
22.08.2010, 23:15:50
| Ответить | Цитировать | Написать  
Алгоритм выдачи сдачи
    #36805322
Джеки Мхртчан
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Джеки Мхртчан
Гость
alex_kесли ставить целью максимально долгую возможность выдавать сдачу, то выдавать ее надо максимально крупными купюрами. потому что если закончатся мелкие - то не каждую сдачу выдашь, хотя сумма денег позволяет.
Нужно сделать по условию, это не обязательно должно быть рационально. Условие - рациональность не важна.
...
Рейтинг: 0 / 0
22.08.2010, 23:23:22
| Ответить | Цитировать | Написать  
Алгоритм выдачи сдачи
    #36805427
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
Совершенно стандартная задача о рюкзаке. Что там париться то?
"Равномерное расходование номиналов" это либо студенческое задание, либо чушь.
Даже если это студенческое задание, то присваиваешь каждому номиналу число вида "количество_купюр_в_номинале/общее_количество_купюр", используя эту вероятность выбираешь случайный номинал и дальше рюкзак в чистом виде.
...
Рейтинг: 0 / 0
23.08.2010, 04:56:28
| Ответить | Цитировать | Написать  
Алгоритм выдачи сдачи
    #36805619
Джеки Мхртчан
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Джеки Мхртчан
Гость
White OwlСовершенно стандартная задача о рюкзаке. Что там париться то?
"Равномерное расходование номиналов" это либо студенческое задание, либо чушь.
Даже если это студенческое задание, то присваиваешь каждому номиналу число вида "количество_купюр_в_номинале/общее_количество_купюр", используя эту вероятность выбираешь случайный номинал и дальше рюкзак в чистом виде.
я об этом не слышал. расскажи подробнее
...
Рейтинг: 0 / 0
23.08.2010, 10:15:59
| Ответить | Цитировать | Написать  
Алгоритм выдачи сдачи
    #36805625
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
Джеки Мхртчаня об этом не слышал. расскажи подробнее
http://en.wikipedia.org/wiki/Knapsack_problem
White Owl поторопился.
В задаче о рюкзаке:
1. Однозначно задаётся "ценность" каждого предмета. Оценка ценности купюр в твоей задаче и является основной сложностью, в явном виде она не задана. Считать её обратно пропорциональной количеству таких же банкнот или равной их количеству со знаком минус -- вот по меньшей мере два "естественных", но различных варианта, и оба могут быть оспорены.
2. Нет никаких вероятностей. Решение строго детерминировано и является неявным полным перебором.
...
Рейтинг: 0 / 0
23.08.2010, 10:20:19
| Ответить | Цитировать | Написать  
Алгоритм выдачи сдачи
    #36805830
Джеки Мхртчан
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Джеки Мхртчан
Гость
junior idiot,

там все проще, задача расчитана на полчаса, это тестовое задание
...
Рейтинг: 0 / 0
23.08.2010, 11:41:45
| Ответить | Цитировать | Написать  
12 сообщений из 12, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм выдачи сдачи
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=36804755&tid=1343502]:
 0ms
get settings:
 8ms
get forum list:
 16ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 183ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 57ms
get tp. blocked users:
 1ms
others: 196ms
total:  480ms
созд. / загр.: 480ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]