Блог

Я занимаюсь Java, и я пытался создать программу для вычисления количества способов деления числа с использованием заданного количества разделителей.

Например:

100 — это число, а разделители равны 50,20,5. Каковы возможные разделения.

Ответ будет:

 Amount of 50 : 0, Amount of 20 : 0, Amount of 10 : 10
Amount of 50 : 0, Amount of 20 : 1, Amount of 10 : 8
Amount of 50 : 0, Amount of 20 : 2, Amount of 10 : 6
Amount of 50 : 0, Amount of 20 : 3, Amount of 10 : 4
Amount of 50 : 0, Amount of 20 : 4, Amount of 10 : 2
Amount of 50 : 1, Amount of 20 : 0, Amount of 10 : 5
Amount of 50 : 1, Amount of 20 : 1, Amount of 10 : 3
Amount of 50 : 1, Amount of 20 : 2, Amount of 10 : 1
Amount of 50 : 2
 

Я написал код, который запрашивает у пользователя сумму и 3 делителя. Теперь я пытаюсь выяснить, есть ли способ динамического создания кода для стольких разделителей, сколько захочет пользователь. Код в некотором смысле очень повторяющийся, и существует определенный шаблон для добавления другого разделителя, но я не могу понять, как реализовать это динамическое изменение в коде.

Первый код, который я придумал для этого, следующий:

 public class Test2 {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        System.out.println("Insert the amount:");
        int amount = scanner.nextInt();
        List<Integer> dividers = new ArrayList<>();
        System.out.println("Insert the first divider:");
        int tempDivider = scanner.nextInt();
        if (!dividers.contains(tempDivider)) {
            dividers.add(tempDivider);
        }

        while (dividers.size()<3) {
                System.out.println("Insert the next divider: ("   (3-dividers.size())   " more to go)");
                tempDivider = scanner.nextInt();
            if (!dividers.contains(tempDivider)) {
                dividers.add(tempDivider);
            }
        }

        dividers.sort(Collections.reverseOrder());
        System.out.print("Dividers are: ");
        System.out.println(dividers);

        int getal1 = dividers.get(0);
        int getal2 = dividers.get(1);
        int getal3 = dividers.get(2);

        int fiftyAmount = amount / getal1;
        int fiftyRemainder = amount % getal1;
        for (int i = 0; i <= fiftyAmount; i  ) {
            int currentFiftyAmount = amount - (getal1 * i);
            int twentyAmount = currentFiftyAmount / getal2;
            int twentyRemainder = currentFiftyAmount % getal2;
            if (twentyAmount == 0) {
                StringBuilder output = new StringBuilder();
                output.append("Amount of "   getal1   " banknotes: "   i);
                if (fiftyRemainder != 0) output.append(", Remainder: "   fiftyRemainder);
                System.out.println(output);
            } else {
                for (int j = 0; j <= twentyAmount; j  ) {
                    int currentTwentyAmount = currentFiftyAmount - (getal2 * j);
                    int tenAmount = currentTwentyAmount / getal3;
                    int tenRemainder = currentTwentyAmount % getal3;
                    if (tenAmount == 0) {
                        StringBuilder output = new StringBuilder();
                        output.append("Amount of "   getal1   " banknotes: "   i   ", Amount of "   getal2   " banknotes: "   j);
                        if (tenRemainder != 0) output.append(", Remainder: "   twentyRemainder);
                    } else {
                        StringBuilder output = new StringBuilder();
                        output.append("Amount of "   getal1   " banknotes: "   i   ", Amount of "   getal2   " banknotes: "   j  
                                ", Amount of "   getal3   " banknotes: "   tenAmount);
                        if (tenRemainder != 0) output.append(", Remainder: "   tenRemainder);
                        System.out.println(output);
                    }
                }
            }
        }
    }
}
 

Я попытался сделать это более абстрактным, чтобы найти способ автоматизировать создание дополнительных разделительных циклов, но я не могу понять это.
Более абстрактная версия, которую я написал, выглядит следующим образом:

 import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        System.out.println("Insert the amount:");
        int amount = scanner.nextInt();
        List<Integer> dividers = new ArrayList<>();
        System.out.println("Insert the first divider:");
        dividers.add(scanner.nextInt());

        int divider;
        while (dividers.size()<2) {
            System.out.println("Insert the next divider: ("   (2-dividers.size())   " more to go)");
            divider = scanner.nextInt();
            if (!dividers.contains(divider)) {
                dividers.add(divider);
            }
        }
        dividers.sort(Collections.reverseOrder());
        System.out.print("Dividers are: ");
        System.out.println(dividers);


        int divided1Amount = amount / dividers.get(0);
        int divided1Remainder = amount % dividers.get(0);
        for (int i = 0; i <= divided1Amount; i  ) {
            int currentDivided1Amount = amount - (dividers.get(0) * i);
            int divided2Amount = currentDivided1Amount / dividers.get(1);
            int divided2Remainder = currentDivided1Amount % dividers.get(1);
            if (divided2Amount == 0) {
                StringBuilder output = new StringBuilder();
                output.append(dividers.get(0)   ":"   i);
                if (divided1Remainder != 0) {
                    output.append(", Remainder: "   divided1Remainder);
                }
                System.out.println(output);
            } else {
                StringBuilder output = new StringBuilder();
                output.append(dividers.get(0)   ":"   i   ","   dividers.get(1)   ":"   divided2Amount);
                if (divided2Remainder != 0) {
                    output.append(", Remainder: "   divided2Remainder);
                }
                System.out.println(output);
            }
        }
    }
}
 

Это также доступно на GitHub: https://github.com/realm1930/rekendin/blob/master/src/Main.java

Может кто-нибудь, пожалуйста, просветите меня. Прошу прощения, если я не совсем ясно описал проблему.

Спасибо

Хотя к фиксированному числу разделителей можно хорошо подойти с помощью вложенных циклов, я предлагаю для общего случая записать решение в виде рекурсивной функции.

Эта проблема хорошо подходит для динамического программирования. Под этим я подразумеваю, что проблему можно разбить на более простые подзадачи, и таким образом решение естественным образом реализуется с помощью рекурсии. Например, в вашем примере выражения 100 в виде суммы, кратной 50, 20 и 10, найдено три решения, все из которых используют один 50:

 Amount of 50 : 1, Amount of 20 : 0, Amount of 10 : 5
Amount of 50 : 1, Amount of 20 : 1, Amount of 10 : 3
Amount of 50 : 1, Amount of 20 : 2, Amount of 10 : 1
 

Посмотрите на это как на решение подзадачи поиска способов выражения значения 50 в виде кратных 20 и 10 (то есть 50 равно 20*0 10*5 , 20*1 10*3 и 20*2 10*1 ). Таким образом, вы можете разделить и победить исходную проблему в этом смысле.

Пусть X — число (например, 100) для выражения, и D1, D2, … DN разделители. Вот возможный план:

• Если есть только один разделитель, N = 1, это просто: есть только ноль или одно решение в зависимости от того, делит ли D1 X.
• В противном случае возможные решения могут иметь D1 с любым кратным от 0, 1, …, X / D1 . Итак, создайте цикл m1 = 0, 1, …, X / D1 и рекурсивно решите подзадачу, имеющую X’ = X — m1 * D1 и оставшиеся делители D2, …, DN. У этой подзадачи на один делитель меньше, поэтому после достаточного количества рекурсий она сводится к случаю N = 1.

Это решает проблему. Обратите внимание, однако, что полная рекурсия может привести к комбинаторно огромному количеству решаемых подзадач. Поэтому для эффективного решения рекомендуется хранить или «запоминать» решения ранее решенных подзадач в таблице, чтобы работа не повторялась.

Другие мысли:

• Пусть Q — наибольший общий делитель (GCD) всех делителей {D1, …, DN}. Если X не делится на Q, то решений нет, и в этом случае мы можем полностью пропустить приведенный выше рекурсивный поиск. Например. невозможно выразить X = 103 с разделителями 50, 20 и 10. Этот тест GCD также может быть применен к каждой подзадаче, чтобы некоторые рекурсивные вызовы могли возвращаться раньше.
• Эта проблема является разновидностью диофантова уравнения, более конкретно, она связана с проблемой монеты Фробениуса и числами Фробениуса. Существует сообщение mathoverflow, в котором обсуждается это.