Вася вносит X руб.У него имеются номиналы:1,2,5,10,50,100,500. Сколько РАЗНЫХ купюр он отдаст,если начинает с больших? (как решить с помощью ДЕЛЕНИЯ?

Question

[alexeidilos]

Мне по учёбе нужно решить задание:


Я написал решение, в котором от суммы отнимается число. Оно работает верно, но его отвергли. Мне сказали переписать его с помощью деления ( / ), потому что оно более производительное, чем вычитание.
Как возможно это сделать?
Мне нужно поменять s = s - nominals[z]; на деление. Если я так и пишу, то программа уходит в бесконечный цикл..

import java.util.Scanner;

public class execution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("Сколько вы хотите заплатить?");
        int S = scanner.nextInt(); //сумма к оплате
        int[] nominals = new int[]{500, 100, 50, 10, 5, 2, 1}; //какие купюры имеются
        ArrayList<Integer> paidNominalsArrayList = new ArrayList<Integer>(); // какие номиналы внесли

        //перебор числа S по убывающей
        for (int s = S; s >= 1; s--) {
            // перебор номиналов по убывающей
            for (int z = 0; z < nominals.length; z++) {
                //Если номинал входит в сумму хоть один раз
                if ((s / nominals[z]) >= 1) {
                    System.out.println("Нужно заплатить: "+s);
                    paidNominalsArrayList.add(nominals[z]); //добавляем потраченный номинал в массив
                    s = s - nominals[z]; //НУЖНО ЗАМЕНИТЬ НА ДЕЛЕНИЕ
                    System.out.println("+1 купюра номиналом: " + nominals[z] + ", Оставшаяся сумма: " + s);
                    s++;
                    break;
                }
            }
        }
        // Сколько было потрачено РАЗНЫХ купюр? Чтобы узнать
        // помещаем нашу коллекцию в сет (в нём не бывает дубликатов)
        Set<Integer> set = new HashSet<>(paidNominalsArrayList);

        System.out.println("Были потрачено: "+ set.size()+" купюр разного достоинства");
    }
}

Comments

[Dmitry Roo]

Это банальнейшая задача, про которую даже на тостере спрашивали не один раз.

[Dmitry Roo]

Вот, например: https://qna.habr.com/q/1216372

[mayton2019]

У меня - странное дежа-вю. Кажется неделю назад эта задача уже звучала. И где-то лежит ее решение.

Answer 1

[mayton2019]

Ну если к примеру сумма - 1531 рубль то для таких номиналов {500, 100, 50, 10, 5, 2, 1}
нет необходимости вычитать 500-тку три раза. Можно поделить 1531 на 500 и посмотреть
целочисленное частное. Если оно больше 0 - то 500 тку можно было использовать.
Далее - остаток от деления на 500 даст 31. И так далее.

Answer 2

[otdameskapizm]

Это вариация дискретной задачи об укладке рюкзака. Вы здесь будете использовать жадный алгоритм, так как нужно начинать с самой крупной купюры. Просто загуглите это))

Answer 3

[pshevnin]

Если число больше чем N, делишь его на N получаешь количество купюр, с остатком от деления начальной суммы на N проделываешь то же самое для меньшей купюры