Показать сообщение отдельно
Старый 27.02.2013, 16:31
KumoKairo вне форума Посмотреть профиль Отправить личное сообщение для KumoKairo Найти все сообщения от KumoKairo
  № 4  
Ответить с цитированием
KumoKairo
 
Аватар для KumoKairo

Регистрация: Jan 2013
Сообщений: 550
Записей в блоге: 1
Я думаю там можно обойтись простым алгоритмом с использованием наибольшего делителя из заданных.
То есть берем число, берем массив номиналов. Находим наибольший делитель из заданных номиналов, чтобы при целочисленном делении результат не был равен нулю (если делимое больше делителя, то после целочисленного деления получится ноль). Считаем это первым номиналом, запоминаем, увеличиваем счетчик найденных номиналов. Вычитаем из числа номинал, получаем новое число, которому таким же образом находим максимальный из возможных номинал. В итоге у нас получится какое-то количество (M) номиналов, которое будет или не будет равно желаемому количеству (N). Если M != N, то произвольно (или любым другим способом) берем один из имеющихся (найденных) номиналов, которые можно разложить с помощью других потенциальных номиналов, и раскладываем. Снова проверяем M != N, при необходимости повторяем

То есть в случае с вашим примером с 2.53 по этому алгоритму найдется список номиналов [1, 1, 0.5, 0.01, 0.01, 0.01], а потом номинал 1 разложится на два номинала 0.5
Если нужно, могу накатать саму программу)