Décomposition en billets et/ou pièces

Version imprimable

Bonjour,
j'ai un vecteur =(500;200;100;50;10;5)
je désire afficher la décomposition de la somme en billets et/ou en pièces mais je n'arrive pas a transcrire ce qui suit en une procédure algorithmique.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
comparer le montant de la monnaie avec les différents éléments du vecteur argent.
Exemple : si la monnaie à changer est de 1800 :
-	Comparaison du montant 1800 avec les éléments dans le vecteur Argent un après un. Dés que l’élément dans le vecteur courant en cours est inférieur au montant, faire une division et garder toutes les infos dans des variables.
1800 > 500 oui
Division de 1800 par 500 --> 1800/500 = 3  et il reste 300 (garder les information resultat=3, reste=300 et element_vecteur_courant=500 dans des variables)
-	Comparaison du reste 300 avec les éléments dans le vecteur Argent un après un. Dés que l’élément dans le vecteur courant en cours est inférieur au montant, faire une division et garder toutes les infos dans des variables
300 > 500 non. Je passe au vecteur suivant
300 > 200 Oui
Division de 300 par 200 --> 300/200 = 1  et il reste 100 (garder les information resultat=1, reste=100 et element_vecteur_courant=200 dans des variables)
-	Comparaison du reste 100 avec les éléments dans le vecteur Argent un après un. Dés que l’élément dans le vecteur courant en cours est inférieur au montant, faire une division et garder toutes les infos dans des variables
100 > 500 non. Je passe au vecteur suivant
100 > 200 non. Je passe au vecteur suivant
100 > 50 Oui
Division de 100 par 50 --> 100/50 = 2  et il reste 0 (garder les information resultat=2, reste=0 et element_vecteur_courant=50 dans des variables)
----
 
 
Afficher le resultat 
3*500 + 1*200 + 2*50

Merci

04/11/2010, 20h08
Sehnsucht

Bonsoir,

Quelques détails ; dans ton raisonnement tu as oublié le passage par l'élément 100 de ton vecteur (tu passes de 200 à 50) c'est juste un oubli mais ça fausse le résultat qui devrait être:
1800 = 3 * 500 + 1 * 200 + 1 * 100

Autre point le reste d'une division étant strictement inférieur au diviseur, il n'est donc pas besoin de revérifier celui-ci dans l'étape suivante et tu peux donc ainsi commencer par tester directement l'élément suivant de ton vecteur.
Comme l'explication n'est pas nécessairement claire j'illustre mon propos:

Citation:

1800 > 500 oui
1800 / 500 = 3 (reste 300 qui est forcément inférieur à 500)

300 > 200 oui
etc.

Quant au raisonnement en lui-même il a l'air plutôt clair, quel est exactement ton souci dans la transcription en algorithme ?

Cordialement !
04/11/2010, 20h15
netchou

Bonsoir,
mon soucis est la transcription sous forme d'algorithme de mon raisonnement.
Dois-je utiliser une boucle tantque pour rechercher la valeur du vecteur qui divise ,
comment la mettre en place etc..
afficher le résultat...

cordialement .
merci

Il faut déjà savoir que plusieurs "algorithmes" peuvent répondre au problème (le choix pouvant dépendre entre autre des habitudes de celui qui rédige, habitude à certains langages/paradigmes)

personnellement je partirais sur une simple boucle FOR, schématiquement:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Pour chaque élément du vecteur quantité = montant / élément (division entière) montant = montant modulo élément stocker couple (quantité, élément) Fin Pour Exemple: montant = 1100 ; vecteur = {500; 200; 100} tableau de "couples": resultat 1ère itération: élément = 500 quantité = 1100 / 500 = 2 montant = 1100 % 500 = 100 resultat = {{2; 500}} 2ème itération: élément = 200 quantité = 100 / 200 = 0 montant = 100 % 200 = 100 resultat = {{2; 500}; {0; 200}} 3ème itération: élément = 100 quantité = 100 / 100 = 1 montant = 100 % 100 = 0 resultat = {{2; 500}; {0; 200}; {1; 100}} après utilisation par une méthode qui ferait un affichage textuel 2 x 500 + 0 x 200 + 1 x 100 ou (si on suppose que l'on affiche pas les quantités nulles) 2 x 500 + 1 x 100
Notes: Juste au cas où le modulo(%) représente le reste de la division.
Il n'est pas obligatoire de stocker les couples, on ne peut garder que les quantités et re-parcourir le vecteur pour faire l'association ensuite.
De même si c'est pour un affichage textuel on peut directement construire la chaîne dans la boucle par concaténation successives, mais cela perdra en généricité contrairement au cas présenté qui n'est pas dépendant de la manière dont sera utilisé le "tableau" (quelle que soit sa forme) résultat.
J'ai aussi pris le parti de conserver les quantités nulles pour rester dans le cadre "exhaustif" cela peut aussi être sujet à modification (un simple test suffit) selon le contexte, de même on pourrait aussi "optimiser" un peu, en rajoutant en fin de boucle une condition du style "si montant = 0 alors quitter boucle" après avoir peser le pour et le contre de savoir si un test en plus effectué à chaque itération sera probant en terme de performances

Cordialement !

04/11/2010, 20h50
netchou

merci de m'éclairer.

Cordialement garnd Merci.:ccool:

Je corrige qqs erreurs..

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Montant (réel, saisi)
Arrondi fonction, réel, calculé
Résultat (tableau [1..j, 1..i] de réel, calculé)
Quantité (entier, calculé)
 
Procédure_Change(E: Montant: réel, S : Résultat: réel) de réel
Début
Pour i de 1 à taille vecteur(i) Faire
Quantité←Montant DIV (i)
Si Quantité←0 Alors
i<-i+1
Fin Si
Quantité←Montant DIV (i)
Montant ← Montant MOD (i)
Résultat (j, i)
Fin Pour
 
Pour i de 1 à taille vecteur(i) Faire
Afficher (Résultat [1, 1],"+", Résultat [j, i])
Fin Pour
Fin

est-ce que c'est juste ?
Cordialement

Bonsoir,

J'avoue avoir un peu de mal avec la notation utilisée, je vais tenter de transcrire ma pensée en suivi ce schéma (je ne garantis pas le résultat :aie:)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
Montant (réel, saisi)
Arrondi (fonction E: réel, S: entier, défini ailleurs)
Montant_Arrondi (entier, calculé)
Vecteur (tableau [1 .. n] d'entiers, défini ailleurs)
Quantité (entier, calculé)
Résultat (tableau [1 .. taille vecteur][2] d'entiers, calculé)
 
Procedure_Change(E: Montant_Arrondi: entier, S: Résultat: tableau[][] d'entiers)
    Pour i de 1 à taille(Vecteur) Faire
        Quantité ← Montant_Arrondi DIV Vecteur[i]
        Montant ← Montant MOD Vecteur[i]
 
        Ajouter à Resultat: [Quantité, Vecteur[i]]
 
        Si Montant = 0 Alors
            Quitter Pour
        Fin Si
    Fin Pour
 
    Renvoyer Resultat
Fin Procédure
 
Procédure_Affichage(E: Résultat: tableau[][] d'entiers, S: N/A)
    Pour i de 1 à taille(Resultat) Faire
        Note Resultat[n][1] représente donc la quantité et Resultat[n][2] représente la valeur du billet
        Afficher (Resultat[i][1], "*", Resultat[i][2])
    Fin Pour
Fin Procédure

Bien sûr cela reste schématique (et approximatif vu mon peu d'habitude à rédiger du pseudo-code ainsi)

Cordialement !

05/11/2010, 18h07
netchou

Merci a toi Sehnsucht.
je vais essayer de ne faire q'une procédure en intégrant "l'affichage" a "change".

Cordialement.