Niveau Licence Maths 1e ann

Algorithme : décomposition d'une somme

Posté par
mankathada 07-03-17 à 12:41

Bonjour,

J'essaie de résoudre un autre exercice de mon TD en parallèle, mais je suis bloqué aussi.

Je vous donne l'énoncé :

Ecrire un sous programme récursif qui déclare le nombre de façons qu'il existe pour décomposer une somme d'argent S avec des billets de 20, 10 et 5. La valeur des décompositions n'est pas demandé, seulement leur nombre.

On me dit qu'il faut utiliser 3 paramètres :
- S : somme à décomposer

- bmax : la plus grande valeur de billet qu'il reste encore à essayer

- bmin : la plus petite valeur de billet

Perso j'ai du mal à utiliser ces 3 paramètres, pouvez vous me donner des indications svp ?

PS : j'écris mes algos en pseudo code, libre à vous d'écrire dans votre propore langage pseudo code, je saurais m'y retrouver

Merci de votre aide

Posté par re : Algorithme : décomposition d'une somme 07-03-17 à 16:39

salut

s = 5a + 10b + 20c = 5a + 10(b + 2) + 20(c - 1) = 5(a + 2) + 10(b + 1) + 20(c - 1) = 5(a + 4) + 10b + 20(c - 1)

ce qui définit !! la récursivité ...

Posté par re : Algorithme : décomposition d'une somme 07-03-17 à 16:41

plus clairement reprenons :

1/ s est multiple de 5

2/ la récursivité est de déterminer n(s + 5) en fonction de n(s)

Posté par re : Algorithme : décomposition d'une somme 07-03-17 à 21:32

salut,

donc ce que tu veux dire c'est que je dois commencer par diviser la somme par 5 d'abord ?

Posté par re : Algorithme : décomposition d'une somme 08-03-17 à 12:41

Bonjour,

comment on arrive à s = 5(a+4) + 10b + 20(c-1), et comment on l'insère dans l'algo.