Discussion :

[nek_kro_kvlt]

Bonjour, en TP je devais faire la liste des combinaisons possibles de pièces de 2, 5, 10, 20 et 50 centimes pour arriver a 1€.
J'ai fait le code suivant, seulement ma récurrence est infinie. Pourtant, je ne vois pas mon erreur, étant encore novice en C++, votre aide serait la bienvenue

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
#include <stdlib.h>
#include <stdio.h>
 
const int cp1 = 2, cp2=5, cp3 = 10, cp4 = 20, cp5 = 50;
 
void afficher(int p1, int p2, int p3, int p4,int p5);
void frec(int p1, int p2, int p3, int p4, int p5);
 
int total = 0;
 
int main()
{
/*Ecrivez un programme qui affiche toutes les manières possibles d’obtenir un Euro avec des
pièces de 2, 5, 10, 20 et 50 centimes. Dire combien de possibilités ont été ainsi trouvées. Les
résultats seront affichés comme suit :*/
frec(0,0,0,0,0);
system("pause");
}
 
void afficher(int p1, int p2, int p3, int p4,int p5)
{
    fflush(stdout);
    total++;
    printf("%d : %d x %d   %d x %d   %d x %d   %d x %d   %d x %d \n", total, p1, cp1, p2, cp2, p3, cp3, p4, cp4, p5, cp5);
    //system("pause");
}
void frec(int p1, int p2, int p3, int p4, int p5)
{
    //afficher(p1, p2, p3, p4, p5);
    if ((p1*cp1+p2*cp2+p3*cp3+p4*cp4+p5*cp5) > 100)
    {
        //system("pause");
        return;
    }
    else if ((p1*cp1+p2*cp2+p3*cp3+p4*cp4+p5*cp5) == 100)
    {
       afficher(p1, p2, p3, p4, p5); 
    }
    else
    {
        frec(p1+1, p2, p3, p4, p5);
        frec(p1, p2+1, p3, p4, p5);
        frec(p1, p2, p3+1, p4, p5);
        frec(p1, p2, p3, p4+1, p5);
        frec(p1, p2, p3, p4, p5+1);
    }
}

Merci d'avance !

[Luc Hermitte]

A froid, cela me parait plus un problème d'algorithmique appliqué au C (tu n'utilises rien de propre au C++).

Sinon, ta solution me semble marcher, par contre certaines branches seront explorées plusieurs fois. D'où tes solutions en 42000 exemplaires.
Tu peux stocker les chemins par lesquels tu passes (196 solutions sur 1172 chemins explorés (j'ai pu me tromper)), remarquer qu'il n'est pas nécessaire de tout le temps incrémenter de 1, ... Ou peut-être repenser ta récursivité?

[nek_kro_kvlt]

Ah en fait j'avais pas pensé que le fait de décaler comme cela ça feras des croisement... j'ai rechanger l'algorithme ça semble marcher ...

[David Fleury]

En tout cas ça ressemble pas mal au problème 147 du site ACM
http://acm.uva.es/p/v1/147.html mais en plus simple.

Si tu veux t'amuser, essaye le