On tire six plaques au hasard contenant un nombre; puis on doit calculer à l'aide des quatre opérations arithmétiques élémentaires un total tiré au hasard entre 100 et 999. Les plaques peuvent valoir: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25, 50, 75 et 100. Tous les calculs doivent être effectués sur des nombres entiers. Si le total n'est pas atteint, on recherche le nombre le plus proche.
Analyse
On ne cherche pas a faire dans la finesse, on prend 2 plaques et on applique le premier
opérateur ( si possible ), si le resultat est trouvé, on s'arrête, sinon on cherche
a faire le compte avec ce résultat et les 4 chiffres qui restent. Et ainsi de suite ...
On va donc utiliser la récursivité, les nombres étant situés dans un tableau et les opérateurs
aussi, de cette manière il est trés facile de modifier le nombre des opérateurs ou des plaques
tirées.
Programme
#define GAP(a,b) (((a)>(b))?((a)-(b)):((b)-(a)))
#define SPRINTOP(a,b,k,res) \
({strcpy(str_tmp,str_result);\
sprintf(str_result,"%3d %c %3d = %d\n%s",\
(((a)>(b))?(a):(b)),s[k],(((a)>(b))?(b):(a)),res,str_tmp);})
#define NBCH 6
int best_tot = 0, best_gap = 999;
char str_result[255],str_tmp[255];
int plus (int *a, int b) { return (*a += b); }
int moins(int *a, int b) { return (*a = GAP(*a,b)); }
int multi(int *a, int b) { return (*a *= b ); }
int divis(int *a, int b) {
if (*a < b) { *a^=b; b^=*a; *a^=b; }
if ( !(*a%b) ) return (*a /= b );
return 0;
}
#define NBOP 4
int (*f[])(int *,int) = { plus , moins , multi, divis };
char s[] = "+-*/";
int lcb(int *tab, int nb, int tot)
{
int i,j,k,t[NBCH];
for ( i=0 ; i<nb-1 ; i++ )
for ( j=i+1 ; j<nb ; j++)
for ( k=0; k<NBOP; k++) {
memcpy(t,tab,sizeof(int)*NBCH);
if ( (*f[k])(&t[i],t[j]) ) {
if ( t[i] == tot ) return SPRINTOP(tab[i],tab[j],k,t[i]);
if ( GAP(t[i],tot) < best_gap) {
best_tot = t[i] ;
best_gap = GAP(best_tot,tot);
}
t[j]=t[nb-1];
if (lcb(t,nb-1,tot)) return SPRINTOP(tab[i],tab[j],k,t[i]);
}
}
return 0;
}
int main(void)
{
int t[NBCH], i, tot;
*str_result = 0x00;
for ( i=0; i<NBCH ; scanf("%d",(printf("nombre %d : ",i+1),&t[i++]))) ;
printf("total : ");
scanf("%d",&tot);
if ( ! lcb(t,NBCH,tot) ) lcb(t,NBCH,best_tot);
else printf("Le compte est bon : \n");
return ! printf(str_result);
}
Conclusion
Pour le compte est bon
la récursivité est béton
pas besoin d'etre malin
avec du C bien bourrin
Problème
Analyse
Programme
Conclusion