Défi chiffres des chiffres et des lettres, ia recherche en profondeur d'abord (pile lifo)

Soyez le premier à donner votre avis sur cette source.

Vue 11 475 fois - Téléchargée 643 fois

Description

Un algo de résolution des défis chiffres du très connu jeu télévisé "Des chiffres et des lettres".

L'interface: vous entrez 6 nombres allant de 1 à 65535 (aucun test n'est effectué sur les valeurs, à vous de répondre correctement aux attentes du programmes ;-)) et un 7ème nombre qui est la "cible" (même restrictions).

Typiquement, on entrera des nombres entre 1 et 100 pr les 6 premiers, et un nombre entre 100 et 999 pour la cible. Notez que cela ne change rien ...

Les règles: on peut utiliser deux nombres des 6 et leur appliquer une transformation (addition, soustraction, multiplication et division, sous réserve d'obtenir des nombres non nuls, positifs et entiers). On obtient donc une nouvelle liste de "nombres utilisables": les 4 non utilisés et le résultat de l'opération. On recommence jusqu'à ce qu'on atteigne le nombre cible (on ne doit pas tout utiliser).

La méthode de l'algo: la recherche en profondeur d'abord. Cela s'apparente presque à du brute force, à ceci près qu'il est ... euh ... ben non, moi je trouve qu'il a rien d'intelligent cet algo, mais on le classe dans les algos d'IA donc moi je suis l'avis commun, je vais pas me prononcer sur des choses que je connais pas ^^

Le principe: basiquement on empile les différents états que l'on peut obtenir à partir d'un état donné sur une ... pile, et... armf, c'est long à expliquer. Lisez ce document-ci, très bien fichu: http://glinfrench.apinc.org/IMG/zip/ia_1.zip
bonne lecture ;-)

Source / Exemple :


Je vous mets juste la boucle de l'algo ici (itératif, BruNews devrait aimer ^^). Téléchargez le zip pr un projet Dev-C++, le code complet et un exécutable Win32 (note: le code devrait être parfaitement portable, je n'ai utilisé que la STD).

  while(!Etats.empty())
  {
   Etat e = Etats.top();
   Etats.pop();
   //est-ce que "e" est une solution?
   if(e.Comporte(Objectif)){
    soltrouvee = true;
    cout << e;
    cin.get();
    break;
   }
   //sinon, on génère ses successeurs directs (une seule opération) et on les empile
   GenererSuccesseurs(e);
  }

Conclusion :


Note: l'idée de ce code m'est venue en lisant celui de mickaeliazerty (http://www.cppfrance.com/code.aspx?ID=23428). Je ne sais pas trop le quel est le plus rapide, mais le mien est moins performant, en ce sens que si le problème n'a pas de solution, je me contente de le dire, alors que l'algo de mickaeliazerty précise quelle "solution" était la plus proche.

exemple de résultat obtenu:

Nombre disponible 1: 7
Nombre disponible 2: 69
Nombre disponible 3: 54
Nombre disponible 4: 12
Nombre disponible 5: 15
Nombre disponible 6: 3
Entrez le nombre a atteindre (objectif): 950
15 / 3 = 5
54 + 12 = 66
69 + 66 = 135
7 * 135 = 945
945 + 5 = 950

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

? Ils ont une formation avant prologin ?

je trouve ça carrément vexant -_-
Messages postés
365
Date d'inscription
vendredi 24 mai 2002
Statut
Membre
Dernière intervention
18 octobre 2004

Non non, c'est juste que j'aide Mathias pour l'entrainement des candidats IOI.

22h ? dommage tu pourras pas participer a la partie de gonflage de matelas ou de 'testage' des machines..
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

comment ça déjà? t'es à l'epita? tu peux pas participer alors?
je pars vendredi soir, j'arriverai vers 22h :)
Messages postés
365
Date d'inscription
vendredi 24 mai 2002
Statut
Membre
Dernière intervention
18 octobre 2004

Yes, a bientot !

ps: j'y suis deja en fait..
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

AVRIL PROCHAIN !!

:D

Trop content, vendredi prochain -> prologiiiiiiiiin :)

PS: je PEUX flooder, c'est MON code :p
Afficher les 28 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.