Bonjour,
Cet article est la suite de "A Le compte est bon sur une page" et "B Le compte est bon en un clin d'oeil".
Il traite également les résultats les plus proches lorsqu'aucune solution exacte n'est trouvée.
A Le compte est bon sur une page.
B Le compte est bon en un clin d'oeil.
Le code complet obtenu tient sur le seul fichier "Presque.html" de moins de 3 Ko.
Algorithme
Tant qu'aucune solution exacte n'est trouvée, on retient les meilleurs approximations, c'est-à-dire les plus proches de la cible.
Mais aussi celles qui utilisent peu d'opérations.
On introduit la variable
nid pour désigner le meilleur "niveau" de la plus petite différence
diff trouvée.
La spécificité du code apparait dans l'initialisation et dans la fonction imbriquée
Recur(op):
function Recur(op) {
if (niv<0) { // aucune solution exacte n'est encore trouvée
if ((d=Math.abs(r-res))<=diff) { // bonne approximation
if ((d<diff)||(n>nid)) {str=""; diff=d; nid=n;}} // meilleure approximation: on élimine les autres
if (n==nid) str+=txt+b+op+a+"="+r+", différence = "+d; // ajoute l'approximation
}
}
nb[j]=r; Cal(nb,txt+b+op+a+"="+r+", "); nb[j]=b;
}
Lorsqu'on se contente de la première meilleure approximation rencontrée (mais pas forcément la plus courte), on peut simplifier cette fonction:
function Recur(op) {
if ((niv<0)&&((d=Math.abs(r-res))<diff)) str=txt+b+op+a+"="+r+", différence = "+(diff=d);
nb[j]=r; Cal(nb,txt+b+op+a+"="+r+", "); nb[j]=b;
}
Exemples de résultat
24 plaques: [1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,25,50,75,100]
6 tirages: [1,6,7,2,25,8] 131
25-6=19, 19×7=133, 133-2=131
7-2=5, 25×5=125, 125+6=131
25-2=23, 23×6=138, 138-7=131
==> 17488 appels à Cal()
6 tirages: [1,4,5,25,2,7] 767
5+1=6, 6×4=24, 25+7=32, 32×24=768, différence = 1
5+1=6, 25+7=32, 6×4=24, 32×24=768, différence = 1
5+1=6, 25+7=32, 32×4=128, 128×6=768, différence = 1
5+1=6, 25+7=32, 32×6=192, 192×4=768, différence = 1
25+7=32, 5+1=6, 6×4=24, 32×24=768, différence = 1
25+7=32, 5+1=6, 32×4=128, 128×6=768, différence = 1
25+7=32, 5+1=6, 32×6=192, 192×4=768, différence = 1
25+7=32, 32×4=128, 5+1=6, 128×6=768, différence = 1
==> 785738 appels à Cal()
6 tirages: [4,9,8,10,75,6] 633
75-4=71, 71×9=639, 639-6=633
==> 34740 appels à Cal()
6 tirages: [7,4,7,50,25,3] 631
7+7=14, 50×3=150, 150+14=164, 164×4=656, 656-25=631
50+7=57, 25×7=175, 175-3=172, 172×4=688, 688-57=631
50+7=57, 57×3=171, 171-7=164, 164×4=656, 656-25=631
25×7=175, 50+7=57, 175-3=172, 172×4=688, 688-57=631
25×7=175, 175-3=172, 172×4=688, 50+7=57, 688-57=631
25×7=175, 175-3=172, 172×4=688, 688-7=681, 681-50=631
25×7=175, 175-3=172, 172×4=688, 688-50=638, 638-7=631
25×7=175, 175-3=172, 50+7=57, 172×4=688, 688-57=631
7+7=14, 50×3=150, 150+14=164, 164×4=656, 656-25=631
50+7=57, 25×7=175, 175-3=172, 172×4=688, 688-57=631
50+7=57, 57×3=171, 171-7=164, 164×4=656, 656-25=631
25×7=175, 50+7=57, 175-3=172, 172×4=688, 688-57=631
25×7=175, 175-3=172, 50+7=57, 172×4=688, 688-57=631
25×7=175, 175-3=172, 172×4=688, 50+7=57, 688-57=631
25×7=175, 175-3=172, 172×4=688, 688-7=681, 681-50=631
25×7=175, 175-3=172, 172×4=688, 688-50=638, 638-7=631
50×3=150, 7+7=14, 150+14=164, 164×4=656, 656-25=631
50×3=150, 150+7=157, 157+7=164, 164×4=656, 656-25=631
50×3=150, 7+7=14, 150+14=164, 164×4=656, 656-25=631
50×3=150, 150+7=157, 157+7=164, 164×4=656, 656-25=631
==> 335612 appels à Cal()
6 tirages: [8,1,2,9,4,1] 824
2+1=3, 8×3=24, 9×4=36, 24-1=23, 36×23=828, différence = 4
2+1=3, 8×3=24, 24-1=23, 23×9=207, 207×4=828, différence = 4
2+1=3, 8×3=24, 24-1=23, 23×4=92, 92×9=828, différence = 4
2+1=3, 8×3=24, 24-1=23, 9×4=36, 36×23=828, différence = 4
2+1=3, 9×4=36, 8×3=24, 24-1=23, 36×23=828, différence = 4
9×4=36, 2+1=3, 8×3=24, 24-1=23, 36×23=828, différence = 4
9×4=36, 2+1=3, 8×3=24, 24-1=23, 36×23=828, différence = 4
2+1=3, 8×3=24, 24-1=23, 23×9=207, 207×4=828, différence = 4
2+1=3, 8×3=24, 24-1=23, 23×4=92, 92×9=828, différence = 4
2+1=3, 8×3=24, 24-1=23, 9×4=36, 36×23=828, différence = 4
2+1=3, 8×3=24, 9×4=36, 24-1=23, 36×23=828, différence = 4
2+1=3, 9×4=36, 8×3=24, 24-1=23, 36×23=828, différence = 4
==> 609670 appels à Cal()
Temps de calcul
Les tests pour les approximations compliquent un peu le calcul, surtout lorsqu'aucune solution exacte n'est trouvée.
Malgré cela, pour les tirages rencontrés sur mon ordi i5 3.2 GHz, aucun temps d'exécution n'a dépassé la seconde.
Remarques:
Les instructions qui concernent la variable
nCal servent à compter le nombre d'appels à la fonction
Cal() et sont donc provisoires.
La solution triviale (sans aucune opération) d'un tirage qui contient 100 avec le résultat 100 n'est pas détectée.
Versions suivantes
Comme déjà précisé précédemment, les doublons qui subsistent sont principalement dus à l'associativité d'opérations telles que
(a+b)+c = a+(b+c), (a×b)×c = a×(b×c), ...
et à la présence de plaques identiques au tirage ou pendant le calcul.
Pour encore limiter les solutions doubles, vaut-il mieux analyser et épurer les résultats trouvées, ou introduire la notion de
ligne de calcul comme par exemple
ici?
Bonne lecture et merci d'avance pour vos conseils ou critiques éventuels.
Testé avec: Chrome, Explorer, Firefox, Opera, Safari
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.