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 France à partir de 1965 (il s'appelait alors "Le Mot le plus long"), puis fut renommé sous son appelation définition "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.3. 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 :

Cette fonction va rechercher toutes les solutions au problème. Dès qu'on aura réaliser un calcul on ajoute 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 choisi deux plaques $a$ et $b$ puis on essaye de rechercher la cible par utilisation de $a+b$, $a-b$, $a×b$ et $a/b$ si ces opérations sont valides.
  1. pour toute plaque dans plaques_restantes faire
  2.     si plaque == cible alors
  3.         afficher "Solution"
  4.         retour
  5.     fin si
  6. fin pour
  7.  
  8. pour tout i dans l'intervalle [1, taille(plaques_restantes) - 1] faire
  9.     pour tout j dans l'intervalle [i+1, taille(plaques_restantes) ] faire
  10.  
  11.         a = plaques_restantes[i]
  12.         b = plaques_restantes[j]
  13.  
  14.         supprimer a et b (ou les éléments aux indices i et j) de plaques_restantes
  15.  
  16.         si a + b < 1000 alors
  17.             resoudre( plaques_restantes + [ (a+b) ], cible)
  18.             supprimer (a+b) de plaques_restantes
  19.         fin si
  20.  
  21.         si a - b > 0 alors
  22.             resoudre( plaques_restantes + [ (a-b) ], cible)
  23.             supprimer (a-b) de plaques_restantes
  24.         fin si
  25.  
  26.         si a * b < 1000 alors
  27.             resoudre( plaques_restantes + [ (a*b) ], cible)
  28.             supprimer (a*b) de plaques_restantes
  29.         fin si
  30.  
  31.         si (b > 1) et (a est divisible par b) == 0 alors
  32.             resoudre( plaques_restantes + [ (a/b) ], cible)
  33.             supprimer (a/b) de plaques_restantes
  34.         fin si
  35.  
  36.  
  37.     fin pour
  38. fin pour

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 64 solutions
  • cible = 899, selection_de_plaques = [3,5,8,9,9,25], on doit obtenir 2 solutions
  • cible = 897, selection_de_plaques = [3,5,8,9,9,25], il n'y a pas de solution

Attention certaines solutions sont identiques.

10.4. 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.5. Troisième version

Exercice 10.3

Modifiez le sous-programme resoudre afin de lui adjoindre un troisième paramètres 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
['5+25=30', '3*30=90', '9+90=99', '9*99=891', '8+891=899']
Solution
['5+25=30', '3*30=90', '9+90=99', '9*99=891', '8+891=899']
nombre de solutions=2

10.6. 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