Le compte est bon

D'après le jeu "Des chiffres et des lettres" d'Armand Jammot (France 2)

 

Le principe du jeu

En choisissant 6 nombres (on peut choisir plusieurs fois le même) dans l'ensemble {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25, 50, 75, 100} et en leur appliquant les quatre opérations élémentaires (addition, soustraction, multiplication et division), il s'agit d'atteindre le résultat demandé (ceci est possible dans 94% des cas). Tous les résultats des calculs intermédiaires doivent être des nombres entiers positifs. Chacun des nombres (parmi ceux de départ et ceux obtenus par un calcul intermédiaire) ne peut être utilisé qu'une fois au plus. Si le résultat demandé ne peut pas être atteint, il faut l'approcher au plus près.

Il existe des programmes sophistiqués trouvant en quelques dixièmes de secondes toutes les solutions (voir références). Nous allons ici nous contenter d'une méthode naïve et peu efficace: il s'agira de rechercher aléatoirement des solutions et de ne garder que celle qui se rapproche le plus du résultat demandé.

 

Algorithme (pour 1 essai)

Données: six nombres dans une liste L et le résultat r à approcher.

  1. Choisir deux nombres a et b au hasard dans la liste L.
  2. Choisir une opération arithmétique (+, -, *, /) au hasard. L'opération doit être possible (par exemple, on ne peut pas diviser 5 par 9) et utile (il est inutile par exemple de multiplier un nombre par 1).
  3. Poser c := opération(a, b). Mémoriser ce calcul intermédaire dans une chaîne de caractères (une string).
  4. Éliminer a et b de la liste L.
  5. Ajouter c à la liste L.
  6. Si c = r alors afficher tous les calculs intermédiaires. STOP.
  7. S'il y a plus d'un nombre dans la liste L alors aller à 1 sinon afficher la liste des calculs intermédiaires et le résultat obtenu

On répétera cet algorithme des milliers de fois et on n'affichera que la meilleure solution trouvée.

Exemple (voir vidéo)

Atteindre 952 avec les nombres 25, 50, 75, 100, 3, 6.

100+3=103
103*6=618
618*75=46350
46350/50=927
927+25=952

solution trouvée après 13865 essais

Références

Applets java

Programmes Windows

Didier Müller, 12.11.09