Résumé : il y a plusieurs façons de résoudre des problèmes. Une méthode consiste à vérifier toutes les solutions possibles et à rechercher la meilleure, on parle alors de recherche combinatoire. Le jeu le «compte est bon» permet d’observer le fonctionnement de cette méthode. Il faudra évidemment également être capable d’estimer le nombre d’opérations à mettre en œuvre pour conclure sur la faisabilité pratique de la méthode.
Mots-clés : combinatoire, complexité, récursivité.
Solutions :
la solution actuellement proposée est donnée par les fichiers MatLab : CompteBonDemo.m, solution.m, DemoTexte.m, nouveau.m, solDeb.m, verif.m et plaque.m.
Nouveau :
une version iPhone: Le compte est bon
Liens :
thèmes
de plus
Le compte est bon
L’exercice s’inspire de l’article La récursivité au secours du «Compte est Bon» de Jean-Christophe Riat, Quadrature No 19.
Dans son introduction, Jean-Christophe Riat explique : «Face à un problème ludique, le premier réflexe est de regarder si les mathématiques permettent d’y apporter une solution. Il est toujours préférable de s’appuyer sur des résultats de cette science, plutôt que de tenter de programmer des méthodes «empiriques» de résolution. Il est par exemple totalement inutile de se creuser la tête lorsqu’il est possible de ramener le problème à un système d’équations linéaires, ou à une équation du second degré !
Lorsque les mathématiques restent impuissantes (ou plus généralement lorsque le programmeur ignore les travaux des mathématiciens !), il est nécessaire de déterminer un méthode spécifique de résolution. (...)
La première idée qui vient à l’esprit est de construire de manière exhaustive l’ensemble des combinaisons possibles. La recherche est terminée quand une solution est trouvée ou quand toutes les possibilités ont été envisagées sans succès. Pour savoir si une telle approche est réaliste, il est nécessaire d’en calculer la complexité. En fonction de la puissance de calcul disponible, l’estimation du nombre d’opérations à réaliser permet d’évaluer le temps de calcul nécessaire et donc de conclure à la faisabilité pratique de la méthode.»
Le jeu du «Compte e
st Bon» fait partie de l’émission télévisée «Des Chiffres et des Lettres». On tire six plaques au hasard contenant un nombre ; puis on doit calculer à l’aide des quatre opérations arithmétiques élémentaires un total tiré au hasard entre 100 et 999. Les plaques peuvent valoir : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25, 50, 75 et 100. Tous les calculs doivent être effectués sur des nombres entiers. Si le total n’est pas atteint, on recherche le nombre le plus proche.
Exemple : 50 & 10 & 10 & 5 & 4 & 2 pour obtenir 768.
Dans la première étape, on peut choisir 2 plaques parmi 6, il y a donc C62 = 15 couples possibles. Pour chaque couple, il y a quatre opérations envisageables (produit, addition, soustraction et division). On a donc 4 × 15 = 60 calculs différents. Après chaque calcul, il reste quatre plaques et une valeur calculée que l’on peut considérer comme une nouvelle plaque. On peut recommencer le raisonnement avec cinq plaques et on obtient alors (ce qui reste à vérifier) 2’764’800.
Ce résultat impressionnant au premier abord est une limite maximale. C’est rare en effet que toutes les opérations soient faisables (en particulier, les divisions). On peut réduire alors ce chiffre à environ un million d’opérations.
Un ordinateur peut aisément effectuer ces calculs relativement rapidement. La recherche se termine alors lorsque l’on a trouvé une solution ou lorsque tous les cas ont été observés, lorsque le problème n’a pas de solution.
Indications
La méthode peut s’exprimer comme suit : pour chaque couple de plaques, pour chaque opération arithmétique on effectue le calcul, soit on trouve le résultat demandé soit on remplace les deux plaques par le résultat du calcul. On recommence cette opération sur les plaques restantes de façon récursive.
A la manière dont on se déplace sur un arbre informatique, on explore une branche de l’arbre, si l’on arrive à une extrémité qui n’est pas la solution recherchée on remonte dans l’arbre et l’on explore une nouvelle branche.
Dans l’exemple ci-dessous, on prend les deux premières plaques 6 et 5. On considère la première opération, la multiplication, on obtient donc 30. On prend alors le produit 30 × 4 = 120 et on poursuit l’exploration. Lorsque l’on arrive au cas pour lequel il reste deux plaques 720 et 1 on constate que l’on est dans une impasse, on remonte alors au niveau précédent et on retrouve 360 et 2. On passe alors en revue les autres opérations. Là encore, c’est une impasse, on doit alors remonter au niveau 120, etc.
