Défi chiffres des chiffres et des lettres, ia recherche en profondeur d'abord (pile lifo)
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 ;-)
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
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
- Défi chiffres des chiffres et des lettres, ia recherche en profondeur d'abord (pile lifo)
- Rib maroc 24 chiffres - Forum Visual Basic 6
- Sql decimal 2 chiffres après virgule - Forum SQL
- Pile ou face google - Forum Visual Basic 6
- Java arrondir 2 chiffres après virgule - Forum Java
- Convertir chiffre en lettre arabe delphi ✓ - Forum Delphi / Pascal
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.