ciel

Le compte est bon

Résolution par recherche exhaustive instantannée

Le principe du jeu

En choisissant 6 termes chacun 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é. Chacun des termes doit être utilisé au plus une fois. Si le résultat demandé ne peut être atteint, il faut l'approcher au plus près.
Le résultat le plus élégant est bien sûr celui faisant intervenir le moins de termes possibles.

L'algorithme utilisé

Je commence par calculer toutes les valeurs que l'on peut obtenir à partir de seulement 2 des éléments. En stockant ces résultats, il devient possible de calculer toutes les valeurs auxquelles on peut aboutir avec 3 des termes initiaux.
Par exemple, tous les résultats obtenus à partir des éléments {1 2 3} sont les résultats obtenus à partir de {1 2} qu'on peut encore ajouter, soustraitre, diviser ou multiplier par 3, ainsi que les résultats obtenus à partir de {1 3} auxquels on "applique" de même 2, et enfin les résultats obtenus à partir de {2 3} auxquels on "aplique" 3.
On peut ensuite calculer les résultats obtenus à partir de 4 éléments en considérant de même l'ensemble des partitions de ces 4 éléments en 2 sous-ensembles, puis avec 5 éléments, et enfin tous les 6.
On s'arrête dès qu'on obtient le résultat demandé.

L'intérêt par rapport à l'algoritme récursif est qu'on cherche d'abord la façon la plus simple d'obtenir un résultat que très souvent on peut obtenir sans utiliser tous les 6 éléments. Cet avantage est en fait minime, vu que le temps pour obtenir tous les résultats possibles est très court.
On peut aussi par certaines optimisations éviter d'effectuer plusieurs fois les mêmes opérations en ne regardant plus les résultats qu'on a déjà obtenu avec moins d'éléments.
Le coût de cette méthode est exponentiel (il y a 2n parties d'un ensemble de n nombres), alors que le coût de la méthode récursive brute est en n!. Il est vrai que les constantes ne sont pas les mêmes, et pour n petit la méthode récursive peut s'avérer moins couteuse.

L'inconvénient de cette méthode est l'occupation d'un espace mémoire très important, et la nécessité de structures plus complexes pour stocker tous les résultats "intermédiaires".

Voir aussi :


Conforme au standard HTML 4.01 Feuille de style CSS valide Page non-fumeur(c) JM11-04-2003 Me laisser un message Page d'accueil