docducon11
Messages postés dimanche 17 octobre 2004Date d'inscription
18 mai 2005
Dernière intervention
-
7 déc. 2004 à 13:22 - Dernière réponse : azakeu1
Messages postés mardi 12 décembre 2017Date d'inscription
12 décembre 2017
Dernière intervention
- 12 déc. 2017 à 10:33
Minhounet20
Messages postés mercredi 17 novembre 2004Date d'inscription
8 décembre 2004
Dernière intervention - 8 déc. 2004 à 23:26
1
Merci
Je n'ai pas d'algo en tête, mais basiquement ce que je ferai c'est prendre un mot dans la base et de vérifier s'il s'inscrit dans :
- les lignes : un exemple, par exemple le mot paon :
le P est comparé avec la première lettre, si la lettre est la même, alors je compare le A avec la 2è lettre de la ligne etc.. le mot existe dans la grille si bien sûr on arrive à renvoyer vrai à chaque test.
Ne pas oublier qu'il faut aussi tester en décalant le mot d'un cran vers la droite, à savoir le P avec la 2è lettre de la grille, le A avec la 3è lettre de la grille etc..
Ne pas oublier de faire le test en allant de droite à gauche car le mot peut être trouvé à l'envers dans la ligne.
Il faudra faire ça pour chaque ligne (ça fait beaucoup hein)
- les colonnes : idem
- les diagonales : idem
Si on se bornait à comparer lettre par lettre on mettrait beaucoup de temps vu le nombre de façon de prendre n lettres qui se suivent dans une grille.
Il faut donc penser à comparer seulement si le mot ne dépasse pas la taille de la grille, si au moins la première lettre est présente du mot est présente dans la grille.
Donc la solution, c'est de rechercher la première lettre du mot dans la grille et à partir de la position de cettre lettre, tenter de trouver le mot :
s d r a l
t p f v o
t r a i n
t r i o f
a e r n n
si je cherche le mot PAON dans la grille, je dois d'abord chercher la lettre P, elle se trouve en (1,1).
Je teste d'abord si le mot peut etre sur la ligne :
P c'est ok, F c'est pas possible.
Dans l'autre sens ensuite, P c'est OK, T pas possible.
Ensuite en colonne, P c'est okay, R non.
En colonne dans l'autre sens : P okay, D pas possible.
En diagonale, P okay, A okay, O okay, N okay.
En diagonale dans l'autre sens : ça ne marche pas
etc.. pour les autres diagonales.
Tu saisis ?
Il faut bien sûr appliquer cette façon de faire à chaque P qu'on trouve, ici il n'y en a qu'un.
Donc pour chaque mot on va faire au plus (8 * longueurdumot)*nbDePremiereLettreTrouvee. Complexité donc linéaire.
C'est donc l'idée de l'algo, le côté pratique c'est juste du parcours de matrice et des comparaisons lettre par lettre.
docducon11
Messages postés dimanche 17 octobre 2004Date d'inscription
18 mai 2005
Dernière intervention - 8 déc. 2004 à 22:46
0
Merci
Alors, je t explique:
voila un jeu de mots mélé se présente sous forme d une grille de lettres.
le but du jeux et de trouver des mots dans tout le merdier de lettres, ( dans les bouquins de jeu, il faut les entourer!!!)
mon problème est de trouver un algorithme qui propose toutes les facons de croiser un certain nombre de mots.
exemple un peu moins foireux:
s d r a l
t p f v o
t r a i n
t r i o f
a e r n n
nous avons donc : train horizontalement en 3eme ligne
avion verticalement en 4 eme colonne
et paon en diagonale
voila j esper que c mieu comme exemple.
et donc le but est de pouvoir croiser des mots que l on tire d une base de donnée.
a aidé 101 internautes ce mois-ci