ALGO : RESOLUTION "LE COMPTE EST BON" AVEC DES ARBRES BINAIRE
BruNews
Messages postés
21040
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
-
14 mai 2009 à 20:25
cs_panini21 Messages postés 11 Date d'inscription jeudi 21 août 2003 Statut Membre Dernière intervention 31 janvier 2007 - 18 mai 2009 à 15:47
cs_panini21 Messages postés 11 Date d'inscription jeudi 21 août 2003 Statut Membre Dernière intervention 31 janvier 2007 - 18 mai 2009 à 15:47
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/50017-algo-resolution-le-compte-est-bon-avec-des-arbres-binaire
https://codes-sources.commentcamarche.net/source/50017-algo-resolution-le-compte-est-bon-avec-des-arbres-binaire
18 mai 2009 à 15:47
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...
}
18 mai 2009 à 10:03
15 mai 2009 à 16:35
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
15 mai 2009 à 16:21
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 ...
14 mai 2009 à 23:49
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.
14 mai 2009 à 22:00
Joli.
Les deux code réalisent le même travail, mais de manière différentes. Mais dans ce cas, la récursivité est beaucoup plus rapide.
J'ai basé mon code sur l'idée de ne jamais avoir a refaire un calcul : calcul effectué une fois, stocké dans un conteneur set, puis réutilisable par un nœud de l'arbre plus profond que le nœud actuel.
De même, ton code ne refait pas 2 fois le même calcul, mais la manière dont sont stockés les calculs temporaires et relancés pour de nouveaux calcul sont terriblement plus efficace...
Je pense que le ralentissement vient du fait que je crée une multitude de conteneur ???
Jolie la manière pour garder une trace des résultats dans un tableau de char.
14 mai 2009 à 20:25
http://www.cppfrance.com/codes/CHIFFRES-LETTRES-WIN32_11289.aspx