时间戳

首页 > 解决方案 > 基于 List 动态创建循环链

java - 基于 List 动态创建循环链

问题描述

我正在练习 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

任何人都可以请赐教。如果我对问题的描述不清楚，我很抱歉。

谢谢

标签： javamathchain

解决方案

虽然使用嵌套循环可以很好地处理固定数量的分隔符，但我建议在一般情况下将解决方案编写为递归函数。

这个问题非常适合动态规划。我的意思是这个问题可以分解成更简单的子问题，这样解决方案自然是用递归来实现的。例如，在您将 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，只有 0 个或一个解。

  • 否则，可能的解决方案可能使 D1 具有 0、1、...、X/D1 中的任意倍数。所以做一个循环 m1 = 0, 1, ..., X/D1，并递归求解具有 X' = X - m1*D1 和剩余除法器 D2, ..., DN 的子问题。这个子问题的除法器少了一个，所以经过足够的递归后，它减少到 N = 1 的情况。

这样就解决了问题。但是请注意，完全递归可能会导致需要解决的子问题的组合数量庞大。因此，对于有效的解决方案，将先前解决的子问题的解决方案存储或“记忆”在一个表中是一个好主意，这样就不会重复工作。

其他想法：

  • 令 Q 为所有除数 {D1, ..., DN} 的最大公约数 (GCD)。如果 X 不能被 Q 整除，则没有解，在这种情况下，我们可以完全跳过上述递归搜索。例如，没有办法用分频器 50、20 和 10 来表示 X = 103。这个 GCD 测试也可以应用于每个子问题，以便一些递归调用可以提前返回。

  • 这个问题是一种丢番图方程，更具体地说，它与Frobenius 硬币问题和 Frobenius 数有关。有一个 mathoverflow 帖子讨论它。

推荐阅读