基于列表动态创建循环链
Creating a chain of loops dynamically based on a 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
谁能赐教。如果我对问题的描述不清楚，请见谅。
谢谢
虽然嵌套循环可以很好地处理固定数量的除法器，但我建议在一般情况下将解决方案编写为递归函数。
这个问题很适合dynamic programming。我的意思是，问题可以分解成更简单的子问题，这样解决方案自然就用递归实现了。例如，在您将 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 的情况。
问题解决了。但是请注意，完全递归可能会导致需要解决的子问题的组合数量非常庞大。因此，为了获得有效的解决方案，最好将先前解决的子问题的解决方案存储或 "memoize" 到 table 中，这样就不会重复工作。
其他想法：
令 Q 为所有除数 {D1, ..., DN} 的最大公约数 (GCD)。如果 X 不能被 Q 整除，则没有解决方案，在这种情况下我们可以完全跳过上述递归搜索。例如。无法用除数 50、20 和 10 来表示 X = 103。此 GCD 测试也可以应用于每个子问题，以便一些递归调用可以 return 提早。
这个问题属于Diophantine equation, more specifically, it is related to the Frobenius coin problem and Frobenius numbers. There is a mathoverflow post讨论
我正在练习 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
谁能赐教。如果我对问题的描述不清楚，请见谅。
谢谢
虽然嵌套循环可以很好地处理固定数量的除法器，但我建议在一般情况下将解决方案编写为递归函数。
这个问题很适合dynamic programming。我的意思是，问题可以分解成更简单的子问题，这样解决方案自然就用递归实现了。例如，在您将 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 的情况。
问题解决了。但是请注意，完全递归可能会导致需要解决的子问题的组合数量非常庞大。因此，为了获得有效的解决方案，最好将先前解决的子问题的解决方案存储或 "memoize" 到 table 中，这样就不会重复工作。
其他想法：
令 Q 为所有除数 {D1, ..., DN} 的最大公约数 (GCD)。如果 X 不能被 Q 整除，则没有解决方案，在这种情况下我们可以完全跳过上述递归搜索。例如。无法用除数 50、20 和 10 来表示 X = 103。此 GCD 测试也可以应用于每个子问题，以便一些递归调用可以 return 提早。
这个问题属于Diophantine equation, more specifically, it is related to the Frobenius coin problem and Frobenius numbers. There is a mathoverflow post讨论