LE QUE LES CHIFFRES DANS LES CHIFFRES ET LES LETTRES

Signaler
Messages postés
360
Date d'inscription
samedi 27 septembre 2003
Statut
Membre
Dernière intervention
30 mai 2006
-
reto25
Messages postés
1
Date d'inscription
samedi 7 juin 2008
Statut
Membre
Dernière intervention
2 janvier 2010
-
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

reto25
Messages postés
1
Date d'inscription
samedi 7 juin 2008
Statut
Membre
Dernière intervention
2 janvier 2010

Bonjour,
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 ?
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

http://www.cppfrance.com/code.aspx?ID=23621
ma version de l'algo, dispo ici ;-) (trouvais dommage que personne le vois (*tête d'ange*))
BruNews
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
17
Tu devrais trouver la partie Lettres soit dans mes sources, soit dans celles de aardman avec qui j'avais deja fait cette partie Lettres.
mickaeliazerty
Messages postés
10
Date d'inscription
samedi 5 juin 2004
Statut
Membre
Dernière intervention
27 juillet 2004

BruNews, assez sympa ton interface graphique...
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...
StanOfSky
Messages postés
43
Date d'inscription
mardi 30 mars 2004
Statut
Membre
Dernière intervention
7 octobre 2006

lé bien cet algo ;)
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)
BruNews
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
17
Je l'ai mis en mode graphique ici:
http://www.cppfrance.com/code.aspx?ID=23487
en respectant les specs du jeu.
BruNews
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
17
Je viens de trouver la page du reglement du jeu TV
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.
cs_NSF94
Messages postés
3
Date d'inscription
dimanche 22 février 2004
Statut
Membre
Dernière intervention
7 juin 2004

tro bien mec , bravo (y)
vecchio56
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7
Ca fait du bien de voir un algo écrit en rolog, un langage vraiment génial, et très adapté à ce type de problème

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]
BruNews
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
17
Il marche vraiment bien cet algo !!!
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.
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

yahouuu, i'm looking forward to it ^^ (examen d'anglais demain, ce qui explique que je sois devant mon PC depuis ce matin ^^)
BruNews
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
17
Kirua, le serveur sature a fond en ce moment.
Encore un peu de patience et vous aurez une belle surprise (chut).
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

c'est bizarre comme langage ton PROLOG :p enfin, bizarre vu par les yeux de qq un qui a tjs fait de la POO...

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 :/)
BruNews
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
17
Merci Kirua, je suis dans le meme cas au sujet de la tele.
StanOfSky
Messages postés
43
Date d'inscription
mardi 30 mars 2004
Statut
Membre
Dernière intervention
7 octobre 2006

j'ai fait une version PROLOG pour ceux que ca interesse

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]).
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

BruNews, pr le jeu télévisé, ts les nombres sont des entiers positifs non nuls inférieurs à 1000 (sauf erreur ^^ je regarde jamais la télé).

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
StanOfSky
Messages postés
43
Date d'inscription
mardi 30 mars 2004
Statut
Membre
Dernière intervention
7 octobre 2006

hihihi encore ce jeu ;)
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)
BruNews
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
17
qui saurait me dire quelle est la plage de valeurs pour les 6 nombres source et celle de la cible, par exemple dans le jeu TV ?
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

et voilà, j'ai codé le mien en 1h30 avec la technique de la profondeur d'abord, et ça fait 30 min que je dois dodo.

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 ...
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

c logique que ça marche pas, les enteirs signés sont codés sur 32 bits, donc 31 bits de positif, ça fait " seulement " 2 milliards au max, et du coup ton 99 milliards est tronqué

utilise un unsigned long int, ça te fait 2^64 de max, et avec ça tu devrais plus être frustré ;-)
neo_00110010101
Messages postés
360
Date d'inscription
samedi 27 septembre 2003
Statut
Membre
Dernière intervention
30 mai 2006

et pour résumer mes deux précedents commentaires, c'est excellent !
encore bravo mickaeliazerty !!! ça va en inspirer plus d'un ! c'est vraiment original
neo_00110010101
Messages postés
360
Date d'inscription
samedi 27 septembre 2003
Statut
Membre
Dernière intervention
30 mai 2006

Pas si infaillible que ça ^^
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 !
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

bon, pr résumer ce document, il n'ajoute rien de plus qu'une limite de profondeur pr éviter les boucles infinies.

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.
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

la vache, 10e58 c bcp bcp trop :-/
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 ..............
mickaeliazerty
Messages postés
10
Date d'inscription
samedi 5 juin 2004
Statut
Membre
Dernière intervention
27 juillet 2004

Si on prend les noms du cours et qu'on applique les formules de complexité:
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
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

je viens de relire les documents "recherche en profondeur d'abord" et "recherche en largeur d'abord" (http://glinfrench.apinc.org/IMG/pdf/largeur_dabord.pdf)

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) ?
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

http://glinfrench.apinc.org/rubrique.php3?id_rubrique=7

au temps pr moi, c'est glinfrench, pas du tout prografîx ^^
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

"améliorée", comme tu y vas, lol ^^
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.
mickaeliazerty
Messages postés
10
Date d'inscription
samedi 5 juin 2004
Statut
Membre
Dernière intervention
27 juillet 2004

En effet, il fait toutes les possibilités en récurrant et s'arrête dès qu'il a le bon résultat.
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...
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

c'est un gros jeu de récursivité en fait? je pense qu'avec une pile LIFO y doit y avoir moyen de raccourcir le code. Faudra juste trouver une façon intelligente de représenter les états en cours de travail dans une structure.
mickaeliazerty
Messages postés
10
Date d'inscription
samedi 5 juin 2004
Statut
Membre
Dernière intervention
27 juillet 2004

Bah en fait, j'ai fait la première ébauche en 1h en maths.
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.
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

raaah, c pas possible, pas une seule fois il n'a pas trouvé O_o et je tappe n'importe quoi comme nombres O_o je dois dire que pour un brute force c'est impressionnant de rapidité en plus. jdois malheureusement étudier, examen demain, mais ce soir, j'essaye d'en faire un comme toi, mais en C++ ;-) ça t'as pris combien de temps?

res: 10598
876 - 123 = 753
50 - 12 = 38
38 - 24 = 14
753 * 14 = 10542
56 + 10542 = 10598
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

magnifique :) et vrmnt rapide (sur mon PC en tt cas).
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
neo_00110010101
Messages postés
360
Date d'inscription
samedi 27 septembre 2003
Statut
Membre
Dernière intervention
30 mai 2006

cela fait deux fois que je mets n'importe quoi et ton programme me donne une super solution !
en plus il n'y a pas d'erreur mais juste un warning sur VC++ 6.0

bref c'est super bien ^^