Accueil › Python › Combien de façons de régler un montant
Combien de façons de régler un montant
Exercice de la série « Deux pointeurs, comptage, piles et récursivité »avance
Le besoin. La caisse affiche de combien de façons un montant peut être réglé avec les coupons de fidélité disponibles. Deux règlements qui n'utilisent pas les mêmes coupons comptent pour un ; l'ordre des coupons ne compte pas.
Ce qu'on vous demande. Écrivez facons(montant, coupons) qui renvoie
le nombre de combinaisons de coupons dont la somme vaut exactement
montant. Chaque coupon est disponible en quantité illimitée.
| Appel | Résultat attendu |
|---|---|
5, [1, 2, 5] |
4 — 1×5, 5×1, 1+2+2, 1+1+1+2 |
0, [1, 2] |
1 — ne rien prendre est une façon |
3, [5] |
0 |
7, [] |
0 |
Le piège. Compter 1+2 et 2+1 comme deux règlements différents
multiplie le résultat. Pour compter des combinaisons et non des
arrangements, il faut parcourir les coupons dans un ordre fixé et ne
jamais revenir en arrière — d'où un indice de coupon dans l'état de la
récursion.
Cas de test
[5,[1,2,5]][0,[1,2]][3,[5]][7,[]][0,[]][100,[1,5,10,25]]
Votre code s'exécute réellement dans le navigateur, et la correction compare son résultat à celui d'une solution de référence.