我在练习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
谁能开导我一下吗。如果我对这个问题的描述不清楚，我很抱歉。
谢谢
1条答案
按热度按时间exdqitrt1#
虽然使用嵌套循环可以很好地接近固定数量的除法器，但对于一般情况，我建议将解决方案编写为递归函数。
这个问题很适合于动态规划。我的意思是，这个问题可以分解成更简单的子问题，通过这种方式，解决方案自然地用递归实现。例如，在将100表示为50、20和10的倍数之和的示例中，发现三种解决方案都使用一个50：
把这个问题看作是解决了一个子问题，即如何将值50表示为20和10的倍数（即50等于10）
20*0 + 10*5,20*1 + 10*3以及20*2 + 10*1). 所以你可以在这个意义上分而治之。设x为表示的数字（如100），d1，d2。。。把隔板拆了。以下是可能的概要：
如果只有一个除法器，n=1，那么很简单：根据d1是否除法x，只有零或一个解。
否则，可能的解决方案可能具有d1，具有0，1，…，x/d1的任意倍数。所以做一个循环m1=0，1，…，x/d1，然后递归地求解子问题x'=x-m1*d1和剩余的除数d2，…，dn。这个子问题的除法器少了一个，所以经过足够的递归，它就减少到n=1的情况。
这就解决了问题。不过，请注意，完全递归可能会导致大量子问题的组合求解。因此，对于有效的解决方案，最好将以前解决的子问题的解决方案存储或“记忆”在一个表中，这样工作就不会重复。
其他想法：
设q是所有除数{d1，…，dn}中的最大公约数（gcd）。如果x不能被q整除，那么就没有解，在这种情况下我们可以完全跳过上面的递归搜索。e、 g.无法用50、20和10等分表示x=103。这个gcd测试也可以应用于每个子问题，以便一些递归调用可以提前返回。
这个问题是一类丢番图方程，更具体地说，它与frobenius硬币问题和frobenius数有关。有个帖子在讨论这个问题。