Problème de changement de pièce Java Utilisant la Récursivité-ne fonctionne pas
J'ai cherché le code et la logique pour cela et j'ai essentiellement copié le code à partir de https://www.youtube.com/watch?v=k4y5Pr0YVhg et https://www.techiedelight.com/coin-change-problem-find-total-number-ways-get-denomination-coins/
Mais mon programme est faux car il y a certainement plus de 2 façons de faire 2 livres.
public class TwoPounds
{
private static int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};
private static int amount;
private static int count;
public TwoPounds()
{
amount = 2;
count = 0;
}
public static void main(String[] args)
{
TwoPounds run = new TwoPounds();
count = run.combos(amount);
run.printOut();
}
public int combos(int amountIn)
{
if (amountIn == 0)
{
return 1;
}
if (amountIn < 0)
{
return 0;
}
int combosCount = 0;
for(int i = 0; i < coins.length; i++)
{
System.out.println("amountIn now is " + amountIn);
combosCount += combos(amountIn - coins[i]);
}
return combosCount;
}
public void printOut()
{
System.out.println("\n\n\n");
System.out.println("There are " + count + " ways can 2 pounds be made, "
+ "using any number of coins");
System.out.println("\n\n\n");
}
}
Sortie:
There are 2 ways can 2 pounds be made, using any number of coins
2 answers
Vos coins sont en cents (ou en pence, puisque je suppose que vous utilisez des livres GB), donc puisque vous effectuez amountIn - coins[i] avec eux, cela signifie que votre montant est également en cents/pence.
Alors, changez votre montant en:
amount = 200;
Il vaut la peine de prendre un moment pour considérer la dénomination des variables, et comment cela aurait pu aider à identifier - ou même à éviter - ce problème. Les termes "montant " et" Montant " sont ambigus.
Rien dans les mots ne suggère les unités. Donc, aller dans l'habitude de rendre les noms de variables aussi spécifiques et sans ambiguïté que possible - et d'inclure des unités le cas échéant.
Par exemple, si les variables ont été appelées 'amountInPounds', l'erreur devient plus évidente lors de l'écriture de amountInPounds - coins[i]
Maintenant, avant de faire la mise à jour de amount = 200;, sachez que :
1) Il y aura un grand nombre de résultats (200 pennies, 198 pennies+2p), qui prendront un certain temps à parcourir un penny à la fois, plus
2) Votre code est actuellement écrit dans parcourez CHAQUE combinaison ordonnée discrète-par exemple, elle comptera:
- 198 "1 cent" + 1 "2 cent"
- 197 "1 cent" + 1 "2 cent" + 1 "1 cent"
- 196 "1 cent" + 1 "2 cent" + 2 "1 cent"
- 195 "1 cent" + 1 "2 cent" + 3 "1 cent" etc
Encore une fois, beaucoup trop de temps d'exécution. Ce que vous voulez, c'est ne pas démarrer votre for(int i = 0; i < coins.length; i++) à partir de zéro à chaque fois, mais plutôt ajouter un paramètre supplémentaire à combos - donc quelque chose comme:
public int combos (int amountIn, int startCoin)
{
// blah ... existing code ... blah
for(int i = startCoin; i < coins.length; i++)
{
System.out.println("amountIn now is " + amountIn);
combosCount += combos(amountIn - coins[i], i);
}
Enfin, comme je l'ai dit avant, 200 se traduira par de grands nombres qui seront effectivement impossibles pour vous de confirmer l'exactitude, alors commencez plutôt par de petites quantités que vous pouvez vérifier.
Cet algorithme permet l'utilisation de plusieurs pièces de la même dénomination, il y a donc 2 façons de faire de 2 livres:
- {1, 1}
- {2}