Le compte est bon : algorithme de résolution

**Magicarpet** · 28/01/2011, 23h51

Bonsoir,

En tant que débutant en C, j'ai quelques petits soucis pour pondre un code correct..;
Mon projet est le suivant : Le compte est bon (jeu super connu).

Je bug au niveau de la fonction "calculuser" qui doit me permettre d'afficher la solution à partir d'un tirage de 6 nombres et d'un nombre cible à trouver.

Je ne sais pas trop si j'appelle correctement ma fonction récursive, si vous pouvez m'aider...

Merci d'avance!

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
//prototypes
int initialisation (int *nbtires);
int calculuser(int cible, int *tab, int taille);
int operation(int n1, int n2, int operateur);
 
int main()
{
    int nbc;    //nb cible
    int *nbtir; //pointeur car tableau
 
    nbtir = (int *)malloc(sizeof(*nbtir) * 6);  //allocation mémoire pour tableau tirage. Malloc car tableau
 
    if (nbtir == NULL)
    {
        printf("Erreur lors de l'allocation mémoire\n");  //si allocation pas réussie, exit
        return (EXIT_FAILURE);
    }
 
    nbc=initialisation(nbtir);
    free(nbtir);
 
    calculuser(nbc, nbtir, 6);
 
 
    return EXIT_SUCCESS;
}
 
//Initialisation du jeu : 6 nbs aléatoires tirés + 1 nb à trouver
int initialisation (int *nbtires)
{
    int indice,i,j;
    int nbcible;
    int nbpossible[14]={1,2,3,4,5,6,7,8,9,10,25,50,75,100}; //valeurs départ possibles
 
    srand(time(0));
 
    printf("Tirage : ");
 
    for (i=0;i<6;i++)
    {
    indice= rand()%14;
 
        if (nbpossible[indice] <= 10)   //pour faire apparaitre 2 fois un nombre <10
        {
            nbtires[i] = nbpossible[indice];   //nombres tirés au hasard
            printf("%i \t",nbpossible[indice]);
            fflush(NULL);
        }
        else
        {
            for(j=0;j<6;j++)
            {
                if (nbtires[j] == nbpossible[indice])   //si 2 fois mm nb, retour au début du for(i)
                    continue;
                if (j == 5)                            //si boucle finie, on stocke le nb tiré
                {
                    nbtires[i] = nbpossible[indice];   //nombres tirés au hasard
                    printf("%i \t",nbpossible[indice]);
                    fflush(NULL);
                }
            }
        }
    }
 
    nbcible=(rand()%900)+100;//nombre à trouver enter 100 et 999
    printf("\n\nVous devez trouver : %i\n\n",nbcible);
 
    return (nbcible);
}
 
//calcul de la solution du nombre à trouver
int calculuser(int cible, int *tab, int taille)
{
    int i,j,o;  //boucles sur nb1, nb2, operation
    int resultat;
    char operateurs[4]={'+','-','*','/'};   //les 4 opérations
    int backup[6];  //tableau auxiliaire pr stocker nbs utilisés
    //int prochediff,procheres;
    int a,b;
 
    for (i=0;i<5;i++)
    {
        for (j=1;j<6;j++)
        {
            for(o=0;o<4;o++)
            {
                resultat=operation(*(tab+i),*(tab+j),o);
                if (resultat==cible) continue;
 
                if (resultat!=cible)
                {
                backup[a]=*(tab+i);
                backup[b]=*(tab+j);
                *(tab+i)=resultat;
                *(tab+j)=*(tab+(taille-1));
 
                printf("%d %c %d = %d\n", *(tab+i),operateurs[o],*(tab+j),resultat);
 
                calculuser(cible,tab, 6);   //appel récursif pr recommencer
                }
 
 
            }
        }
    }
 
 
    return 0;
 
}
 
 
//fonction qui calcule les opérations entre 2 nb tirés
int operation(int n1, int n2, int operateur)
{
    switch (operateur)
    {
        case 0:
        {
            return (n1+n2);
            break;
        }
        case 1:
        {
            return (n1-n2);
            break;
        }
 
        case 2:
        {
            return (n1*n2);
            break;
        }
 
        case 3:
        {
            if (0== n1%n2) return (n1/n2);
            break;
        }
        default:
        {
            printf("ERROR!!!\n");
            break;
        }
    }
    return 0;
}

**LittleWhite** · 29/01/2011, 00h54

Bonjour,

Il aurait été bien que:

Vous nous décriviez le bug
Vous nous décriviez ce qui était attendu
Votre reflexion sur le pourquoi / comment résoudre

Bon, j'ai pris le temps de compiler le programme. Mon gentil GCC m'indique les choses suivantes:

calc.c: In function ‘calculuser’:
calc.c:96: warning: ‘a’ may be used uninitialized in this function
calc.c:97: warning: ‘b’ may be used uninitialized in this function

Il serait peut être bon de faire en sorte que ces warnings partent.

Lors du lancement du programme, cela crash. Dans ce cas, il vous sera utile de regarder ce qui se passe à l'aide d'un débuggueur (gdb ou celui dans Code::Blocks ou celui de VS). Cela permet de faire une exécution pas à pas, de voir les valeurs des variables, et de trouver le bug ultra rapidement (arrêt sur la ligne du bug)

Et comme par hasard (non mais vraiment, je vais croire qu'il y a des liens entre les différents éléments de l'univers (sarcasme off)), le bug est du fait que les variables 'a' et 'b' ne sont pas initialisé (cela vous rappel quelque chose?) et que du coup, l'accès au tableau buffer est illicite (car en dehors du tableau).

**sam1507** · 29/01/2011, 01h05

Code :

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

1
2
3
free(nbtir);
 
calculuser(nbc, nbtir, 6);

Gros soucis à ce niveau là aussi. Le tableau est désalloué avant d'être utilisé.

**Magicarpet** · 29/01/2011, 01h22

Désolé, j'ai été un peu rapide sur l'explication de mon problème.

Pour que ca soit clair; si tout se passe bien, la fonction calculuser doit pouvoir m'afficher la solution pas à pas pour trouver le nombre cible à partir du tirage.

Ainsi, je fais tous les calculs possibles grace à la fonction opérations. Les résultats sont stockés dans la variable "resultat". Il s'agit en principe des opérations entre 2 nombres du tirages.
Il faut ensuite se débarasser des nombres utilisés, donc j'utilise "backup", un tableau auxiliaire qui doit contenir ces nombres usés.
Puis, il faut utiliser le résultat des opérations, donc je fais appel à ma fonction récursive.

Pour revenir aux variables a et b, c'est bizarre. Dans mon 1er poste, je ne les avais meme pas utilisé. De plus, mon Code Blocks ne m'a indiqué aucune erreur, c'est pour ça que je n'ai rien pu dire sur les erreurs ^^

Voici une autre version de mon code. Là encore, aucune erreur n'est indiquée, seulement un gros plantage.
Dans la console, on voit quand meme beaucoup de calculs, mais avec des 0 dont je ne sais pas d'où ca sort...

Merci encore pour votre aide!

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
//prototypes
int initialisation (int *nbtires);
int calculuser(int cible, int *tab, int taille);
int operation(int n1, int n2, int operateur);
 
int main()
{
    int nbc;    //nb cible
    int *nbtir; //pointeur car tableau
 
 
    nbtir = (int *)malloc(sizeof(*nbtir) * 6);  //allocation mémoire pour tableau tirage. Malloc car tableau
 
    if (nbtir == NULL)
    {
        printf("Erreur lors de l'allocation mémoire\n");  //si allocation pas réussie, exit
        return (EXIT_FAILURE);
    }
 
    nbc=initialisation(nbtir);
    calculuser(nbc, nbtir, 6);
 
    free(nbtir);
 
    return EXIT_SUCCESS;
}
 
//Initialisation du jeu : 6 nbs aléatoires tirés + 1 nb à trouver
int initialisation (int *nbtires)
{
    int indice,i,j;
    int nbcible;
    int nbpossible[14]={1,2,3,4,5,6,7,8,9,10,25,50,75,100}; //valeurs départ possibles
 
    srand(time(0));
 
    printf("Tirage : ");
 
    for (i=0;i<6;i++)
    {
    indice= rand()%14;
 
        if (nbpossible[indice] <= 10)   //pour faire apparaitre 2 fois un nombre <10
        {
            nbtires[i] = nbpossible[indice];   //nombres tirés au hasard
            printf("%i \t",nbpossible[indice]);
            fflush(NULL);
        }
        else
        {
            for(j=0;j<6;j++)
            {
                if (nbtires[j] == nbpossible[indice])   //si 2 fois mm nb, retour au début du for(i)
                    continue;
                if (j == 5)                            //si boucle finie, on stocke le nb tiré
                {
                    nbtires[i] = nbpossible[indice];   //nombres tirés au hasard
                    printf("%i \t",nbpossible[indice]);
                    fflush(NULL);
                }
            }
        }
    }
 
    nbcible=(rand()%900)+100;//nombre à trouver enter 100 et 999
    printf("\n\nVous devez trouver : %i\n\n",nbcible);
 
    return (nbcible);
}
 
//calcul de la solution du nombre à trouver
int calculuser(int cible, int *tab, int taille)
{
    int i,j,o;  //boucles sur nb1, nb2, operation
    int resultat;
    char operateurs[4]={'+','-','*','/'};   //les 4 opérations
    int backup[6]={0,0,0,0,0,0};  //tableau auxiliaire pr stocker nbs utilisés
    int a=0,b=0;
 
    for (i=0;i<taille-1;i++)
    {
        for (j=1;j<taille;j++)
        {
            for(o=0;o<4;o++)
            {
                resultat=operation(*(tab+i),*(tab+j),o);
 
                if (resultat==cible) return;
 
                if (resultat!=cible)
                {
                printf("%d %c %d = %d\n", *(tab+i),operateurs[o],*(tab+j),resultat);
                }
 
                for(a=0;a<taille;a++)
                {
                    if (backup[a]==*(tab+i) || backup[b]==*(tab+j)) continue;
 
                *(tab+i)=resultat;
                *(tab+j)=*(tab+(taille-1));
                }
 
 
                if (calculuser(cible,tab, taille-1))   //appel récursif pr recommencer
                {
                    return cible;
                }
 
            }
        }
    }
 
 
    return 0;
 
}
 
 
//fonction qui calcule les opérations entre 2 nb tirés
int operation(int n1, int n2, int operateur)
{
    switch (operateur)
    {
        case 0:
        {
            return (n1+n2);
            break;
        }
        case 1:
        {
            return (n1-n2);
            break;
        }
 
        case 2:
        {
            return (n1*n2);
            break;
        }
 
        case 3:
        {
            if (0== n1%n2) return (n1/n2);
            break;
        }
        default:
        {
            printf("ERROR!!!\n");
            break;
        }
    }
    return 0;
}

**souviron34** · 29/01/2011, 13h59

Envoyé par Magicarpet

Là encore, aucune erreur n'est indiquée, seulement un gros plantage.

bien régler son compilateur est essentiel..

Voir le chapitre à ce sujet sur ce forum...

Un minimmum de -Wall ...

**Magicarpet** · 29/01/2011, 14h04

Bon, je pense que je me rapproche du but. Seulement, les lignes de calculs affichées ne correspondent pas vraiment au détail d'une solution...

Je pense qu'il y a des modifs à faire au niveau de l'affichage des résultats (printf). Pouvez-vous me dire mon erreur?

Merci!

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
//prototypes
int initialisation (int *nbtires);
int calculuser(int cible, int *tab, int taille);
int operation(int n1, int n2, int operateur);
 
int main()
{
    int nbc;    //nb cible
    int *nbtir; //pointeur car tableau
    char *soluce;
 
 
    nbtir = (int *)malloc(sizeof(int));  //allocation mémoire pour tableau tirage. Malloc car tableau
    //soluce=(int*)malloc(sizeof(*soluce)*2000);
 
    if (nbtir == NULL)
    {
        printf("Erreur lors de l'allocation mémoire\n");  //si allocation pas réussie, exit
        return (EXIT_FAILURE);
    }
 
    nbc=initialisation(nbtir);
    calculuser(nbc, nbtir, 6);
 
    free(nbtir);
 
    return EXIT_SUCCESS;
}
 
//Initialisation du jeu : 6 nbs aléatoires tirés + 1 nb à trouver
int initialisation (int *nbtires)
{
    int indice,i,j;
    int nbcible;
    int nbpossible[14]={1,2,3,4,5,6,7,8,9,10,25,50,75,100}; //valeurs départ possibles
 
    srand(time(0));
 
    printf("Tirage : ");
 
    for (i=0;i<6;i++)
    {
    indice= rand()%14;
 
        if (nbpossible[indice] <= 10)   //pour faire apparaitre 2 fois un nombre <10
        {
            nbtires[i] = nbpossible[indice];   //nombres tirés au hasard
            printf("%i \t",nbpossible[indice]);
            fflush(NULL);
        }
        else
        {
            for(j=0;j<6;j++)
            {
                if (nbtires[j] == nbpossible[indice])   //si 2 fois mm nb, retour au début du for(i)
                    continue;
                if (j == 5)                            //si boucle finie, on stocke le nb tiré
                {
                    nbtires[i] = nbpossible[indice];   //nombres tirés au hasard
                    printf("%i \t",nbpossible[indice]);
                    fflush(NULL);
                }
            }
        }
    }
 
    nbcible=(rand()%900)+100;//nombre à trouver enter 100 et 999
    printf("\n\nVous devez trouver : %i\n\n",nbcible);
 
    return (nbcible);
}
 
//calcul de la solution du nombre à trouver
int calculuser(int cible, int *tab, int taille)
{
    int i,j,o;  //boucles sur nb1, nb2, operation
    int resultat;
    char operateurs[4]={'+','-','*','/'};   //les 4 opérations
    int backup[6]={0,0,0,0,0,0};  //tableau auxiliaire pr stocker nbs utilisés
    int a=0,b=0;
    char calculs[1000];
    //char soluce[2000];
 
 
    for (i=0;i<taille-1;i++)
    {
        for (j=i+1;j<taille;j++)
        {
            for(o=0;o<4;o++)
            {
                if (*(tab+i)==cible) return;
                //calcul des 4 opérations entre 2 nbs du tirage
                resultat=operation(*(tab+i),*(tab+j),o);
 
                //sauvegarde dans tableau les valeurs de i et j
                backup[i]=*(tab+i);
                backup[j]=*(tab+j);
 
                //modification du tirage : resultat à la place de i
                *(tab+i)=resultat;
                //echange de place entre i et dernier element
                *(tab+j)=*(tab+(taille-1));
 
                printf("%d %c %d = %d\n", *(tab+i),operateurs[o],*(tab+j),resultat);
 
                //sprintf(calculs,"%d %c %d = %d\n", *(tab+i),operateurs[o],*(tab+j),resultat);
                //strcpy(soluce,calculs);
 
                if (calculuser(cible,tab, taille-1))   //appel récursif pr recommencer
                {
                    //printf("%d %c %d = %d\n", backup[i],operateurs[o],backup[j],resultat);
                    return;
                }
 
 
                *(tab+i)=backup[i];
                *(tab+j)=backup[j];
 
 
 
            }
        }
    }
 
    return;
 
}
 
 
//fonction qui calcule les opérations entre 2 nb tirés
int operation(int n1, int n2, int operateur)
{
    switch (operateur)
    {
        case 0:
        {
            return (n1+n2);
            break;
        }
        case 1:
        {
            return (n1-n2);
            break;
        }
 
        case 2:
        {
            return (n1*n2);
            break;
        }
 
        case 3:
        {
            if (0== n1%n2) return (n1/n2);
            break;
        }
        default:
        {
            printf("ERROR!!!\n");
            break;
        }
    }
    return 0;
}

**LittleWhite** · 29/01/2011, 14h32

Mon gentil compilateur m'indique:

calc.c: In function ‘calculuser’:
calc.c:92: warning: ‘return’ with no value, in function returning non-void

Bon ... ce n'est pas très grave (cela ne provoquera peut être pas de crash

)
Après, le programme crash sur une:

Floating point exception

Encore une fois, je conseille l'utilisation d'un debuggueur
Ici:

0x0000000000400bd7 in operation (n1=43, n2=0, operateur=3) at calc.c:147
147 if (0== n1%n2) return (n1/n2);

Mon débuggueur indique que n2 = 0 (cause du crash).
Je vous laisse trouvé la raison du pourquoi nous en arrivons à ce point

(N'hésitez pas à décrire votre raisonnement)

Ligne 101:

Code :

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

1
2
 
if (backup[a]==*(tab+i) || backup[b]==*(tab+j)) continue;

Sachant que a et b sont égal à 0, et que depuis hier je ne trouve pas de ligne qui modifient a et b ... j'ai du mal à comprendre votre reflexion ...

**Sve@r** · 30/01/2011, 00h30

Envoyé par Magicarpet

Désolé, j'ai été un peu rapide sur l'explication de mon problème.

Pour que ca soit clair; si tout se passe bien, la fonction calculuser doit pouvoir m'afficher la solution pas à pas pour trouver le nombre cible à partir du tirage.

Ainsi, je fais tous les calculs possibles grace à la fonction opérations. Les résultats sont stockés dans la variable "resultat". Il s'agit en principe des opérations entre 2 nombres du tirages.
Il faut ensuite se débarasser des nombres utilisés, donc j'utilise "backup", un tableau auxiliaire qui doit contenir ces nombres usés.
Puis, il faut utiliser le résultat des opérations, donc je fais appel à ma fonction récursive.

Je me suis amusé à programmer cet algo en Python. Bon, l'avantage c'est que Python est beaucoup plus souple que le C question syntaxe. Mais surtout c'est que j'ai bien débroussaillé question optilisation.
Par exemple avoir les nombres triés dans l'ordre croissant est un super avantage. Parce que si t'as 2 nombres identiques, style 2; 3; 3; 5; 10; ben une fois que le 2 a été traité puis que le 3 a lui-aussi été testé, inutile de tester le 3 suivant. De plus, ça évite aussi des opérations inutiles (en effet, inutile de tester 3 - 5 puisque ça donne un négatif ou 3/5 puisque ça donne un résultat non entier). De même, inutile de multiplier 2 nombres si l'un des deux vaut 1

Si tu veux regarder, voici le code complet

Code Python :

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
#!/usr/bin/env python
# coding: Latin-1 -*-
 
# Chercher la solution de "le compte est bon"
 
# Objet pour gérer le résultat
class cRes:
	# Constructeur
	def __init__(self, liste):
		self.liste=[elem for elem in liste if elem != 0]
		self.tabSol=[]
	# __init__()
 
	# Affichage
	def __str__(self):
		str=""
		str+="liste: %s\n" % self.liste
		str+="Solution\n"
		for s in self.tabSol: str+="%s\n" % s
		return str
	# __str__()
 
	# Longueur
	def __len__(self):
		return len(self.tabSol)
	# __len__()
 
	# Nombre de doublons
	def getDoublon(self):
		return len([s for s in self.tabSol if s.isDoublon()])
	# getDoublon()
 
	# Recherche de la solution
	def crawler(self, but):
		# Recherche récursive
		if not cRes.__cherche(
				but,
				self.liste,
				[],
				self.tabSol,
			): return False
 
		# Tri des solutions
		self.tabSol.sort()
 
		# Positionnement des solutions en double
		for i in range(1, len(self.tabSol)):
			if self.tabSol[i] == self.tabSol[i - 1]:
				self.tabSol[i].setDoublon()
		return True
	# crawler()
 
	# Fonction de recherche (récursive)
        @staticmethod                                                   # Méthode statique
	def __cherche(but, liste, calc, sol, prof=0):
		# La fonction est par défaut sans solution
		trouve=False
 
		# Parcours de chaque couple de nombres
		for ((x, y), tabOp) in cCalc.tuple(liste):
			# Parcours de chaque opération et son résultat associé
			for (op, res) in tabOp:
				# Ajout calcul à la liste des calculs précédents
				calc.append(cCalc(x, op, y, res))
				#print "%s%d %s: %d %s %d = %d" % ("\t" * prof, but, liste, x, op, y, res)
 
				# Si le résultat est trouvé et que tous calculs utilisés
				if res == but and cSol.check(calc):
					# La fonction a réussi
					trouve=True
 
					# Les calculs sont ajoutés au tableau des solutions
					sol.append(cSol(calc))
				else:
					# S'il y a encore des nombres dans la liste
					if len(liste) > 2:
						# Création nouvelle liste sans les nombres testés
						new=[res,] + liste
						new.remove(x)
						new.remove(y)
 
						# Si l'appel récursif trouve
						if cRes.__cherche(but, new, calc, sol, prof + 1):
							# L'appel récursif a réussi
							trouve=True
						# if
					# if
				# if
 
				# Suppression dernier calcul inutile
				del(calc[-1])
			# for
		# for
 
		# Renvoi booléen
		return trouve
	# __cherche()
# cRes
 
# Objet pour gérer une solution
class cSol:
	# Constructeur
	def __init__(self, calc):
		self.tabLig=[c for c in calc]
		self.fl_doublon=False
	# __init__()
 
	# Affichage
	def __str__(self):
		str=""
		for t in self.tabLig: str+="%s\n" % t
		if self.fl_doublon: str+="(double)\n"
		return str
	# __str__()
 
	# Longueur
	def __len__(self):
		return len(self.tabLig)
	# __len__()
 
	# Comparaison de 2 solutions
	def __cmp__(self, other):
		if len(self) < len(other): return -1
		if len(self) > len(other): return 1
		tab1=[c for c in self.tabLig]
		tab2=[c for c in other.tabLig]
		tab1.sort()
		tab2.sort()
		for (x, y) in zip(tab1, tab2):
			if x < y: return -1
			if x > y: return 1
		return 0
	# __cmp__()
 
	# Vérification doublon
	def isDoublon(self):
		return self.fl_doublon
	# isDoublon()
 
	# Mise à jour flag doublon
	def setDoublon(self, flag=True):
		self.fl_doublon=flag
	# setDoublon()
 
	# Vérification solution: tout calcul doit être utilisé
        @staticmethod                                                   # Méthode statique
	def check(tabCalc):
		new=[tabCalc[-1],]
 
		# Balayage du tableau des calculs en partant de la fin
		for i in range(len(tabCalc) - 2, -1, -1):
			# Balayage des calculs conservés
			ok=False
			for s in new:
				# Si le résultat de la solution courante est utilisé dans les suivantes
				if tabCalc[i].res == s.o1 or tabCalc[i].res == s.o2:
					ok=True
					break
			# Si résultat pas utilisé, solution rejetée
			if not ok: return False
 
			# Le résultat est mémorisé pour valider les autres calculs
			new.append(tabCalc[i])
 
		return True
	# check()
# cSol
 
# Objet pour gérer un calcul
class cCalc:
	# Constructeur
	def __init__(self, o1, op, o2, res):
		self.o1=o1
		self.op=op
		self.o2=o2
		self.res=res
	# __init__()
 
	# Affichage
	def __str__(self):
		return "%d %s %d = %d" % (self.o1, self.op, self.o2, self.res)
	# __str__()
 
	# Comparaison de 2 calculs
	def __cmp__(self, other):
		if self.res < other.res: return -1
		if self.res > other.res: return 1
		return 0
	# __cmp__()
 
	# Création couples calculs
        @staticmethod                                                   # Méthode statique
	def tuple(liste):
 
		# Initialisation tableaux
		tabTuple=[]
		tabOper=[]
 
		# Tri de la liste de nombres pour éviter les calculs en double
		liste.sort()
 
		# Parcours de chaque élément de la liste
		for i in range(len(liste)):
			# Parcours de chaque élément de la liste
			for j in range(len(liste)):
				# Elimination doublons
				if i == j or (liste[i], liste[j]) in tabTuple: continue
 
				# Création liste opérations
				oper=[]
				# Vérification commutativité (couple inversé)
				if (liste[j], liste[i]) not in tabTuple:
					# Addition - Rien à éviter (aucun nombre ne vaut 0)
					oper.append(('+', liste[i] + liste[j]))
 
					# Multiplication - Si aucun des nombres ne vaut 1
					if liste[i] != 1 and liste[j] != 1:
						oper.append(('*', liste[i] * liste[j]))
				# if
 
				# Soustraction - Si le résultat est positif
				if liste[i] > liste[j]:
					oper.append(('-', liste[i] - liste[j]))
 
				# Division - Si résultat entier et diviseur différent de 1
				if (liste[i] % liste[j]) == 0 and liste[j] > 1:
					oper.append(('/', liste[i] / liste[j]))
 
				# Ajout tableau opérations
				tabOper.append(oper)
 
				# Création tuple
				tabTuple.append((liste[i], liste[j]))
			# for
		# for
 
		# Renvoi tableaux
		return zip(tabTuple, tabOper)
	# tuple()
# cCalc
 
# Si le module est appelé en tant que programme
if __name__ == "__main__":
	import sys
	if len(sys.argv) <= 3:
		print "usage %s but c1 c2 ..." % (sys.argv[0])
		sys.exit(-1)
 
	# Création du résultat
	but=int(sys.argv[1])
	res=cRes([int(arg) for arg in sys.argv[2:]])
	#print cCalc.tuple(res.liste)
	#sys.exit(0)
 
	# Recherche du résultat
	err=0
	while True:
		print "Recherche %d" % but
		if res.crawler(but): break
		err+=1
		but=(err % 2) == 0 and but - err or but + err
 
	# Affichage résultat
	nbSol=len(res)
	nbDbl=res.getDoublon()
	print "Demandé %d - Obtenu %d (%d solution%s %s)" % (\
		int(sys.argv[1]),
		but,
		nbSol,
		nbSol > 1 and "s" or "",
		nbDbl > 0\
			and "dont %d doublon%s" % (\
				nbDbl,
				nbDbl > 1 and "s" or ""
			)
			or "et aucun doublon"
		)
 
	# Parcours de toutes les solutions
	for (i, s) in enumerate([s for s in res.tabSol if not s.isDoublon() or True]):
		print "Solution %d\n%s" % (i + 1, s)

Te suffit de l'enregistrer dans un fichier "toto.py" puis de l'appeler en lui passant le nombre à trouver puis les plaques à utiliser, exemple ./toto.py 123 1 2 3 4 5 6

**Magicarpet** · 02/02/2011, 17h37

Merci pour vos réponses!

J'ai quasiment tout remodifié ma fonction "calculuser". Celle-ci doit afficher les calculs pas à pas pour arriver à la solution. Cependant, ce que j'obtiens est encore bizarre... Si vous pouvez me dire où ca coince!

Perso, je pense que ya au moins des erreurs au niveau de mes return. Mais si je n'en mets pas, ca affiche des trucs indéfiniment. Enfin, je ne suis pas du tout à l'aise avec les return...

Merci d'avance!

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
 
#define GAP(a,b)        (((a)>(b))?((a)-(b)):((b)-(a)))
 
//prototypes
int initialisation (int *nbtires);
int calculuser(int cible, int *tab, int taille);
int operation(int n1, int n2, int operateur);
 
int best_tot = 0, best_gap = 999;
char str_result[255],str_tmp[255];
 
 
int main(void)
{
    int nbc, taille=6;    //nb cible
    int nbtir[6];
 
    //appel des fonctions
    nbc=initialisation(nbtir);
 
    if (!calculuser(nbc,nbtir,taille) ) calculuser(best_tot,nbtir,taille);
    printf("\n");
    //affichage solution
    return printf(str_result);
}
 
//Initialisation du jeu : 6 nbs aléatoires tirés + 1 nb à trouver
int initialisation (int *nbtires)
{
    int indice,i,j;
    int nbcible;
    int nbpossible[14]={1,2,3,4,5,6,7,8,9,10,25,50,75,100}; //valeurs départ possibles
 
    srand(time(0));
 
    printf("Tirage : ");
 
    for (i=0;i<6;i++)
    {
    indice= rand()%14;
 
//        if (nbpossible[indice] < 10)   //pour faire apparaitre 2 fois un nombre <10
//        {
//            nbtires[i] = nbpossible[indice];   //nombres tirés au hasard
//            printf("%i \t",nbpossible[indice]);
//            fflush(NULL);
//        }
 
            for(j=0;j<6;j++)
            {
                if (nbtires[j] == nbpossible[indice])   //si 2 fois mm nb, retour au début du for(i)
                    continue;
 
                if (j == 5)                            //si boucle finie, on stocke le nb tiré
                {
                    nbtires[i] = nbpossible[indice];   //nombres tirés au hasard
                    printf("%i \t",nbpossible[indice]);
                }
            }
    }
 
    nbcible=(rand()%900)+100;//nombre à trouver enter 100 et 999
    printf("\n\nVous devez trouver : %i\n\n",nbcible);
 
    return (nbcible);
}
 
//calcul de la solution du nombre à trouver
int calculuser(int cible, int *tab, int taille)
{
    int i,j,o;  //boucles sur nb1, nb2, operation
    int t[6];
    char operateurs[4]={'+','-','*','/'};   //les 4 opérations
 
    for (i=0;i<taille-1;i++)
    {
        for (j=i+1;j<taille;j++)
        {
            for(o=0;o<4;o++)
            {
                memcpy(t,tab,sizeof(int)*6);
 
                //t contient les résultat des opérations entre 2 nombres du tirage
                if (t[i]=operation(tab[i],tab[j],o))
                {
 
               //if (t[i]!=cible) continue;
 
                //si on a trouvé, alors on affiche la solution
                if(t[i]==cible)
                {
                    strcpy(str_tmp,str_result);
                    sprintf(str_result,"%d %c %d = %d\n", tab[i],operateurs[o],tab[j],t[i]);
 
                    return printf("%s",str_result);
                }
 
                //sinon, on compare le resultat par rapport au nombre cible
                else if (GAP(cible,t[i]) < best_gap)
                {
                    best_tot=t[i];
                    best_gap=GAP(cible,best_tot);
                }
 
                //on retrie le tableau
                t[i]=t[taille-1];
 
                if (calculuser(cible,t, taille-1))   //appel récursif pr recommencer
                {
                    strcpy(str_tmp,str_result);
                    sprintf(str_result,"%d %c %d = %d\n", tab[i],operateurs[o],tab[j],t[i]);
 
                    return printf("%s",str_result);
                }
                }
 
            }
        }
    }
    return;
}
 
 
//fonction qui calcule les opérations entre 2 nb tirés
int operation(int n1, int n2, int operateur)
{
    switch (operateur)
    {
        case 0:
        {
            return (n1+n2);
            break;
        }
        case 1:
        {
            return (n1-n2);
            break;
        }
 
        case 2:
        {
            return GAP(n1,n2);
            break;
        }
 
        case 3:
        {
            if (0== n1%n2) return (n1/n2);
            break;
        }
        default:
        {
            printf("ERROR!!!\n");
            break;
        }
    }
    return 0;
}

**LittleWhite** · 02/02/2011, 19h13

Cette fois, on a les indications suivantes (merci compilateur chéri):

main.c: In function ‘main’:
main.c:28: warning: format not a string literal and no format arguments
main.c: In function ‘calculuser’:
main.c:88: warning: suggest parentheses around assignment used as truth value
main.c:124: warning: ‘return’ with no value, in function returning non-void

Personnellement, je m'inquiéterais pour celui que j'ai mis en rouge.

Sinon, cela ne semble pas crasher, ce qui est déjà bien.
Par contre, cela ne fonctionne pas beaucoup:

100 + 1 = 3
50 + 1 = 100
75 + 1 = 50
100 + 1 = 75

100 + 1 = 75

**Magicarpet** · 02/02/2011, 19h46

Sinon, cela ne semble pas crasher, ce qui est déjà bien.
Par contre, cela ne fonctionne pas beaucoup:

justement je ne sais pas quoi faire pour afficher correctement la solution...si quelqu'un a une idée...

LittleWhite, quels sont les réglages de ton compilateur qui te permettent d'afficher les erreurs citées?? Perso, avec mon Code Blocks, je n'ai aucun message d'erreur

**LittleWhite** · 02/02/2011, 20h05

Envoyé par Magicarpet

justement je ne sais pas quoi faire pour afficher correctement la solution...si quelqu'un a une idée...

LittleWhite, quels sont les réglages de ton compilateur qui te permettent d'afficher les erreurs citées?? Perso, avec mon Code Blocks, je n'ai aucun message d'erreur

J'utilise directement GCC, du coup, je ne sais plus trop comment on met les options sous Code::Blocks.
Maintenant (je ne sais plus si je l'ai dit), il faut utiliser le compilateur pour trouver la réponse rapidement (afin de faire une exécution pas à pas).

Dans l'erreur, il y a cette histoire d'appel récursif, vous ne changer pas de nombre à prendre (enfin je crois (taille - 1, est ce vraiment utile ?) Je penserai que c'est plutot i et j que l'on devrait faire commencer toujours une case plus loin.
De plus, un retour de printf ne donnera surement pas le résultat auquel vous vous attendez (regardez la documentation du printf)

**sam1507** · 02/02/2011, 21h01

Envoyé par Magicarpet

Perso, avec mon Code Blocks, je n'ai aucun message d'erreur

Pour modifier les paramètres de compilations sous Code::Blocks, il faut aller dans :
Projects > Build options... > Onglet Compiler settings > Onglet Compiler Flags

**Magicarpet** · 02/02/2011, 22h04

Merci sam1507, j'ai trouvé! ^^

Sinon LittleWhite, j'ai trouvé une erreur. A la ligne 108, c'est t[j] et non t[i]. Du coup, j'obtiens des calculs cohérents!

Mais, je n'atteins toujours pas le nombre cible...
Il doit manquer quelque chose, du genre un truc qui me dit continuer tant que c'est pas fini???
Aussi, c'est pas normal qu'il ne m'affiche que des additions...

Voici le nouveau code:

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
 
#define GAP(a,b)        (((a)>(b))?((a)-(b)):((b)-(a)))
 
//prototypes
int initialisation (int *nbtires);
int calculuser(int cible, int *tab, int taille);
int operation(int n1, int n2, int operateur);
 
int best_tot = 0, best_gap = 999;
char str_result[255],str_tmp[255];
 
 
int main(void)
{
    int nbc, taille=6;    //nb cible
    int nbtir[6];
 
    //appel des fonctions
    nbc=initialisation(nbtir);
 
    if (!calculuser(nbc,nbtir,taille) ) calculuser(best_tot,nbtir,taille);
    printf("\n");
    //affichage solution
    return 0;
}
 
//Initialisation du jeu : 6 nbs aléatoires tirés + 1 nb à trouver
int initialisation (int *nbtires)
{
    int indice,i,j;
    int nbcible;
    int nbpossible[14]={1,2,3,4,5,6,7,8,9,10,25,50,75,100}; //valeurs départ possibles
 
    srand(time(0));
 
    printf("Tirage : ");
 
    for (i=0;i<6;i++)
    {
    indice= rand()%14;
 
//        if (nbpossible[indice] < 10)   //pour faire apparaitre 2 fois un nombre <10
//        {
//            nbtires[i] = nbpossible[indice];   //nombres tirés au hasard
//            printf("%i \t",nbpossible[indice]);
//            fflush(NULL);
//        }
 
            for(j=0;j<6;j++)
            {
                if (nbtires[j] == nbpossible[indice])   //si 2 fois mm nb, retour au début du for(i)
                    continue;
 
                if (j == 5)                            //si boucle finie, on stocke le nb tiré
                {
                    nbtires[i] = nbpossible[indice];   //nombres tirés au hasard
                    printf("%i \t",nbpossible[indice]);
                }
            }
    }
 
    nbcible=(rand()%900)+100;//nombre à trouver enter 100 et 999
    printf("\n\nVous devez trouver : %i\n\n",nbcible);
 
    return (nbcible);
}
 
//calcul de la solution du nombre à trouver
int calculuser(int cible, int *tab, int taille)
{
    int i,j,o;  //boucles sur nb1, nb2, operation
    int t[6];
    char operateurs[4]={'+','-','*','/'};   //les 4 opérations
 
    for (i=0; i<taille-1; i++)
    {
        for (j=i+1; j<taille; j++)
        {
            for(o=0;o<4;o++)
            {
                memcpy(t,tab,sizeof(int)*6);
 
                //t contient les résultat des opérations entre 2 nombres du tirage
                if (t[i]=operation(tab[i],tab[j],o))
                {
 
                //si on a trouvé, alors on affiche la solution
                if(t[i] == cible)
                {
                    strcpy(str_tmp,str_result);
                    sprintf(str_result,"%d %c %d = %d\n", tab[i],operateurs[o],tab[j],t[i]);
 
                    return printf("%s",str_result);
                }
 
                //sinon, on compare le resultat par rapport au nombre cible
                else if (GAP(cible,t[i]) < best_gap)
                {
                    best_tot=t[i];
                    best_gap=GAP(cible,best_tot);
                }
 
                //on retrie le tableau
                t[j]=t[taille-1];
 
                if (calculuser(cible,t, taille-1))   //appel récursif pr recommencer
                {
                    strcpy(str_tmp,str_result);
                    sprintf(str_result,"%d %c %d = %d\n", tab[i],operateurs[o],tab[j],t[i]);
 
                    return printf("%s",str_result);
                }
                }
 
            }
        }
    }
    return;
}
 
 
//fonction qui calcule les opérations entre 2 nb tirés
int operation(int n1, int n2, int operateur)
{
    switch (operateur)
    {
        case 0:
        {
            return (n1+n2);
            break;
        }
        case 1:
        {
            return (n1-n2);
            break;
        }
 
        case 2:
        {
            return GAP(n1,n2);
            break;
        }
 
        case 3:
        {
            if (0== n1%n2) return (n1/n2);
            break;
        }
        default:
        {
            printf("ERROR!!!\n");
            break;
        }
    }
    return 0;
}

**sam1507** · 02/02/2011, 22h38

Je ne sais pas où se situe exactement le problème mais il y a deux choses dans le code que je ne comprends pas :

1. Il y a trois return dans la fonction de calcul, du coup j'ai du mal à voir qu'elle est la condition de sortie de l'algorithme récursif. J'aurais tendance à penser que la récursivité se termine lorsque la 6ème et dernière plaquette a été utilisée, non ?

2. On attend de la fonction de calcul qu'elle retourne un entier, ce qui me laisse perplexe face à ces trois instructions :

Code :

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

1
2
3
return printf("%s",str_result);
return printf("%s",str_result);
return;

**Magicarpet** · 03/02/2011, 00h31

Merci beaucoup sam1507!! Grace à toi, j'ai pu corriger mes erreurs, et je crois que j'ai un code fonctionnel!

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
 
#define GAP(a,b)        (((a)>(b))?((a)-(b)):((b)-(a)))
 
//prototypes
int initialisation (int *nbtires);
int calculuser(int cible, int *tab, int nbch);
int operation(int n1, int n2, int operateur);
 
int best_tot = 0, best_gap = 999;
char str_result[555],str_tmp[555];
 
 
int main(void)
{
    int nbc, nbch=6;    //nb cible
    int nbtir[6];
 
    //appel des fonctions
    nbc=initialisation(nbtir);
 
    if ( ! calculuser(nbc,nbtir,nbch) ) calculuser(best_tot,nbtir,nbch);
 
    else printf("Le compte est bon \n");
 
    printf("\n");
    //affichage solution
    //printf(str_result);
    return ;
}
 
//Initialisation du jeu : 6 nbs aléatoires tirés + 1 nb à trouver
int initialisation (int *nbtires)
{
    int indice,i,j;
    int nbcible;
    int nbpossible[14]={1,2,3,4,5,6,7,8,9,10,25,50,75,100}; //valeurs départ possibles
 
    srand(time(0));
 
    printf("Tirage : ");
 
  for (i=0;i<6;i++)
    {
    nouveau:    //etiquette
    indice= rand()%14;
 
        for(j=0;j<6;j++)
        {
            if (nbtires[j]==nbpossible[indice]) goto nouveau; //condition pour ne pas avoir 2 fois le meme nombre
        }
    nbtires[i]=nbpossible[indice];   //nombres tirés au hasard
    printf("%i \t",nbpossible[indice]);
    }
    nbcible=(rand()%900)+100;//nombre à trouver enter 100 et 999
    printf("\n\nVous devez trouver : %i\n\n",nbcible);
 
    return nbcible;
}
 
//calcul de la solution du nombre à trouver
int calculuser(int cible, int *tab, int taille)
{
    int i,j,o;  //boucles sur nb1, nb2, operation
    int t[6];
    int n;
    char operateurs[4]={'+','-','*','/'};   //les 4 opérations
 
    for (i=0; i<taille-1; i++)
    {
        for (j=i+1; j<taille; j++)
        {
            for(o=0;o<4;o++)
            {
                memcpy(t,tab,sizeof(int)*6);
 
                //t contient les résultat des opérations entre 2 nombres du tirage
                t[i]=operation(tab[i],tab[j],o);
 
                if (!t[i]) continue;
                //si on a trouvé, alors on affiche la solution
                if(t[i] == cible)
                {
                    strcpy(str_tmp,str_result);
                    n=sprintf(str_result,"%d %c %d = %d\n", tab[i],operateurs[o],tab[j],t[i],str_tmp);
                    printf("%s",str_result,n);
                    return n;
                }
 
                //sinon, on compare le resultat par rapport au nombre cible
                if (GAP(cible,t[i]) < best_gap)
                {
                    best_tot=t[i];
                    best_gap=GAP(cible,best_tot);
                }
 
                //on retrie le tableau
                t[j]=t[taille-1];
 
                if (calculuser(cible,t, taille-1))   //appel récursif pr recommencer
                {
                    strcpy(str_tmp,str_result);
                    n=sprintf(str_result,"%d %c %d = %d\n", tab[i],operateurs[o],tab[j],t[i],str_tmp);
                    printf("%s",str_result,n);
                    return n;
                }
            }
        }
    }
    return 0;
}
 
 
//fonction qui calcule les opérations entre 2 nb tirés
int operation(int n1, int n2, int operateur)
{
    switch (operateur)
    {
        case 0:
        {
            return (n1+n2);
            break;
        }
        case 1:
        {
            return GAP(n1,n2);
            break;
        }
 
        case 2:
        {
            return (n1*n2);
            break;
        }
 
        case 3:
        {
            if (0== n1%n2) return (n1/n2);
            break;
        }
        default:
        {
            printf("ERROR!!!\n");
            break;
        }
    }
    return 0;
}

J'ai fais plusieurs essais, et apparemment, ca marche.

Petit bémol; la solution est affichée de bas en haut... comment faire le contraire, c'est à dire de haut en bas??

Merci encore!

EDIT : l'erreur qui faisait que je n'avais que des additions était toute simple : dans la fonction "opération", j'ai remplacé le produit n1*n2 par GAP(n1,n2)....du coup forcément, je ne pouvais atteindre le nombre cible...

**Sve@r** · 06/02/2011, 13h31

Envoyé par sam1507

1. Il y a trois return dans la fonction de calcul, du coup j'ai du mal à voir qu'elle est la condition de sortie de l'algorithme récursif. J'aurais tendance à penser que la récursivité se termine lorsque la 6ème et dernière plaquette a été utilisée, non ?

Pour moi, l'algorithme doit se terminer quand le nombre à atteindre à été trouvé. Et la solution n'est valide que si tous les calculs intermédiaires sont utiles. Ce qui se comprend, car s'il y a un calcul intermédiaire non utilisé par la suite, ça veut dire que, quelque part dans l'arbre récursif, se trouvera la même solution sans ledit calcul. Mais bon, bref, ce qui est facile à faire en Python l'est moins en C...

Envoyé par Magicarpet

Petit bémol; la solution est affichée de bas en haut... comment faire le contraire, c'est à dire de haut en bas??

J'aurais tendance à dire que c'est à cause de la récursivité. Tu obtiens le résultat final en dernier que tu affiches puis ensuite tu remontes l'arbre en affichant tous les calculs intermédiaires qui ont amené ce résultat. Donc si tu veux l'afficher dans le bon ordre, te faut mémoriser ces lignes de calcul dans un tableau de lignes puis afficher ce tableau dans l'ordre inverse.

Ceci dit, question affichage il y a un truc que je ne pige absolument pas

Code c :

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

1
2
3
4
strcpy(str_tmp,str_result);
n=sprintf(str_result,"%d %c %d = %d\n", tab[i],operateurs[o],tab[j],t[i],str_tmp);
printf("%s",str_result,n);
return n;

Là, je ne pige rien...

**Magicarpet** · 07/02/2011, 20h03

Oui, alors j'ai revu mon code, et en effet, j'ai pas besoin d'utiliser sprintf, strcpy et un return n;...
En fait, ce que je voulais faire, c'était justement mémoriser les lignes de calculs dans une chaine de caractères et afficher ensuite cette chaine, d'où l'utilisation certes maladroite, des sprintf...

Là, je ne comprends pas trop la logique. Je croyais avoir besoin de chaines de caractères pour afficher la solution, mais au final je n'en ai pas besoin...

Je croyais aussi avoir besoin d'un tableau auxiliaire pour stocker les nombres du tirage usés et les calculs intermédiaires entre 2 nombres...mais au final non...

Du coup, j'aboutis à quelque chose qui marche (je ne sais pas trop comment), avec des trucs bizarres dans le code.

**LittleWhite** · 07/02/2011, 20h06

Envoyé par Magicarpet

Oui, alors j'ai revu mon code, et en effet, j'ai pas besoin d'utiliser sprintf, strcpy et un return n;...
En fait, ce que je voulais faire, c'était justement mémoriser les lignes de calculs dans une chaine de caractères et afficher ensuite cette chaine, d'où l'utilisation certes maladroite, des sprintf...

Là, je ne comprends pas trop la logique. Je croyais avoir besoin de chaines de caractères pour afficher la solution, mais au final je n'en ai pas besoin...

Je croyais aussi avoir besoin d'un tableau auxiliaire pour stocker les nombres du tirage usés et les calculs intermédiaires entre 2 nombres...mais au final non...

Du coup, j'aboutis à quelque chose qui marche (je ne sais pas trop comment), avec des trucs bizarres dans le code.

Je vous propose de nous présenter ce dernier code et de nous dire sur quels points vous avez des problèmes afin que l'on puisse vous donner des explications (si possible)

**Magicarpet** · 09/02/2011, 00h12

Voici le dernier code :

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
 
#define GAP(a,b)    (((a)>(b))?((a)-(b)):((b)-(a)))
 
//prototypes
int initialisation (int *nbtires);
int calculuser(int cible, int *tab, int nbch);
int operation(int n1, int n2, int operateur);
 
int best_tot = 0, best_gap = 999;
char str_result[555],str_tmp[555];
 
 
int main()
{
    int nbc, nbch=6;    //nb cible
    int nbtir[6];
 
    //appel des fonctions
    nbc=initialisation(nbtir);
 
    if ( ! calculuser(nbc,nbtir,nbch) )
    {
        calculuser(best_tot,nbtir,nbch);
        printf("Solution approchee : \n");
    }
 
    else printf("Le compte est bon \n");
 
    printf("\n");
    //affichage solution
    //printf(str_result);
    return 0;
}
 
//Initialisation du jeu : 6 nbs aléatoires tirés + 1 nb à trouver
int initialisation (int *nbtires)
{
    int indice,i,j;
    int nbcible;
    int nbpossible[14]={1,2,3,4,5,6,7,8,9,10,25,50,75,100}; //valeurs départ possibles
 
    srand(time(0));
    printf("Tirage : ");
 
  for (i=0;i<6;i++)
    {
    nouveau:    //etiquette
    indice= rand()%14;
 
        for(j=0;j<6;j++)
        {
            if (nbtires[j]==nbpossible[indice]) goto nouveau; //condition pour ne pas avoir 2 fois le meme nombre
        }
    nbtires[i]=nbpossible[indice];   //nombres tirés au hasard
    printf("%i \t",nbpossible[indice]);
    }
    nbcible=(rand()%900)+100;//nombre à trouver enter 100 et 999
    printf("\n\nVous devez trouver : %i\n\n",nbcible);
 
    return nbcible;
}
 
//calcul de la solution du nombre à trouver
int calculuser(int cible, int *tab, int taille)
{
    int i,j,o;  //boucles sur nb1, nb2, operation
    int t[6];
    char operateurs[4]={'+','-','*','/'};   //les 4 opérations
 
    for (i=0; i<taille-1; i++)
    {
        for (j=i+1; j<taille; j++)
        {
            for(o=0;o<4;o++)
            {
                memcpy(t,tab,sizeof(int)*6);
                t[i]=operation(tab[i],tab[j],o);//t contient les résultat des opérations entre 2 nombres du tirage
                //si on n'a pas encore trouvé, on continue de chercher
                if (!t[i]) continue;
                //si on a trouvé, alors on affiche la solution
                if(t[i] == cible)
                {
                    //strcpy(str_tmp,str_result);
//                    sprintf(str_result,"%d %c %d = %d\n", tab[i],operateurs[o],tab[j],t[i]);
//                    printf("%s",str_result);
                    printf("%d %c %d = %d\n", tab[i],operateurs[o],tab[j],t[i]);
                    return ;
                }
 
                //sinon, on compare le resultat par rapport au nombre cible
//                if (GAP(cible,t[i]) < best_gap)
//                {
//                    best_tot=t[i];
//                    best_gap=GAP(cible,best_tot);
//                }
 
                //on retrie le tableau
                t[j]=t[taille-1];
 
                if (calculuser(cible,t, taille-1))   //appel récursif pr recommencer
                {
                    //strcpy(str_tmp,str_result);
//                    sprintf(str_result,"%d %c %d = %d\n", tab[i],operateurs[o],tab[j],t[i]);
//                    printf("%s",str_result);
                    printf("%d %c %d = %d\n", tab[i],operateurs[o],tab[j],t[i]);
                    return ;
                }
            }
        }
    }
    return 0;
}
 
 
//fonction qui calcule les opérations entre 2 nb tirés
int operation(int n1, int n2, int operateur)
{
    switch (operateur)
    {
        case 0:
        {
            return (n1+n2);
            break;
        }
        case 1:
        {
            return GAP(n1,n2);
            break;
        }
 
        case 2:
        {
            return (n1*n2);
            break;
        }
 
        case 3:
        {
            if (0== n1%n2) return (n1/n2);
            break;
        }
        default:
        {
            printf("ERROR!!!\n");
            break;
        }
    }
    return 0;
}

Comme je l'avais dis, ca m'affiche la solution à l'envers...
J'ai mis en commentaires tout ce que je n'ai pas besoin pour faire fonctionner mon code, mais que je croyais avoir besoin au début...

Par exemple, dans la fonction calculuser, je croyais avoir besoin d'une chaine de caractères "str_result", pour stocker les lignes de calcul. Mais au final, ca marche sans.
Aussi, j'avais au début introduit une variable "best_gap" (ligne 94). Ca avait pour but de comparer les résultats des calculs par rapport au nombre cible. Mais au final, je n'en ai pas besoin non plus.

Voilà, si vous pouvez me dire pourquoi ca marche finalement...

Merci!

Le compte est bon : algorithme de résolution

C

Discussions similaires

Partager

Partager