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

Atteindre 732 avec les nombres 2, 25, 4, 10, 7, 6.

Une solution exacte a été trouvée après 492 essais:

25*7=175
6+2=8
175+10=185
185*4=740
740-8=732

Exercice

Programmez l'algorithme décrit ci-dessus dans Mathematica. Écrivez tout d'abord un module qui effectuera, sur deux nombres donnés, une opération arithmétique valide choisie au hasard.

Fonctions Mathematica utiles: Abs, AppendTo, Delete, FromCharacterCode, If, Length, Module, Print, Random, StringJoin, ToString, Which, While.

Le fichier Mathematica complet est disponible, mais seulement pour les visiteurs autorisés!
Mot de passe :

Références

Applets java

Programmes Windows

Didier Müller, 25.2.03