Avant tout, quelles sont les contraintes à gérer ?
- le temps : moins de 45 secondes pour trouver serait pas mal, et bien moins serait encore mieux- les plaques : plus il y a de plaques dans les formules, plus c'est long à toruver
- les doublons : les doublons font des permutations inutiles, et donc du temps perdu, et le sujet est à la recherche du temps perdu ...
- la complexité des formules : plus il y a de parenthèses, plus c'est pénible à gérer, d'autant que certaines sont totalement superflues
- gérer les divisions pas entières
quelques problèmes résolus
il faut dire que pour résoudre la question, il aura fallu gérer un générateur de programmes, permettant de gérer les formules à analyser.la génération des formules
Suivant le nombre de plaques, les formules générées varient en nombre et en qualité :pour 2 plaques
la formule est de la forme a*b où "*" remplace un des 4 opérateurs standardIl y a juste une formule générique : a*b
pour 3 plaques
la formule est de la forme a*b*c avec possibilité de rajouter des parenthèsesIl y a 3 formules génériques : a*b*c , (a*b)*c et a*(b*c)
à priori, le nombre de formules développées devrait être de 3 * 4^2 , soit 48.
Il faut cependant supprier les "FIC", les Formules Inutilement Coplexes comme (a+b)+c qui est la même que a+b+c, beaucoup plus simple.
Les formules développées sont au nombre de 20, en voici quelques unes :
try { gerer( a*b*c,"a*b*c",a,b,c,0,0,0 ) ; } catch( ArithmeticException e) {}// try { gerer( a+b+c,"a+b+c",a,b,c,0,0,0 ) ; } catch( ArithmeticException e) {}
( ... )
// try { gerer( (a*b)*c,"(a*b)*c",a,b,c,0,0,0 ) ; } catch( ArithmeticException e) {}
try { gerer( a/b/c,"a/b/c",a,b,c,0,0,0 ) ; } catch( ArithmeticException e) {}
Les lignes commençant par // sont des FIC.
Le nombre réel est d'enviro 50% du nombre théorique, ce qui permet déjà de diviser par deux le temps de calcul pour 3 plaques.
Nombre de formules par plaque
2 : 13 : 3
4 : 11
5 : 45
6 : 217 ( ah, oui, cela fait beaucoup, et cela ne tient pas comptes des quelques 6! permutations possibles )
Pour 6 plaques, donc 5 opérateurs, le nombre de formules théoriques est de 217 * 4^5 soit 222.208, donc 222.208 * 6! pour les permutations, soit 160 millions à quelque chose près.
L'optimisation a donc son importance.
Générer les formules
Là aussi le problème est de taille, pour 3 plaques, la formule générale est "?a?*?b?*?c?", où chque "?" peut représenter un "cretain nombre de parenthèses ouvrantes et fermante, le tout devant donner une formule arithmétiquement correcte, et elle aussi optimisée.Typiquement, la formule a*(b*c)*d est valable, tout comme la formule a*((b*c))*d, sauf que là, il y a des parenthèses inutiles. Cette formule est à éliminer des formules utiles.
Son un PC dual core monothreadé tournant à 3 GHz, il aura fallu plus de 5 minutes à un programme java pour calculer TOUTES les formules plossibles pour 6 plaques. après optimisations expliquées ci-avant, ce temps passe à 90 secondes.
Concrétement
Concernant l'émission qui m'aura servi de référence pour "le mot le plus long" ( tirages consultables ici : http://fitness-greg.over-blog.com/article-pascal-a-encore-fait-une-bouchee-face-annick-119337317.html ), les tirages sont les suivants :new CompteEstBon( 5 , 9 , 25 , 2 , 7 , 5 , 782 ) ;
new CompteEstBon( 7 , 1 , 2 , 9 , 100 , 25 , 844 ) ;
new CompteEstBon( 4 , 5 , 1 , 9 , 8 , 6 , 607 ) ;
new CompteEstBon( 10 , 3 , 10 , 4 , 6 , 3 , 881 ) ;
new CompteEstBon( 2 , 3 , 5 , 4 , 7 , 9 , 205 ) ;
new CompteEstBon( 1 , 4 , 25 , 5 , 10 , 7 , 785 ) ;
Le programme s'arrête au calcul impliquant le moins de plaques possibles.
Afin d'éviter les doublons qui n'auraient pas (encore) été filtrés, le programme affiche au maximum 4 calculs exacts. Le programme ne va donc pas (encore) chercher les calculs approchés.
tirage : 5 9 25 2 7 5 = 782
secondes pour 2 plaques : 0.003secondes pour 3 plaques : 0.036
secondes pour 4 plaques : 0.09
782 = (5*5+9)*(25-2) // (a*b+c)*(d-e) [5,5,9,25,2,0]
782 = (5*5-2)*(9+25) // (a*b-c)*(d+e) [5,5,2,9,25,0]
782 = (5*5-2)*(25+9) // (a*b-c)*(d+e) [5,5,2,25,9,0]
782 = (9+5*5)*(25-2) // (a+b*c)*(d-e) [9,5,5,25,2,0]
secondes pour 5 plaques : 0.749
secondes pour 999 plaques : 0.889
Le programme trouve plusieurs résultats ( dont 50% de permutations ) en moins de 1 seconde pour 5 plaques.
Le résultat a été trouvé pour 5 plaques. Le résultat de l'émission est constitué de 6 plaques. Il faut dire que les tables de 23 et de 34 sont généralement assez peu utilisées.
tirage : 7 1 2 9 100 25 = 844
secondes pour 2 plaques : 0.001secondes pour 3 plaques : 0.006
secondes pour 4 plaques : 0.139
844 = (7+2)*(100-9)+25 // (a+b)*(c-d)+e [7,2,100,9,25,0]
844 = (1-7+100)*9-2 // (a-b+c)*d-e [1,7,100,9,2,0]
844 = ((1-7+100)*9)-2 // ((a-b+c)*d)-e [1,7,100,9,2,0]
844 = (1+100-7)*9-2 // (a+b-c)*d-e [1,100,7,9,2,0]
secondes pour 5 plaques : 1.076
secondes pour 999 plaques : 1.222
Similaire au résultat trouvé. Les 2° et 4° solutions sont les mêmes aux permutations près.
tirage : 4 5 1 9 8 6 = 607
secondes pour 2 plaques : 0.0secondes pour 3 plaques : 0.001
secondes pour 4 plaques : 0.052
secondes pour 5 plaques : 2.159
secondes pour 6 plaques : 50.656
secondes pour 999 plaques : 52.871
Cas typique de résultat exhaustif non trouvé ( 51 secondes pour les 6 plaques )
Vu les temps indiqués pour les 2, 3, 4 et 5 plaques, le temps total pour gérer les 6 plaques ( 51 secondes ) est hors cadre. Il doit encore manques des optimisations.
Dans l'émission, un résultat approché à 608 a été trouvé.
tirage : 10 3 10 4 6 3 = 881
secondes pour 2 plaques : 0.0secondes pour 3 plaques : 0.001
secondes pour 4 plaques : 0.021
secondes pour 5 plaques : 0.618
secondes pour 6 plaques : 13.345
secondes pour 999 plaques : 13.986
Idem, et résultat approché trouvé à 880
Remarque : avec 2 plaques identiques, le temps de traitement des 6 plaques passe globalement de 50 secondes à 15 secondes.
tirage : 2 3 5 4 7 9 = 205
secondes pour 2 plaques : 0.0secondes pour 3 plaques : 0.001
secondes pour 4 plaques : 0.045
205 = (2+3)*(5+4*9) // (a+b)*(c+d*e) [2,3,5,4,9,0]
205 = (2+3)*(5*9-4) // (a+b)*(c*d-e) [2,3,5,9,4,0]
205 = (2+3)*(5+9*4) // (a+b)*(c+d*e) [2,3,5,9,4,0]
205 = (2+3+4*9)*5 // (a+b+c*d)*e [2,3,4,9,5,0]
secondes pour 5 plaques : 0.083
secondes pour 999 plaques : 0.13
Similaire à l'émission. La 4° solution proposée est bien plaisante.
tirage : 1 4 25 5 10 7 = 785
secondes pour 2 plaques : 0.0secondes pour 3 plaques : 0.002
secondes pour 4 plaques : 0.106
785 = ((25-4)*7+10)*5 // ((a-b)*c+d)*e [25,4,7,10,5,0]
785 = (((25-4)*7)+10)*5 // (((a-b)*c)+d)*e [25,4,7,10,5,0]
785 = 25*(5*7-4)+10 // a*(b*c-d)+e [25,5,7,4,10,0]
785 = (25*(5*7-4))+10 // (a*(b*c-d))+e [25,5,7,4,10,0]
secondes pour 5 plaques : 1.23
secondes pour 999 plaques : 1.341
Similaire à l'émission
Conclusion
- des permutations difficiles à gérer- des optimisations ( ? ) concernant les 6 plaques
- calculs approchés à prévoir
- gestion des plaques en double
- gestion "améliorée" des traitements des formules allant des calculs simples aux calculs complexes
- des chronos la plupart du temps très réduits
- le cas des 6 plaques encore problématique.
quelques références en ligne
non exhaustif bien évidemmenthttp://www.langue-au-chat.fr/tricher-au-compte-est-bon/
http://fitness-greg.over-blog.com/
Aucun commentaire:
Enregistrer un commentaire