CodeS-SourceS est hébergé par Frontier.fr

Cliquez ici pour mettre ce site au démarrage de votre navigateur

AccueilCodesTutorielsForumsEmploiLivresGuide achatConnexion

begin process at 2009 07 05 08:48:06

SILVERLIGHT 3 : COMMUNICATION ET MULTICAST par KooKiz

[PERSO] DéCOUVERTES ESTIVALES : LINUX (PART I) par FREMYCOMPANY

[REFACTORING] RESHARPER POUR VISUAL STUDIO 2010 (PREVIEW) par tja

[REFACTORING] ANALYSER VOS EXCEPTIONS AVEC RESHARPER EXCEPTIONAL par tja

SHAREPOINT 2007 : PATTERNS & PRACTICES SHAREPOINT GUIDANCE par phil

RE : TRAITEMENT D'UN FICHIER par boualiasma

TRAITEMENT D'UN FICHIER par boualiasma

RE : [QT] PROBLèME D'ENREGISTREMENT DE FICHIERS par magicienap

OWNER DRAWN COMBOBOX - SCINTILLEMENT EXCESSIF par Hades53

RE : DISQUE DUR SATA par ghuysmans99

+ de logiciels à télécharger

1 464 568 membres
72 nouveaux aujourd'hui
15 045 membres club

Trouver une ressource

Trouvez une ressource parmi 40 096 codes, 1 302 925 messages d'aide etc...

Recherche: dans [ Dernières recherches ]

Filtre:Tous les codes.NET uniquementExclure .NET

Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

DÉFI CHIFFRES DES CHIFFRES ET DES LETTRES, IA RECHERCHE EN PROFONDEUR D'ABORD (PILE LIFO)

Information sur la source

Catégorie :Maths & Algorithmes Niveau : Débutant Date de création : 11/06/2004 Vu / téléchargé: 5 373 / 351

Auteur : Kirua

Site perso

Ecrire un message privé

Note :

8,33 / 10

Commentaire sur cette source (28)

Ajouter un commentaire et/ou une note

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

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);
}

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

Fichier Zip

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

ChiffresSansLettres.dev880 octets
ChiffresSansLettres.exe221 184 octets
main.cpp 10 120 octets

Télécharger le zip

Sources du même auteur

PARTICLE ENGINE 2D OPENGL DEV-C++ - EFFETS DE FEU ETC [ MOTE...

SIMULATION DE LA GRAVITATION SELON NEWTON (OPENGL / DEVC++)

CLASSE DE VECTEURS EN 2D / 3D PORTABLE, UTILISATION POUR SIM...

SNAKE 3D OPENGL DEV C++

TEMPS DEPUIS LE DÉMARRAGE DE WINDOWS

Toutes les sources de Kirua

Sources de la même categorie

ALGORITHME DE BRUTEFORCE POUR LES CRACKERS par oh1234

ALGORITHMES D'OPTIMISATION NON LINÉAIRE: DESCENTE DE GRADIEN... par Pistol_Pete

RESOLUTION DE SYSTEME LINEAIRE PAR LA METHODE DU GRADIENT CO... par zangul

CALCULATRICE AVEC REPRESENTATION GRAPHIC par msavyo1

POLYNOME AVEC LISTE DOUBLEMENT CHAINÉ par redoualinho

Toutes les sources de la catégorie Maths & Algorithmes

Commentaires et avis

Commentaire de neo_00110010101 le 11/06/2004 23:09:25

j'ai fait 3 essais avec 6 nombres disponibles < 100 et un objectif < 1000 et j'ai eu 3 bonnes solutions !
Donc le programme marche mais il marche très bien même :]

quant à savoir lequel est le plus rapide ... je ne pense pas que la différence soit visible.

Commentaire de Kirua le 11/06/2004 23:14:20

j'ai jamais eu de cas où il arrivait pas à résoudre, sauf quand je lui donne 6 "1" et "7" comme but, argnangnangangna ]:-D (*diablotin*)

l'IA m'intéresse de plus en plus, je lis des documents sur l'algo MINIMAX et son amélioration Alpha-Beta depuis hier. Si quelqu'un sait où je peux trouver des codes sources commentés en C/C++, si possible un tic tac toe, qui me paraît l'exemple le plus simple, me le dire ;-)

j'ai plus des masses envie de faire un GUI pour ce programme-ci. ce qui est amusant c'est d'écrire l'algo, après qd ça marche, y a plus de plaisir ^^

Commentaire de neo_00110010101 le 11/06/2004 23:22:17

bien sûr que j'ai ça :)
moi aussi je commence à apprécier l'IA (pathfinding pour l'instant et pê les reseaux neuronaux ensuite ...)
Si tu veux des sources en C++ (tictactoe par exemple) c'est ici :

http://www.startjeux.com/index.php?page=96

y'a un peu de tout en ce qui concerne l'IA bien sûr ! des algorithmes, des scripts d'heuristique, des scripts de recursion, des scripts de reconnaissance ...

sinon sur google il y a des tonnes de choses magnifiques !!! mais je ne pourrais pas mettre tous les liens !
Bon code :)

Commentaire de Kirua le 11/06/2004 23:33:20

google est mon maître à penser ;-) j'ai une longue histoire avec elle (bah oui, autant s'imagienr que c'est une femme (plantureuse si possible)). Ce qui nous amène à dire qu'elle est ma maîtresse à penser... Passons.

Merci pr le lien, je vais voir ça de suite. J'ai pas mal lu sur les algos génétiques sinon, et j'ai voulu créer un algo de résolution du problème du voyageur de commerce, bien connu. J'ai eu des problèmes mémoires que je comprennais pas, parce que obscursis par la STL et j'ai laché l'affaire, mais si je recommençais mtnt ce serait sûrement plus propre!

Commentaire de neo_00110010101 le 12/06/2004 11:19:39

ton numéro de tel ne marche pas (0900 12 34 56) ... ^_^ et ton projet de rpg est stoppé ? (sur ton site) parce qu'il avait l'air excellent (manquait plus qu'un brin de multijoueur online et tu le transfomais en MMORPG)

Commentaire de Kirua le 12/06/2004 11:44:34

ben il lui manque surtout un système de menus (qui, crois-moi, est super chiaaaant à coder, et je trouve pas la motivation pr ça), un système de combat (mais jdois d'abord faire les menus, heh!), et puis pr le reste ma foi... ça devrait être ok. Je m'étais donné 1 an pour le moteur complet, il me reste juillet, aout et les 20 premiers jours de septembre... seulement moi je serai tt le tps oqp alors jpense que ça ira pas ^^ enfin, cqui est sûr, c que je le terminerai.

pr le multi joueur, je pense pas que moi je me lancerai dedans (où à la limite pr faire un salon de chat héroique-fantastique ^^ ça pourrait être marrant), par contre un ami m'a proposé de poursuivre le projet de son côté mais dans une autre direction: un jeu d'infilration moderne. Et en effet, le code devrait être adaptable, c'est tout en POO et commenté ;-)

tu as aussi des gros projets comme ça, dans lesquels tu te lances pour longtemps en sachant que ça mettra du temps? c'est sympa à faire mais... le problème majeur c'est qd même la motivation qui baisse vite et qui met du temps à revenir! c'est sinusoïdal...

Commentaire de neo_00110010101 le 12/06/2004 11:56:56

pas encore au niveau de la programmation mais il ne faut jamais dire jamais ...
En modelisation 3D, je me fixais comme objectif de faire tel ou tel modèle (avec concept ...) et je passais mes journées (voire des semaines) dessus en train de générer les images et peaufiner les textures.
Il fallait ~30 minutes pour créer l'image de mon musée parce qu'il fallait calculer l'éclairage qui était le plus compliqué de tout mon "oeuvre" mais j'en suis revenu à la programmation après une quarantaine de modèles sur different programmes professionnels ou non ... c'est sûr que j'ai énormement appris.
Comme tu l'as si bien dit, le problème c'est la motivation (tiens ça me rappelle le lycée ça ...) et le temps aussi car il passe vite ou on n'en a pas assez ...

Commentaire de Kirua le 12/06/2004 12:11:36

bah j'ai trouvé la solution pour le temps, la même que la plupart des programmeurs d'ailleurs: faut juste se décaler de 6h par rapport au schéma des gens: tu te couches entre 3 et 4h, et tu te lèves vers 11h. Tu dors pas plus que les autres, mais à partir de 1h y a plus personne qui t'em**** sur ton pager et tu te retrouves entre programmeurs ^^

tu as un site de présentation pour tes modèles? ça m'amuserait de voir ça :)

Commentaire de neo_00110010101 le 12/06/2004 14:16:34

merci pour la "soluce" ^^
>> www.angelfire.com/ms3/neo_00110010101
mes préférés :

MILKSHAPE 3D ("petit" programme sympa)
http://www.angelfire.com/ms3/neo_00110010101/weapons/g3sg1.html
http://www.angelfire.com/ms3/neo_00110010101/weapons/mp5.html
http://www.angelfire.com/ms3/neo_00110010101/others/boitier.html
http://www.angelfire.com/ms3/neo_00110010101/weapons/sw.html

3D STUDIO MAX 6 (le programme par exellence ^^)
http://www.angelfire.com/ms3/neo_00110010101/3dsmax/mp5k.html (regarde les liens-images en bas de page)
http://www.angelfire.com/ms3/neo_00110010101/3dsmax/usword.html
http://www.angelfire.com/ms3/neo_00110010101/3dsmax/gizmo.html
http://www.angelfire.com/ms3/neo_00110010101/3dsmax/usword2.html
http://www.angelfire.com/ms3/neo_00110010101/3dsmax/museum.html

et voilà ai le temps de tout regarder ! @+

Commentaire de Kirua le 14/06/2004 12:38:55

ouach, y a des choses vrmnt bien, et ton musée est incroyable (y a même les glaneuses :p). c'est assez impressionnant pour moi qui ai du mal avec paint shop pro :p

Commentaire de mehdibou le 14/06/2004 17:53:44

Je vois que t'as mordu à l'ameçon de l'algorithmique :)
Si tu veux, le site www.prologin.org te permettra de découvrir des algo intéressants et t'entrainer.

En ce qui concerne ton algo, j'aurai plutôt privilégié un parcours en largeur pour trouver ainsi la solution la plus rapide (voire la plus simple en utilisant par exemple addition et multiplication avant division).
En ce qui concerne ton TODO (recherche de la solution la plus proche), je pense que maintenant une variable "solution la plus proche" ne devrait pas poser de problème.

Remarque à part : quel est le compilo qui génère un exe si lourd ? (216 Ko c'est énorme!)

Je mets quand même 9/10 :)

Commentaire de Kirua le 14/06/2004 18:04:54

c'est GCC, et si je mets pas la commande -s dans les options de compil', il m'en sort un à 400Ko. C'est la STD qui prend autant de place. Il suffit que je fasse un programme sans STD et c'est plus raisonnable. C'est dépitant la taille de ces exe :(

maintenant une variable de la plus proche demanderait en fait de parcourir chaque étape intermédiaire à la recherche d'un meilleur nombre. ou bien faudrait modifier la méthode de recherche du nombre cible (Objectif) pour qu'elle précise également si la solution est meilleure que les précédentes. Dans ts les cas, c'est pas compliqué.

La recherche en largeur ça aurait pris bcp trop de place en mémoire, c'est pas jouable :/

Commentaire de mehdibou le 14/06/2004 18:22:06

Si mes calculs sont bons, ça ne fait que 2645395200 possibilités au maximum :D
En dynamisant le tout, on peut réduire à 64 * valeur maxi (32767) = 2097088
Evidemment, 16 Mo de mémoire pour si peu, ça fait beaucoup :\

Commentaire de Kirua le 14/06/2004 18:29:26

un Etat occupe 44 octets, pas 1 :-/

Commentaire de mehdibou le 14/06/2004 18:40:26

j'avais compté 8, je ne sais plus pourquoi...
bon, en plus ce sont des unsigned short donc pas 32767 mais 65535, on a donc ... 64 * 65535 * 20 (on peut réduire Etat à 20 octets en faisant des champs de bits pour les opérations déjà effectuées) = 80 Mo :D
Je pourrai le lancer mais c'est tout lol

Commentaire de Kirua le 14/06/2004 18:44:36

surtout que ça risque d'exploser le tas :/ je pense pas que le fait d'avoir même 256 Mo de RAM t'autorise à allouer 80Mo à ton programme. En tout cas avec les vector (STL), quand j'alloue trop de mémoire, il m'envoie paître (et ferme le programme sans msg d'erreur, ce qui est pénible à débugger!)

Commentaire de neo_00110010101 le 14/06/2004 19:50:56

merci pour tes commentaires (voir plus haut, très très haut ^^)

sinon tu as fait un super programme comme je l'ai tjs dit :) qui mérite sa place à coté de celui de MICKAELIAZERTY.

Commentaire de Kirua le 14/06/2004 19:56:31

j'ai codé un particle engine ajd, comme ça je fais un peu dans tout ^^. mais mon moteur a un plus que j'ai encore jamais vu ailleurs, donc même si ça existe déjà, ben c'est comme si j'avais innové :p je vous montrerai ça quand j'aurai terminé et débuggé.

Commentaire de neo_00110010101 le 14/06/2004 20:41:40

vivement que tu nous sortes ça alors :]
j'attendrai sagement lol

Commentaire de Kirua le 14/06/2004 21:27:37

j'ai quasiment fini ;-)
me faudra aussi pas mal de temps pr expliquer ce qu'elle a de plus :p

Commentaire de victorcoasne le 02/09/2004 13:17:55

Super nickel 10/10 !!!

Commentaire de Kirua le 15/05/2005 21:23:23

"Commentaire de : mehdibou le 14/06/2004 17:53:44
Je vois que t'as mordu à l'ameçon de l'algorithmique :)
Si tu veux, le site www.prologin.org te permettra de découvrir des algo intéressants et t'entrainer."

J'imagine que c'est grâce à toi que je suis allé roder sur prologin.org. Me suis classé à la finale de cette année, alors: MERCI! C'était génial :) Et je vous encourage tous à y aller.

Commentaire de mehdibou le 15/05/2005 23:29:14

<mode:arf,chui arrivé _que_ 12ième>
Hoho.. faut arrêter d'encourager tout le monde à aller à Prologin, après ils font mieux que vous ;)
</mode>
En tout cas je suis content de t'avoir pu te faire découvrir cette aventure (ce périple ?)...
L'année va paraître longue jusqu'à avril prochain :)

En attendant, pensez à vous entrainer.
Et à l'année prochaine (ou pas.)

Commentaire de Kirua le 23/04/2006 02:23:09

AVRIL PROCHAIN !!

:D

Trop content, vendredi prochain -> prologiiiiiiiiin :)

PS: je PEUX flooder, c'est MON code :p

Commentaire de mehdibou le 23/04/2006 20:50:09

Yes, a bientot !

ps: j'y suis deja en fait..

Commentaire de Kirua le 24/04/2006 12:38:36

comment ça déjà? t'es à l'epita? tu peux pas participer alors?
je pars vendredi soir, j'arriverai vers 22h :)

Commentaire de mehdibou le 24/04/2006 22:38:05

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..

Commentaire de Kirua le 24/04/2006 23:38:43

? Ils ont une formation avant prologin ?

je trouve ça carrément vexant -_-