Formations — 1 037 leçons en français

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

Écrire le code et le faire exécuter →

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.

La leçon qui prépare cet exercice

Les autres exercices de « Deux pointeurs, comptage, piles et récursivité »