Разложить число.

[pivnoibaron]

Привет. Дали тестовое задание. Но не пойму по какому принципу разложить надо. Как разложить число используя номиналы, точнее что делать то, умножать что то или как? Может кто знает.

---------------------------------------------------------------------------------------------------------------
Разложить число, используя монеты заданных номиналов, на N монет. Сделать интерфейс, в
котором можно будет устанавливать число, номиналы и N.
Визуализировать результат выполнения программы в виде стопки монет/фишек.

Минимальные требования:
- программа должна быть написана на ActionScript 3.0

Плюсами будет:
- программа сделана на AIR и запускается на iOS
- программа написана на haxe, с использованием фреймворка NME

===========================================
Пример

Дано:
номиналы = [0.01, 0.1, 0.25, 0.5, 1, 5]
число = 2.53
N=7

Ответом будет: [1, 0.5, 0.5, 0.5, 0.01, 0.01, 0.01]
------------------------------------------------------

[AlexCooper]

Ух... мне бы в такой универ) Я ActionScript изучал на факультативе

Добавлено через 3 минуты
А имеется ввиду, что у вас номиналы: 1, 2, 5, 10, 25 и 50копеек. А нужно к примеру на входе ввести 123 разложить на 10 монет, программа должна подобрать комбинацию из 10 монет чтобы в сумме они давали 123 копейки.

[alatar]

Ошибка в ответе, номинала 1 нет.

Добавлено через 4 минуты

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

Ух... мне бы в такой универ) Я ActionScript изучал на факультативе

Не думаю, что это задание из универа. Больше похоже на тестовое задание при приеме на работу.

[KumoKairo]

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

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

[AlexCooper]

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

Не думаю, что это задание из универа. Больше похоже на тестовое задание при приеме на работу.

Тогда печально, для работодателя.

[-De-]

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

Тогда печально, для работодателя.

Почему? Хорошее же задание. Не всякий придумает оптимизированный алгоритм, но переборный должен уметь написать всякий.

[iflamberg]

Ошибка в ответе, номинала 1 нет.

[0.01, 0.1, 0.25, 0.5, 1, 5]

Really?

[alatar]

Прочитал как 1,5

[КорДум]

Алгоритм "в лоб" предельно прост. Пускаем бесконечный цикл, пока оставшаяся сумма не станет равной 0. Вычитаем из нее каждый шаг самый большой номинал. Если сумма получилась отрицательной, то берем следующий номинал поменьше. Как только стала положительной, сохраняем остаток в переменную, где у нас была первоначальная сумма и идем на новую итерацию.

Что-то типа того (не окончательный вариант без кэширования) выглядит так:

while (sum > 0) {
    for (var i:uint = 0; i < nominalList.length; i++) {
        if ((sum - nominalList[i]) >= 0) {
            sum -= nominalList[i];
            resultList.push(nominalList[i]);
            break;
        }
    }
}

[alatar]

https://www.youtube.com/watch?v=O28YpB4fo18