[logiciel] Le compte est-il bon?

Le Compte est Bon est ma version PC du ‘jadis’ jeu télévisé Des Chiffres et Des Lettres – partie Chiffres seulement. On dispose de 6 nombres ou chiffres tirés au hasard parmi:

  • les 9 premiers chiffres (1, 2, 3, 4, 5, 6, 7, 8, 9)
  • les nombres : 10, 25, 50, 100

On tire au hasard un nombre compris entre 100 et 999. Le but est alors d’atteindre ce nombre en utilisant les 6 nombres précédents avec les quatre opérations arithmétiques élémentaires :

  • addition
  • soustraction
  • multiplication
  • division

Le logiciel permet notamment de trouver les solutions (au maximum 99 en moins d’une seconde) et de les afficher, il permet aussi de créer ses propres tirages avec un compte à trouver.

[Télécharger] Tout simplement *ICI*, et comme à l’habitude un fichier à décompresser dans le répertoire au choix.

Exemle: un tirage et présentation d’une des 28 solutions possibles pour ce tirage.

Apercu du logiciel Une des 28 solutions possibles pour ce tirage

[Complément] Programmation sur ordinateur

En raison du temps limité dont on disposait, la programmation du jeu sur ordinateur fut jadis délicate pour des raisons d’explosion combinatoire. La solution approchée la plus simple était d’utiliser une technique de branch and bound qui donnait au moins ce qui a été trouvé de plus proche de l’objectif au cours des essais. Diverses heuristiques sont imaginables pour l’exploration de l’arbre. Cette contrainte disparaît pour un petit nombre de chiffres et une machine rapide de la classe de celles existant aujourd’hui. Voir la suite de ce texte sur Wikipedia.

Calcul: Plus ou moins ceci:

On dispose de 6 plaques {p1,p2,p3,p4,p5,p6}, on choisit 2 plaques parmi ces 6 plaques :
Il y a donc = 6
x5/2 = 15 combinaisons :
{(p1,p2),(p1,p3),(p1,p4),(p1,p5),(p1,p6),(p2,p3),(p2,p4),(p2,p5),(p2,p6),(p3,p4),(p3,p5),(p3,p6),(p4,p5),(p4,p6),(p5,p6)}

Pour chacun des couple (pi,pj), on dispose des 4 opérations arithmétiques.
La soustraction et la division n’étant pas commutative, il faut aussi penser à l’inverse :
pi – pj et aussi pj – pi
pi / pj et aussi pj / pi

Remarque :

p1 + p2 = p2 + p1 (commutativité de l’addition)
p1
x p2 = p2 x p1 (commutativité de la multiplication)

En y regardant de plus près, seules les valeurs positives nous intéressent :
Hors si p1 – p2 > 0 alors p2 – p1 < 0
Et si p1 – p2 > 0 alors p1> p2 et p2 / p1 n’existe pas (valeur non entière).

On peut donc tester le couple (pi,pj) et faire ensuite la soustraction qui est positive :
pi – pj ou pj – pi.
Si la soustraction est nulle, on peut éliminer le calcul, la valeur nulle ne pouvant nous aider dans la recherche de solutions.

On fait de même la division pi / pj ou pj / pi suivant le test.
Ce qui ramène le couple (pi,pj) à quatre opérations arithmétiques (la multiplication et surtout la division étant les plus coûteuses).
Si pi ou pj dans la multiplication (ou la division) est de valeur 1, alors pi
x pj = pi ou pj (pi / pj = pi si pj = 1) et donc ces opérations ne font pas avancer le calcul et la recherche de solutions :
On peut donc éliminer ces cas également.
Si la division n’existe pas dans N, ce qui est très fréquent, on évite une opération de plus, ce qui donne en tout moins de 4 opérations en moyenne par couple (pi,pj).

On a donc 15 couples (pi,pj), et au plus 4 opérations pour chacun de ces couples, soit au plus 60 opérations pour les 2 premières plaques.

Supposons l’opération pi + pj :
La valeur calculée peut être considéré comme une nouvelle plaque.

On se retrouve alors avec le même problème mais avec 5 plaques et non plus avec 6 (2 plaques remplacées par le résultat de l’opération entre ces 2 plaques).

C’est donc là que la récursivité intervient :

On dispose désormais de 5 plaques, on choisit 2 plaques parmi ces 5 plaques :
il y a donc = 5
x4/2 = 10 combinaisons.
Si par exemple p1 et p2 étaient les 2 premières plaques utilisées et si p1 devenait le résultat de la première opération de p1 et p2, on a ces 10 combinaisons :
{(p1,p3),(p1,p4),(p1,p5),(p1,p6),(p3,p4),(p3,p5),(p3,p6),(p4,p5),(p4,p6),(p5,p6)}

On fait le même raisonnement avec 4 plaques, 3 plaques, puis 2 plaques.

Dès qu’il ne reste plus qu’une seule plaque, on remonte dans l’algorithme récursif.

A chaque niveau de récursion, on vérifie si le résultat de l’opération faite au niveau de récursion précédent n’est pas le résultat qu’on cherche (simple test sur la nouvelle plaque issue des 2 anciennes : si p1 est toujours le résultat de l’opération précédente, on teste simplement si p1 est le résultat qu’on cherche).

On peut calculer la complexité de cet algorithme dans le pire des cas :

x 4 x x 4 x x 4 x x 4 x x 4 = 15 x 4 x 10 x 4 x 6 x 4 x 3 x 4 x 1 x 4 = 15 x 10 x 6 x 3 x 45 = 2 764 800 opérations

2 764 800 opérations dans le pire des cas, c’est vraiment faible pour les ordinateurs actuels.

En plus, l’expérience par le calcul montre même que 400 000 à 1 500 000 opérations sont souvent suffisantes :

  • En effet, la division est dans la plupart des cas non réalisables (une opération de moins sur les 4).
  • La multiplication et la division avec une (ou deux) opérande(s) à 1 peuvent être évité.
  • Une soustraction nulle peut aussi être évité.

Ces suppressions d’opérations dans la recherche divisent presque par trois la recherche dans certains cas (les meilleurs) !
2 764 800 opérations dans le pire des cas à 400 000 opérations pour les meilleurs cas (encore moins pour le meilleur des cas qui doit être le tirage avec que des 1 : 38 206 opérations).

Le pire des cas tel qu’il est envisagé est en plus très improbable, même inexistant vu les critères mis en jeu !

Publicités

3 Responses to [logiciel] Le compte est-il bon?

  1. Laurent dit :

    Très bien ce jeu – gros merci. Laurent.

  2. Vasya dit :

    preved ot slesarya Vasi

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

%d blogueurs aiment cette page :