Trouvez toutes les combinaisons de pièces lorsqu'on leur donne une valeur en dollars

Question

J'ai trouvé un morceau de code que j'ai écrit pour un entretien prep quelques mois.

Selon le commentaire que j'ai eu, c'était d'essayer de résoudre ce problème:

Compte tenu de certains dollar de la valeur en cents (par exemple 200 = 2 dollars, 1000 = 10 dollars), trouver toutes les combinaisons de pièces qui composent la valeur du dollar. Il y a seulement penny, nickel, dime, et par trimestre. (un trimestre = 25 cents, pièce de dix cents = 10 cents, nickel = 5 cents, penny = 1 cent)

Par exemple, si 100 a été donné, la réponse devrait être...
4 trimestre(s) 0 centime(s) 0 nickel(s), 0 pièces d'un cent
3 trimestre(s) de 1 centime(s) 0 nickel(s) 15 centimes
etc.

Cela peut être résolu à la fois itérative et récursive manières, je crois. Ma solution récursive est assez buggé, et je me demandais comment d'autres personnes pourraient résoudre ce problème. La partie la plus difficile de ce problème a été pour la rendre aussi efficace que possible.

Mise à JOUR
Faire de ce fil dans un wiki de la communauté, parce qu'apparemment, nous avons rassemblé de nombreuses implémentations différentes :)

Answer 1

J'ai regardé dans cette fois il y a longtemps, et vous pouvez lire mon petit article sur elle. Voici le Mathematica source.

En utilisant des fonctions génératrices, vous pouvez obtenir une forme fermée constante de temps de la solution au problème. Graham, Knuth, et Patashnik du Béton Mathématiques est le livre pour cela, et contient une discussion assez approfondie du problème. Essentiellement, vous définissez un polynôme où *n*th coefficient est le nombre de façons de faire des changements pour la n de dollars.

Pages 4 et 5 de l'article montrent comment vous pouvez utiliser Mathematica (ou de toute autre pratique système de calcul formel) pour calculer la réponse pour 10^10^6 dollars en quelques secondes en trois lignes de code.

(Et ce fut assez long, il ya que c'est un couple de secondes sur un Pentium 75Mhz...)

Answer 2

Fonction scala propre:

 def countChange(money: Int, coins: List[Int]): Int =
  if (money == 0) 1
  else if (coins.isEmpty || money < 0) 0
  else countChange(money - coins.head, coins) + countChange(money, coins.tail)
 

Answer 3

Je serais favorable à une solution récursive. Vous avez une certaine liste de dénominations, si le plus petit, on peut diviser uniformément tout en restant montant en devise, cela devrait fonctionner correctement.

Fondamentalement, vous vous déplacez de la plus grande à la plus petite des dénominations.
De manière récursive,

1. Vous avez actuellement un total de remplissage, et une plus grande dénomination (avec plus de 1 gauche). Si il ya seulement 1 dénomination de la gauche, il n'y a qu'une seule façon de remplir le total. Vous pouvez utiliser 0 pour k copies de votre dénomination telle que k * cur dénomination <= total.
2. Pour les 0 à k, appeler la fonction avec la modification de total et de la nouvelle plus grande dénomination.
3. Ajouter les résultats de 0 à k. C'est le nombre de façons que vous pouvez remplir votre total de la valeur actuelle sur le bas. De retour de ce nombre.

Voici ma version de python de votre problème, pour 200 cents. Je reçois 1463 façons. Cette version imprime toutes les combinaisons et le décompte final total.

#!/usr/bin/python

# find the number of ways to reach a total with the given number of combinations

cents = 200
denominations = [25, 10, 5, 1]
names = {25: "quarter(s)", 10: "dime(s)", 5 : "nickel(s)", 1 : "pennies"}

def count_combs(left, i, comb, add):
    if add: comb.append(add)
    if left == 0 or (i+1) == len(denominations):
        if (i+1) == len(denominations) and left > 0:
            comb.append( (left, denominations[i]) )
            i += 1
        while i < len(denominations):
            comb.append( (0, denominations[i]) )
            i += 1
        print " ".join("%d %s" % (n,names[c]) for (n,c) in comb)
        return 1
    cur = denominations[i]
    return sum(count_combs(left-x*cur, i+1, comb[:], (x,cur)) for x in range(0, int(left/cur)+1))

print count_combs(cents, 0, [], None)

Answer 4

Fonction Scala:

 def countChange(money: Int, coins: List[Int]): Int = {

def loop(money: Int, lcoins: List[Int], count: Int): Int = {
  // if there are no more coins or if we run out of money ... return 0 
  if ( lcoins.isEmpty || money < 0) 0
  else{
    if (money == 0 ) count + 1   
/* if the recursive subtraction leads to 0 money left - a prefect division hence return count +1 */
    else
/* keep iterating ... sum over money and the rest of the coins and money - the first item and the full set of coins left*/
      loop(money, lcoins.tail,count) + loop(money - lcoins.head,lcoins, count)
  }
}

val x = loop(money, coins, 0)
Console println x
x
}
 

Answer 5

Voici un code C ++ absolument simple pour résoudre le problème qui demandait que toutes les combinaisons soient affichées.

 #include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    if (argc != 2)
    {
    	printf("usage: change amount-in-cents\n");
    	return 1;
    }

    int total = atoi(argv[1]);

    printf("quarter\tdime\tnickle\tpenny\tto make %d\n", total);

    int combos = 0;

    for (int q = 0; q <= total / 25; q++)
    {
    	int total_less_q = total - q * 25;
    	for (int d = 0; d <= total_less_q / 10; d++)
    	{
    		int total_less_q_d = total_less_q - d * 10;
    		for (int n = 0; n <= total_less_q_d / 5; n++)
    		{
    			int p = total_less_q_d - n * 5;
    			printf("%d\t%d\t%d\t%d\n", q, d, n, p);
    			combos++;
    		}
    	}
    }

    printf("%d combinations\n", combos);

    return 0;
}
 

Mais je suis assez intrigué par le sous-problème du calcul du nombre de combinaisons. Je soupçonne qu'il existe une équation fermée pour cela.