Récursivité dans un système "monnayeur"

Version imprimable

11/10/2006, 22h44
TiteFleur

Récursivité dans un système "monnayeur"

Bonsoir,

Voilà je dois réaliser l'algorithme et le codage en Pascal d'un "monayeur non optimisé". Ce que j'entends par là c'est qu'on dispose de pièces de monnaie (2€, 1€, 0,5€, 0,2€, 0,1€, 0,05€, 0,02€, 0,01€) et que l'on doit donner le nombre de possibilités de faire l'appoint. J'appelle "non optimisé" le fait que le monnayeur ne doit pas calculer la meilleure façon de rendre l'argent (avec le moins de pièces possibles), mais qu'il doit nous donner toutes les possibilités. Et c'est bien là que je bloque.
J'ai tenté de découvrir une formule générale de récurrence mais je ne pense pas qu'il faille passer par là : en effet c'est un exercice sur la récursivité, qui a pour suite le même monnayeur mais cette fois avec un nombre limité pour chaque pièce.

Voilà, je comprends bien comme "optimiser" la machine pour qu'elle rende le moins de pièces possibles, mais je ne sais pas comment faire pour le reste, ça fait des heures que je suis dessus et je bloque :roll:

Un ptit coup de pouce serait le bienvenu... merci d'avance.

Bonne soirée,
TiteFleur
12/10/2006, 10h08
HRS

votre problème est d'ordre algorithmique et non de codage PASCAL ==> post déplacé dans la rubrique "algorithmes"
12/10/2006, 13h34
Graffito

Bonjour,

Définissons une solution intermédiaire de niveau N+1 comme une solution comportant une combinaison de pièces toutes supérieures à m centimes d'euros + une somme S résiduelle.

A partir d'une solution intermédiaire de niveau N'=N+1 (example m'=50cts), et avec une somme résiduelle égale à S' on générera pour le niveau N (example n=20cts) X solutions intermédiaires telles que X=S'/m et S=S'-i*n, i variant de 0 à X.

On commence par une solution intiale unique avec S=somme à rendre et on traite chaque niveau N (N=1 m=200, N=2 m=100, N=3 m=50 .... m=1).

Bonjour,

trouver toute les solutions va souvent avec récurrence. :(
Il te faut donc une procédure du style :

Code:

1
2
3
4
5
6
7
8
9
10
11
 
procedure(Somme)
debut
si somme = rendu alors ecrire resultat et retourner
si somme > rendu alors retourner
 
Ajouter une piece de type 1 et appeler procedure(Somme+valeur Type 1).
Ajouter une piece de type 2 et appeler procedure(Somme+valeur Type 2).
...
Ajouter une piece de type N et appeler procedure(Somme+valeur Type N).
Fin

17/10/2006, 14h32
Trap D

Une solution ne serait-elle pas de se dire :
mon monnayeur n'a que des pièces de 0,01 €, quelle solution ,
Il n'a qu 'une pièce de 0,02 €, quelle solution
Il a 2 pièces de 0,02€, il a 3 pièces, quand on a tout epuisé pour les pièces de 0,02 €, on recommence tout le cycle avec une pièce de 0,05 €, puis deux pièces de 0,05 € ...
On peut ainsi trouver une méthode itérative et après pourquoi pas récursive.

Citation:

Envoyé par ToTo13

Bonjour,

trouver toute les solutions va souvent avec récurrence. :(
Il te faut donc une procédure du style :

Code:

1
2
3
4
5
6
7
8
9
10
11
 
procedure(Somme)
debut
si somme = rendu alors ecrire resultat et retourner
si somme > rendu alors retourner
 
Ajouter une piece de type 1 et appeler procedure(Somme+valeur Type 1).
Ajouter une piece de type 2 et appeler procedure(Somme+valeur Type 2).
...
Ajouter une piece de type N et appeler procedure(Somme+valeur Type N).
Fin

Il manque juste à se limiter au nombre de pièces disponibles et à éviter de noter plusieurs fois la même combinaison.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
Valeurs[NombreDeTypeDePièces] = {0.1, 0.2, 0.5, 0.10 ...}
NbPiecesDispo[NombreDeTypeDePièces] = {10, 5, 6 ...}
NbPieces[NombreDeTypeDePièces] = {0, 0, ...}
 
procedure(Somme, Type)
debut
   si Somme = rendu alors ecrire NbPieces et retourner
   si Somme > rendu alors retourner
 
   Pour i de Type à NombreDeTypeDePièces
      Si NbPieces[i] < NbPiecesDispo[i] alors
         NbPieces[i] = NbPieces[i] + 1
         procedure(Somme+Valeurs[i], i)
         NbPieces[i] = NbPieces[i] - 1
      fin si
   fin pour
fin

Il y a un peu trop de variables globales mais c'est pour le principe.

17/10/2006, 18h35
j.p.mignot

J'ai donné un code source ( en C ) sur ce forum qui resoud exactement ce probleme
voir
http://www.developpez.net/forums/sho...d.php?t=210755
dans

Citation:

A.X1 + B.X2 + ... + Y.Xn = TOTAL

if suffit de prendre A=200, B=100 D=50 E=20 F=10 G=5 H=2 et I=1, limiter le système à 9 variables et mettre total en "centi" Euro
Le code, autant que je me souvienne, devrait donner ici des doublons à supprimer ( l'ordre n'intervient pas ici )

Voici un code C basé sur mon principe de résolution, attention, c'est un test, le code n'est pas secure du tout, il utilise des globales et il est limité à 256 solutions.
Il travaille sur des sommes en centimes.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <string.h>
 
int pieces[] = {1, 2, 5, 10, 20, 50, 100, 200};
char *nom[] = {"0,01", "0,02", "0,05", "0,10", 
                "0,20", "0,50", "1", "2"};
 
#define nbP (sizeof(pieces)/sizeof(pieces[0]))
 
int res[256][8];
int nbL;
 
void insert_resultat(int *t)
{
	memcpy(res[nbL], t, sizeof(res[nbL]));
	nbL ++;
}
 
void Calcule(int s, int ind, int *t)
{
	int i = 0;
	if (ind == 0)
	{
		t[ind] = s;
		insert_resultat(t);
	}
	else
	{
		while (i * pieces[ind] <= s)
		{
			t[ind] = i;
 
			Calcule(s - i * pieces[ind], ind - 1, t);
			i++;
		}
	}
 
}
 
 
// affichage de la somme avec les pièces 
void Affiche(void)
{
	int i ;
	for(i = 0; i < nbL; i++)
	{
		int j;
		for( j = 0; j < nbP; j++)
			printf("%3d\t", res[i][j]);
 
		puts("");
	}
}
int main(void)
{
   int S = 17;
   int t[8] = {0};
 
   nbL = 0;
   Calcule(S, nbP-1, t);
 
   Affiche();
 
   return 0;
}