Site de Jean-Michel RICHER

Maître de Conférences en Informatique à l'Université d'Angers

Ce site est en cours de reconstruction certains liens peuvent ne pas fonctionner ou certaines images peuvent ne pas s'afficher.


stacks

10. TP - Le compte est bon

10.1. Introduction

On s'intéresse à la résolution du problème "Le compte est bon" issu du jeu "Des Chiffres et des Lettres" créé par le producteur français Armand Jammot, jeu télévisé français diffusé sur Antenne 2 (maintenant France 2) à partir de 1965 (il s'appelait alors "Le Mot le plus long"), puis fut renommé sous son appelation "Des chiffres et des lettres" à partir de 1972.

Le but du "Compte est bon" est d'obtenir un nombre cible généré aléatoirement compris entre 101 et 999 à partir d'opérations élémentaires (addition, soustraction, multiplication, division entière) sur des entiers naturels, en utilisant 6 plaques tirées au hasard parmi un ensemble de plaques qui comportent des nombres dans la liste [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25, 50, 75, 100].

À défaut de trouver le compte exact, il faut tenter de s'approcher le plus près possible du nombre cible.

On va ici considérer que le nombre cible est atteignable par les 6 plaques tirées aléatoirement.

10.2. Programme

10.2.1. Première version

Dans un premier temps, on va écrire dans le fichier le_compte_est_bon.py, un sous-programme resoudre qui prend deux paramètres :

  • plaques_restantes qui contient la liste des plaques qui n'ont pas encore été utilisées
  • cible qui est le nombre à trouver

Cette fonction va rechercher toutes les solutions au problème de manière récursive. Dès qu'on aura réalisé un calcul, on ajoutera le résultat de ce calcul aux plaques restantes. Il faudra le retirer pour passer à l'opération suivante. Par exemple à partir des plaques 3 et 5 et de la multiplication on génère 15. On retire 3 et 5 des plaques restantes et on y ajoute 15.

L'algorithme de la fonction est le suivant :

Procédure resoudre(plaques_restantes, cible)
Entrée
  • plaques_restantes (liste d'entiers) : plaques restantes pour les calculs
  • cible (entier) : nombre à atteindre par les calculs
Sortie Aucune, on affichera "Solution" si on trouve une solution
Variables
locales		 $a$ et $b$ les deux plaques choisies à chaque itération
Description on choisit deux plaques $a$ et $b$ puis on essaye de rechercher la cible par utilisation des quatre opérations arithmétiques si elles sont valides :
  • $a+b$
  • $a-b$
  • $a×b$
  • $a/b$
Afficher le code    ens/l1/python1/tp10_le_compte_est_bon/resoudre.algo
  1.  
  2. # arrêt de la récursivité si solution trouvée
  3. pour plaque dans plaques_restantes faire
  4.     si plaque == cible alors
  5.         afficher "Solution"
  6.         sortir
  7.  
  8. # en algorithmique les éléments d'un container débutent à l'indice 1
  9. # on tente de résoudre récursivement le problème en essayant tous
  10. # les calculs possibles, il faut que le résultat d'une opération
  11. # reste dans l'intervalle [1, 999]
  12. pour i dans [1 : taille(plaques_restantes)] faire
  13.     pour j dans [1 : taille(plaques_restantes) ] faire
  14.  
  15.         si i != j alors
  16.             a = plaques_restantes[i]
  17.             b = plaques_restantes[j]
  18.  
  19.             créer une liste plaques_a_garder qui est une copie de
  20.             plaques_restantes sans les éléments a et b
  21.            
  22.             si a + b < 1000 alors
  23.                 # le premier + représente la concaténation de liste
  24.                 # le second + représente l'addition
  25.                 resoudre( plaques_a_garder + [ (a+b) ], cible)
  26.  
  27.             si a - b > 0 alors
  28.                 resoudre( plaques_a_garder + [ (a-b) ], cible)
  29.                
  30.  
  31.             si a * b < 1000 alors
  32.                 resoudre( plaques_a_garder + [ (a*b) ], cible)
  33.                
  34.  
  35.             si (b > 1) et (a est divisible par b) == 0 alors
  36.                 resoudre( plaques_a_garder + [ (a/b) ], cible)
  37.                
  38.  
  39.  

Exercice 10.1

Ecrire le programme correspondant et le tester avec

  • cible = 355, selection_de_plaques = [1,4,5,7,7,9], on doit obtenir 2460 solutions
  • cible = 899, selection_de_plaques = [3,5,8,9,9,25], on doit obtenir 192 solutions
  • cible = 722, selection_de_plaques = [3,5,8,9,9,25], il n'y a pas de solution

Attention certaines solutions sont identiques.

10.2.2. Deuxième version

Exercice 10.2

Modifiez le programme précédent afin de compter le nombre de solutions et d'afficher combien de solutions ont été trouvées.

10.2.3. Troisième version

Exercice 10.3

Modifiez le sous-programme resoudre afin de lui adjoindre un troisième paramètre qui correspondra aux opérations effectuées, il s'agira d'une liste de chaînes de caractères.

Ainsi, avec cible = 899 et selection_de_plaques = [3, 5, 8, 9, 9, 25], vous devriez obtenir :

Solution 1:  ['3+9=12', '8*9=72', '5+72=77', '12*77=924', '924-25=899']
Solution 2:  ['3+9=12', '8*9=72', '5+72=77', '77*12=924', '924-25=899']
Solution 3:  ['3+9=12', '8*9=72', '72+5=77', '12*77=924', '924-25=899']
Solution 4:  ['3+9=12', '8*9=72', '72+5=77', '77*12=924', '924-25=899']
...
Solution 191:  ['25+9=34', '34*9=306', '306-8=298', '298*3=894', '5+894=899']
Solution 192:  ['25+9=34', '34*9=306', '306-8=298', '298*3=894', '894+5=899']
nombre de solutions=192

Note : on trouve plusieurs fois la même solution car il y a deux plaques 9.

10.3. Améliorations

S'il vous reste du temps, tentez d'apporter les améliorations suivantes à votre programme :

  1. générez le nombre cible aléatoirement dans l'intervalle [101,999]
  2. générez aléatoirement les plaques
  3. faire en sorte de s'approcher le plus possible du nombre cible s'il n'est pas atteignable avec les 6 plaques choisies