对于这个问题，我必须编写一种方法，当用户以美分计入货币金额时，我必须以String格式输出带有角钱，镍币和美分的所有可能组合。我只能使用递归，而不能使用任何类型的循环或集合（即数组，列表，堆栈等）。该代码应该可以工作，但是由于某种原因它不会输出所有组合，因此会丢失以下输出：“ 0d 3n 7p”和“ 0d 0n 17p”输出。
package Assignement02;
public class Coins {
public static String ways (int money) {
System.out.println("Enter an amount in cents:");
System.out.println(money);
System.out.println("This amount can be changed in the following ways:");
if(money == 0) {
return "there are no ways to change that amount";
} else {
return waysHelper(0, 0, 0, money);
}
}
public static String waysHelper(int countd, int countn, int countp, int money) {
if(money >= 10) {
countd++;
return waysHelper(countd, countn, countp, money - 10);
} else if (money >= 5) {
countn++;
return waysHelper(countd, countn, countp, money - 5);
} else {
String s = " " + countd + "d, " + countn + "n, " + money + "p";
int orig = 10*countd + 5*countn + money;
return counterHelper(orig, countd, countn, money, s);
}
}
public static String counterHelper(int money, int countd, int countn, int countp, String s) {
if(countp == money) {
s = s + s + "\n " + countd + "d, " + countn + "n, " + countp + "p";
}
if(countd > 0) {
if(countn > 0) {
countn--;
countp = countp + 5;
s = s + "\n " + countd + "d, " + countn + "n, " + countp + "p";
counterHelper(money, countd, countn, countp, s);
}
countd--;
countn = countn + 2;
s = s + "\n " + countd + "d, " + countn + "n, " + countp + "p";
counterHelper(money, countd, countn, countp, s);
}
if(countn > 0) {
countn--;
countp = countp + 5;
s = s + "\n " + countd + "d, " + countn + "n, " + countp + "p";
counterHelper(money, countd, countn, countp, s);
}
if(countn > 0) {
countn--;
countp = countp + 5;
s = s + "\n " + countd + "d, " + countn + "n, " + countp + "p";
counterHelper(money, countd, countn, countp, s);
}
return s;
}
public static void main(String[] args) {
System.out.print(ways(17));
}
}
输出：
输入以美分表示的金额：17可以通过以下方式更改此金额：1d，1n，2p1d，0n，7p0d，2n，7p0d，1n，12p0d，0n，17p
如果您使用37美分作为测试用例，您的问题将会更加明显。您永远不会有两个以上镍的例子，因为您先转向角钱，再也不会回来。您只能通过额外的if（countn ...）步骤来弥补这一点，但我不太了解。
而不是让wayHelper返回一个字符串，您应该传入一个字符串列表（或仅将其中一个作为成员变量），并且每次对WaysHelper的调用都会将一些字符串添加到列表中。如果您还没有完成列表，则可以在一个大的String中构建它，但是您必须小心，因为这时您必须返回它，捕获每个修改的版本，并始终将其传递。使用列表，您可以传递它，并且您调用的方法可以对其进行修改。
递归执行而不是使用循环的整个想法有点愚蠢，但是请注意，尾递归和循环本质上是同一回事。您可以利用这一点。
import java.util.ArrayList;
import java.util.List;
public class MoneyChangers {
public static void main(String[] args) {
List<String> results = new ArrayList<>();
getCombos(results, 28, 0);
System.out.println(results);
}
public static void getCombos(List<String> results, int target, int dimesCount) {
int pennies = target - 10 * dimesCount;
if (pennies < 0) {
return;
}
getCombosForDimesFixed(results, target, dimesCount, 0);
// This is tail recursion, which is really just a loop. Do it again with one more dime.
getCombos(results, target, dimesCount+1);
}
private static void getCombosForDimesFixed(List<String> results, int target, int dimesCount, int nickelsCount) {
int pennies = target - 10 * dimesCount - 5 * nickelsCount;
if (pennies < 0) {
return;
}
results.add("\n" + dimesCount + "d, " + nickelsCount + "n, " + pennies + "p");
getCombosForDimesFixed(results, target, dimesCount, nickelsCount+1); // tail recursion again
}
}
我相信您通常对问题细分有正确的想法。这就是我对您的解释的看法：
以您的WaysHelper为第一部分，而您的counterHelper为第二部分。
在下面找到我的解决方案，并内嵌评论：
public class Coins {
public static void main(String[] args) {
System.out.print(findAllCoinCombinationsForPennies(17));
}
public static String findAllCoinCombinationsForPennies(int money) {
System.out.println("Enter an amount in cents:");
System.out.println(money);
System.out.println("This amount can be changed in the following ways:");
if(money <= 0) {
return "there are no ways to change that amount";
} else {
return findAllCoinCombinations(0, 0, money);
}
}
// break down the initial amount into the largest coinage to start (i.e. 17 pennies will be 1d, 1n, 2p)
private static String findAllCoinCombinations(int dimes, int nickels, int pennies) {
if(pennies >= 10) {
// we can still convert pennies to another dime
return findAllCoinCombinations(dimes + 1, nickels, pennies - 10);
} else if (pennies >= 5) {
// we can still convert pennies to another nickel
return findAllCoinCombinations(dimes, nickels + 1, pennies - 5);
} else {
// base case where we have the largest coins (can't convert pennies to any more dimes or nickels)
return findCoinCombinationsFor(dimes, nickels, pennies, "");
}
}
// find all combinations of coins recursively
private static String findCoinCombinationsFor(int dimes, int nickels, int pennies, String output) {
// each call is another combination of coins, add that combination to our result output
output += "\n " + dimes + "d, " + nickels + "n, " + pennies + "p";
if (dimes > 0) {
// if we have dimes, break the dime down into 2 nickels
return findCoinCombinationsFor( dimes - 1, nickels + 2, pennies, output);
} else if (nickels > 0) {
// if we have nickels break each nickel down into 5 pennies
return findCoinCombinationsFor( dimes, nickels - 1, pennies + 5, output);
} else {
// we have no more dimes or nickels, return the accumulated output
return output;
}
}
}