C Le compte est bon ou presque

Télécharger le projet
Commenter

Description

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
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (William VOIROL)