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;
}

Le compte est bon : algorithme de résolution

C

Vue hybride

Discussions similaires

Partager

Partager