Algo : resolution "le compte est bon" avec des arbres binaire

Soyez le premier à donner votre avis sur cette source.

Vue 9 568 fois - Téléchargée 585 fois

Description

le jeu televisé "des chiffres et des lettres" propose "le compte est bon"

mon code propose une résolution du compte est bon via des arbres binaires.

données :
6 chiffres aléatoire comprit entre 1 et 10.
1 chiffre a trouver comprit entre 100 et 999.

résultat:
la liste des opérations qui servent a trouver meilleur le résultat possible(le nombre à trouver, ou la solution qui s'en rapproche le plus).

Source / Exemple :


#include <iostream>
#include <time.h>
#include "leCompteEstBon.h"

int main()
{
	srand((unsigned int)time(NULL));
	clock_t start = clock();

	LeCptEstBon *leCompteEstBon;
	leCompteEstBon = new LeCptEstBon();

	leCompteEstBon->computeResult();
	leCompteEstBon->printSolution();

	delete leCompteEstBon;

	clock_t finish  = clock();
	float elapsed = (float)(finish-start) / (float)CLOCKS_PER_SEC;
	cout<<endl<<"------------------------------"<<endl;
	cout<<"elapsed time :"<<elapsed<<" seconds "<<endl;
	cout<<"------------------------------"<<endl;

	cout<<endl<<"press a key "<<endl;
	int waiting;
	cin>>waiting;
	exit(0);
}

Conclusion :


J'attends vos remarques sur ce code, notamment sur ses performances.
Il s'execute en 1 à 2 secondes pour les cas les plus compliqués.
Existe t'il un code plus rapide?

Je n'ai pas utilisé un système de "tas" car je ne vois pas comment résoudre cet exemple via les tas:
données : 5 5 10 8
solution a trouver : 105
5 * 5 = 25 (A)
8 * 10 = 80 (B)
25 + 80 = 105 (A+B)

on voit dans cet exemple que le fils droit effectue (A), et fils gauche effectue (B), indépendamment l'un de l'autre. puis (A)+(B). comment faire sans arbre ?

merci pour vos remarques,

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
11
Date d'inscription
jeudi 21 août 2003
Statut
Membre
Dernière intervention
31 janvier 2007

@clem0338
Dans le vrai jeu non, mais dans le code de aardman/BruNews ça peut arriver. Ça change pas grand chose...
J'ai fixé ce problème en mettant le plus grand chiffre à gauche dans les calculs, comme ça on a plus de chiffre négatif.

if (a>b)
{
res1 = a - b;
res2 = a + b;
res3 = a * b;
res4 = a / b; // plus test si la solution est un nombre entier...
}
else
{
res1 = b - a;
res2 = b + a;
res3 = b * a;
res4 = b / a; // plus test si la solution est un nombre entier...
}
Messages postés
65
Date d'inscription
mercredi 19 juin 2002
Statut
Membre
Dernière intervention
9 mars 2008

Peut être une question idiote, mais les nombres négatifs sont valides (dernier cas) ????
Messages postés
11
Date d'inscription
jeudi 21 août 2003
Statut
Membre
Dernière intervention
31 janvier 2007

un autre pour la route :

numbers : 4 2 5 7 9 100
number to find : 564

---------------------------------------------
mon code :
946 calculs en 94 (millisecondes)
calculs :
7 + 4 = 11
100 + 11 = 111
111 * 5 = 555
555 + 9 = 564

---------------------------------------------
autre code :
51426 calculs en 16 (millisecondes)
calculs :
4 * 2 = 8
7 * 9 = 63
5 - 63 = -58
8 * -58 = -464
100 - -464 = 564
Messages postés
11
Date d'inscription
jeudi 21 août 2003
Statut
Membre
Dernière intervention
31 janvier 2007

Je me suis amusé a comparer les 2 codes :
je place un compteur quand on check le résultat actuel et la solution (a chaque fois qu'on fait un calcul en fait)
je place un chrono sur chaque code (entre debut et fin du calcul)

j'ai obtenu cet exemple, assez significatif...
exemple :
numbers : 8 9 6 10 100 7
number to find : 306

---------------------------------------------
mon code :
325 calculs en 47 (millisecondes)
calculs :
7 * 6 = 42
42 - 8 = 34
34 * 9 = 306

---------------------------------------------
autre code :
7807 calculs en 0 (millisecondes)
calculs :
8 + 9 = 17
6 * 17 = 102
10 - 7 = 3
102 * 3 = 306

conclusion:
mon code résous le problème "mieux" (3 lignes contre 4 lignes)
mon code effectue moins de calculs aussi (300 contre 7000 ...)
Mais, il est 100 fois plus lent (47 contre 0)...

C'est la fête ...
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
28
La création d'un conteneur (multitude de new et delete) et ensuite le parcours d'un conteneur (pointeur sur suivant et deref de ce pointeur) n'ont bien sur aucun rapport en terme de performances avec une structure linéaire en mémoire (tableau).
Il faut donc bien voir que ce n'est pas la récursivité qui donne les perfs de l'autre version, on peut même dire qu'on aurait pu les améliorer en virant toute récursivité mais ça aurait demandé un gros effort de codage.

Bien que n'ayant parcouru ton code qu'à peine en diagonale (le temps me manque), je tiens à préciser que tu as très bien fait de présenter cette version.
Afficher les 7 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.