LE QUE LES CHIFFRES DANS LES CHIFFRES ET LES LETTRES
neo_00110010101
Messages postés
360
Date d'inscription
samedi 27 septembre 2003
Statut
Membre
Dernière intervention
30 mai 2006
-
5 juin 2004 à 16:49
reto25 Messages postés 1 Date d'inscription samedi 7 juin 2008 Statut Membre Dernière intervention 2 janvier 2010 - 2 janv. 2010 à 16:15
reto25 Messages postés 1 Date d'inscription samedi 7 juin 2008 Statut Membre Dernière intervention 2 janvier 2010 - 2 janv. 2010 à 16:15
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/23428-le-que-les-chiffres-dans-les-chiffres-et-les-lettres
https://codes-sources.commentcamarche.net/source/23428-le-que-les-chiffres-dans-les-chiffres-et-les-lettres
2 janv. 2010 à 16:15
je vois que le code date un peu mais bon...
J'essaie de le lancer avec wxDEV-C++ mais il ne marche pas... Est-ce normal ?
14 juin 2004 à 12:42
ma version de l'algo, dispo ici ;-) (trouvais dommage que personne le vois (*tête d'ange*))
11 juin 2004 à 18:07
11 juin 2004 à 17:53
Sinon, merci pour vos commentaires, c'est motivant pour la première source que je publie.
Quand même, on a beau dire, mais LES CHIFFRES ET LES LETTRES, ca restera toujours à la mode :-)
Au fait, si quelqu'un connait un dictionnaire en mode text, qu'il me le fasse savoir, j'ai une ébauche de la partie lettres...
7 juin 2004 à 23:54
on pourrai faire un concours à savoir celui qui optimise au maximum ce genre d'algo ;) (d'un point de vue algorythmique c tres interessant et stimulant)
pour ce qui est de PROLOG, je l'avais deja fait. c pa la premiere fois que je vois ce sujet :p. donc j'ai juste ressorti celui que j'avais sorti la derniere fois.
pour ceux qui voudraient apprendre le PROLOG je donne le lien de mes cours à la fac : http://www710.univ-lyon1.fr/~nducloss/Prolog/index.html
ce qui est interessant c que PROLOG ne possede que tres peu de mots propre (a lui meme) et donc s'apprend extrement vite (bcp plus vite que le c par exemple, en une soirée normalement on sait deja faire presque tout :p) et c un langage qui permet de bien comprendre les techniques de récursivité (PROLOG ne marche qu'en récursivité) et les techniques d'IAs ;)
sympas l'interface graphique ;)
je l'aurai bien fait sous QT mais bon fau dl la librairie pour ceux qui sont sous windows (QT est portable)
7 juin 2004 à 18:56
http://www.cppfrance.com/code.aspx?ID=23487
en respectant les specs du jeu.
7 juin 2004 à 18:22
http://cybercl.free.fr/reglem/freglem.html
- deux séries de 10 plaques numérotées de 1 à 10,
- quatre plaques portant les nombres 25, 50, 75 et 100
La cible est de 1 - 999.
Voila je peux finir la version graphique.
7 juin 2004 à 18:16
7 juin 2004 à 17:46
BruNews, pour l'émission télé:
source dans {1, 2, 3, 4, 5, 6, 7, 8, 9, 19, 25, 50} et ptet 100
result dans [1, 999]
7 juin 2004 à 16:21
J'en ai fait une appli graphique qui tire les 6 nombres et la cible en aleatoire, j'ai le resultat dans un EDIT quasi illico.
Un 10/10 largement merite.
7 juin 2004 à 16:17
7 juin 2004 à 15:51
Encore un peu de patience et vous aurez une belle surprise (chut).
7 juin 2004 à 15:43
tu as codé ça mtnt ou tu l'as sorti d'un fond de dossier?
(j'essaye de poster un commentaire depuis des heures... les serveurs encaissent mal la popularité de CS :/)
7 juin 2004 à 14:12
7 juin 2004 à 14:11
ca renvoi tous les résultats possibles, j'ai essayé vite fait de supprimer les cas redondants mais c pa facile ;)
genre : 5*10=50 3*50=150 && 5*3=15 15*10=150
j'ai aussi supprimé les opérations inutiles genre x/1, x*1, x+0, x-0, x/0, x*0, x-x etc...
/* supprime l'élt E de la liste */
enleve(_,[],[]).
enleve(E,[E|L],L).
enleve(E,[X|L],[X|R]) :- X \== E, enleve(E,L,R).
/* fonction de permutation de listes */
permut([],[]).
permut(L,[M|R]) :-
member(M,L),
enleve(M,L,LmM),
permut(LmM,R).
/* supprime tous les élts avant E compris*/
reste(E,[E|L],L) :- !.
reste(E,[_|L],R) :- reste(E,L,R).
/* supprime les elts présents plusieurs fois */
elimine(E,L,L) :- not(member(E,L)),!.
elimine(E,L,R) :- enleve(E,L,LmE), elimine(E,LmE,R).
/* transforme une liste de liste en une liste d'éléments */
uneliste([],[]).
uneliste([X|L],S) :- uneliste(L,R), append(X,R,S).
/* affichage d'une liste */
aff([],[]).
aff([X|L],[A,[46]|Ecrire]) :- name(X,A), aff(L,Ecrire).
/* Affichage du résultat */
affiche([],_) :- nl.
affiche([[X,Op,Y,=,R]|L],Liste) :-
name(X,A),
name(Op,B),
name(Y,C),
name(R,D),
uneliste([A,B,C,[61],D],ListeTexte),
name(Texte,ListeTexte),
print(Texte),
affiche(L,Liste).
/*
définition de chaque opération avec A > B
+ : Addition A!=0 ou B!=0
* : multiplication A!=1 ou B!=1
- : soustraction A>B donc que des valeurs positives
/ : division avec diviseur non nul et reste de la division nul
*/
operations([A,B],+,R) :- R is A+B.
operations([A,B],*,R) :-
A =\= 1,
B =\= 1,
R is A*B.
operations([A,B],-,R) :-
A =\= B,
R is A-B,
R =\= B.
operations([A,B],/,R) :-
B =\= 1,
B =\= 0,
A mod B =:= 0,
R is A / B,
R =\= B.
/*
opérations sur listes
prend les éléments 2 par 2, effectue l'opération, supprime les
2 éléments de la liste et rajoute le résultat au début.
*/
ope(Ec,[X,Op,Y,=,R],[R|Ls2]) :-
member(A,Ec), /* prend 1 élts */
reste(A,Ec,Lt), /* enleve l'élts */
member(B,Lt), /* prend 1 autre élts */
X is max(A,B), /* X le plus gd des 2 élts */
Y is min(A,B), /* Y le plus pt des 2 élts */
operations([X,Y],Op,R), /* execute une opération */
enleve(X,Ec,Ls1), /* supprime gd élt */
enleve(Y,Ls1,Ls2). /* supprime pt élt */
/* algo de recherche de tout les résultats possible */
rechpf_op([X|_],[],[X]).
rechpf_op(Ec,[Op|Lop],Save) :-
ope(Ec,Op,Es),
rechpf_op(Es,Lop,Save).
resoudre(S) :- etatinitial(Ei), etatfinal(Ej), rechpf_op(Ei,S,Ej).
resoudre(S,Ej) :- etatinitial(Ei), rechpf_op(Ei,S,Ej).
resoudre(S,Ei,Ej) :- rechpf_op(Ei,S,[Ej]).
valeur(V) :- etatinitial(Ei), rechpf_op(Ei,_,V).
all_valeur :-
print('Recherche'), nl,
setof(V,valeur(V),L),
print('Valeurs possibles : '),
uneliste(L,ListeTexte),
print(ListeTexte).
aff_solution(_,[]).
aff_solution(Liste,[X|L]) :-
aff(Liste,Ecrire),
uneliste(Ecrire,ListeTexte),
name(Texte,ListeTexte),
print(Texte),
print('->'),
affiche(X,Liste), nl,
aff_solution(Liste,L).
solution :- setof(S,resoudre(S),L), nl, etatinitial(Liste), aff_solution(Liste,L).
solution(Ef) :- setof(S,resoudre(S,[Ef]),L), nl, etatinitial(Liste), aff_solution(Liste,L).
solution(Liste,Ef) :- setof(S,resoudre(S,Liste,[Ef]),L), nl, aff_solution(Liste,L).
/* Etatinitiaux et finaux */
etatinitial([9,75,9,75,6,5]).
etatfinal([298]).
7 juin 2004 à 14:08
la division n'est légale (pr parler franglais :p) que si elle est parfaite (reste nul: modulo = 0)
la soustraction n'est légale que si tu obtiens un nombre positif non nul
7 juin 2004 à 14:02
c vrai que c marrant a coder et que ca donne une bonne approche des techniques d'IAs...
la recherche en profondeur pour ce genre de probleme me parait beaucoup plus adaptée que celle en largeur :p
de plus la récursivité d'un point de vue purement informatique n'existe pas, c juste des réultats empilés en FIFO (first in, first out)...
pour optimiser ce genre d'algorythme il faut utiliser des coupures
je m'explique :
quand on utilise ce genre d'algorythme récursif, cela revient a créer un arbre. le but est donc d'anticiper quelle branche ne parviendra pas a un résultat quoi qu'il arrive et couper cette branche de maniere a ne pas faire de calculs inutiles.
plus l'anticipation a lieu tot plus l'algorythme sera rapide. bien sur l'algorythme d'anticipation ne doit pas etre trop lourd (ne pas faire un algo qui coninue la coupure pour verifer si ya un résultat parce que ce serai inutile:p)
par exemple vérifer a un certain stade que multiplier (ou ajouter si petits nombres) toutes les réultats ensemble est inférieur au nombre que l'on veu obtenir. ca ne sert a rien de continuer a tester tous les cas possible vu que quoi qu'il arrive on abtiendra jamais le nombre voulu...
pour ceux que l'ia interesse, faites un tour du coté de PROLOG, c un langage super (un peu comme LISP)
7 juin 2004 à 13:43
6 juin 2004 à 23:29
je posterai le code demain, après avoir pu chercher les bugs, mais j'en vois pas...
exemple de ce que j'ai obtenu:
Entrez le nombre a atteindre (objectif): 950
Nombre disponible 1: 7
Nombre disponible 2: 69
Nombre disponible 3: 54
Nombre disponible 4: 12
Nombre disponible 5: 15
Nombre disponible 6: 3
15 / 3 = 5
54 + 12 = 66
69 + 66 = 135
7 * 135 = 945
945 + 5 = 950
il est quand même significativement plus lent que ton algo ...
6 juin 2004 à 19:36
utilise un unsigned long int, ça te fait 2^64 de max, et avec ça tu devrais plus être frustré ;-)
6 juin 2004 à 19:34
encore bravo mickaeliazerty !!! ça va en inspirer plus d'un ! c'est vraiment original
6 juin 2004 à 19:30
j'ai fait 5 tests -> tous ratés (il n'aime pas les gros chiffres) :
celui là est vraiment débile, et pareil que les autres, m'a demandé une fraction de seconde de calcul (très rapide comme programme)
>> http://a6.cpimg.com/image/3A/B7/34693946-6f7b-02000102-.jpg
et pourtant là on y était presque dommage !
>> http://a8.cpimg.com/image/A4/C3/34694308-f326-02000102-.jpg
comme l'a dit Kirua, c'est vraiment bien comme brute force-like !
6 juin 2004 à 16:07
ceci dit, ça vaut la peine de le lire, car l'exemple fourni pr illustrer le problème est très convainquant, et ça permet de bien situer la brèche.
6 juin 2004 à 16:01
l'occupation spatiale de la recherche en profondeur est linéaire, donc comme toi je dirais que c jouable.
qd à trouver un "workaround" pr la boucle infinie, il y avait un article sur le même site 'recherche en profondeur limitée", mais il n'est plus accessible. heureusement que je ne nettoie mon PC que ts les ans :p j'ai encore le document, je vais le mettre sur ftp
[...]
http://nboumal.free.fr/IA_Recherche_Profondeur_Limitee.pdf
vala, sauve-le, on sait jamais que je décide de nettoyer mon espace ftp :p
je le lis mtnt, mais je devrais qd même travailler ..............
6 juin 2004 à 15:50
n 6 - 1 5 (5 calculs au max avec 6 nombres)
b = 5(=nb max op ac 2 nbres en restant ds |N) * (nbre de possibilités de prendre 2 entiers parmis 6) = 6 * 15 = 75
donc au niveau de la complexité spatiale de la recherche en largeur d'abord, ca fait du 6^75 = 2*10^58 à un facteur multiplicatif près (qu'on peut prendre aux alentours de 50 octets par situation) ce qui à mon avis est beaucoup trop pour la machine.
Par contre la recherche en profondeur d'abord semble jouable ici, si on peut casser la boucle infinie
6 juin 2004 à 15:03
et la conclusion c'est: les deux sont du même niveau à coder (c'est pas plus dur de programmer l'une que l'autre), mais:
profondeur: moins d'espace mémoire nécessaire mais risque de boucle infinie
largeur: certitude de trouver une solution s'il y en a une, mais besoin de BCP plus de mémoire
alors je sais pas trop... en général, on peut compter qu'un programme pourra occuper combien de place en mémoire avec un conteneur de type file (FIFO) ou pile (LIFO) ?
6 juin 2004 à 14:43
au temps pr moi, c'est glinfrench, pas du tout prografîx ^^
6 juin 2004 à 14:41
LIFO ça veut dire "last in, first out" (c'est-à-dire: dernier entré, premier sorti).
Le principe de la pile, c'est de mettre des données dans un conteneur de données (qui est la pile) mais en ne pouvant effectuer que ces opérations-ci:
- ajouter des données au dessus de la pile
- lire les données tout au dessus
- effacer les données tout au dessus (ce qui rend les données suivantes accessibles)
ainsi, à chaque étape de la récurrence, tu rajoutes tous les états possibles après une évolution de l'état que tu es entrain de traiter (tu suis? :p) et tu empiles ces états là. ensuite, tu rappelles la fonction (récurrence) qui va lire l'état du dessus. si cet état est une solution, c'est la fin et tu l'affiches, sinon tu empiles toutes les évolutions possibles de cet état là (avec une seule étape d'évolution, c ça l'astuce pr rendre la chose "simple"). et rebelote tu appelles la fonction récurrentes pr qu'elle refasse le teste et réempile etc... qd un état ne peut plus évoluer mais n'est pas une solution, tu le dépiles et tu rappelles la fonction, ce qu ite fait passer à l'état suivant, et au final tu auras testé toutes les possibilités.
ça s'appelle la technique de "recherche en profondeur d'abord", c'est une méthode basique d'IA que j'ai apprise sur un site français, je sais plus, je pense que c t prografix.org, mais suis pas certain.
6 juin 2004 à 14:29
Je pense que des optimisations sont possibles, en tenant compte par exemple des nombres qui sont présents plus d'une fois, mais ca complique pas mal.
Pour ce qui est de la pile LIFO, je ne connais pas, ou alors pas de nom.
Si toutefois tu comptais en refaire une version améliorée, ca serait cool que tu me la présente, histoire d'enrichir ma pauvre culture...
6 juin 2004 à 13:07
6 juin 2004 à 12:11
Après il m'a fallu une petite semaine de déboggage et d'optimisation à raison d'une bonne heure par jour, parce que j'ai codé sans trop avoir réfléchi aux détails cruciaux et aux difficultés.
Il suffit juste de bien penser à marquer ceux qui ont été pris et ceux qui ne le sont pas, et après c'est du bourrin.
Pour la vitesse, on se rend compte de sa complexité en mettant un résultat introuvable. C'est là qu'il effectue le plus de calculs et qu'il est le plus long.
6 juin 2004 à 11:05
res: 10598
876 - 123 = 753
50 - 12 = 38
38 - 24 = 14
753 * 14 = 10542
56 + 10542 = 10598
6 juin 2004 à 10:55
Jvais lire ton code, c'est du tout bon :)
res: 789
50 / 2 = 25
25 - 3 = 22
41 * 22 = 902
35 + 78 = 113
902 - 113 = 789
5 juin 2004 à 16:49
en plus il n'y a pas d'erreur mais juste un warning sur VC++ 6.0
bref c'est super bien ^^