Требуется написать класс наследник DispenseAlgorithm, реализующий алгоритм расчета сдачи обеспечивающий равномерное расходование номиналов.
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> где ключ — уникальный идентификатор набора купюр, а значение – колво купюр данного набора требуемое к выдачи.
Желаемый результат: купюры выдаются таким образом, чтобы они заканчивались в как можно более равномерно на протежении нескольких сессий выдачи сдачи.
Пример:
Имеются наоборы:автор
я бы рассчитывал оптимальную по колличеству купюр выдачу (для реально применяющихся купюр подойдет жадный алгоритм).
а потром смотрел на количество оставшихся купюр в кассетах и пытался разменять крпные купюры мелкими до достижения баланса.
ps: а откуда такие странные требования? это же приведет к тому что когда деньги будут заканчиватся будут повысится вероятность случая когда сдачу выдать не удастся из за того что остались только крупные купюры.
Здравствуйте, cvetkov, Вы писали:
C>я бы рассчитывал оптимальную по колличеству купюр выдачу (для реально применяющихся купюр подойдет жадный алгоритм).
C>а потром смотрел на количество оставшихся купюр в кассетах и пытался разменять крпные купюры мелкими до достижения баланса.
C>ps: а откуда такие странные требования? это же приведет к тому что когда деньги будут заканчиватся будут повысится вероятность случая когда сдачу выдать не удастся из за того что остались только крупные купюры.
Дело не в том, как рациональнее, а в том, чтобы сделать так, как написано в условии.
Здравствуйте, Darooma, Вы писали:
D>Дело не в том, как рациональнее, а в том, чтобы сделать так, как написано в условии.
ну тогда не повезло
ну и делать надо в лоб.
проссумировать номиналы всех касет.
разделить сумму квыдаче на этот сумму номиналов.
частное будет количеством купюр каждого номинала которык надо выдать.
остаток выдать жадным алгоритмом. (если постаратся следовать букве закона до конца то остаток надо выдать тем же алгоритмом только без учета самого старшего номинала, если опять будет остаток операцию повторять убирая номиналы от большего к меньшему).
но этот алгоритм будет еще интенсивнее пожирать мелкие купюры.
если цель выдавать как можно ровнее это лучший вариант.
Здравствуйте, Darooma, Вы писали:
D>Желаемый результат: купюры выдаются таким образом, чтобы они заканчивались в как можно более равномерно на протежении нескольких сессий выдачи сдачи.
Welcome to the real world, с его нечёткими техническими заданиями.
Что значит "как можно более равномерно"?
— стараться сохранить пропорции количества монет в кассе
— стараться сохранить разницу (т.е. сдать примерно равное количество каждого номинала)
— стараться выровнять количество
Например, было 10×1р, 10×2р, 10×5р, 100×10р (т.е. 1:1:1:10)
Нужно сдать 100р.
Варианты
— 1×1р, 2×2р, 1×5р, 9×10р — сдали примерно по 1/10 каждого количества, и остаётся 9:8:9:91 ≈ 1:0.9:1:10.1
— 5×1р, 5×2р, 5×5р, 6×10р — сдали примерно по 5 монет, остаётся 5:5:5:94
— 10×10р — стремимся достичь 10:10:10:10, но пока что получилось 10:10:10:80
"На протяжении нескольких сессий" — неплохо бы знать о распределении запросов сдачи.
Тогда мы можем выработать стратегию, полагающуюся на грядущие запросы, а не только на текущий.
Например, мы знаем, что запросы 1р, 2р, 5р, 10р встречаются с равной вероятностью. Тогда нет нужды придумывать, как разменять 10р: всегда отдаём 1×10р, полагая, что возникший сейчас перекос будет выравнен последующими запросами более мелких монет.