Idée de lecture des cases de la matrice

Version imprimable

25/04/2016, 09h42
mido1951

Idée de lecture des cases de la matrice

Bonjour,
j'ai remplis une matrice avec des entiers. je vais vous donnez une exemple simplifié.
voici ma matrice.
0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0
0 0 0 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 7 7 7 0 0 0 0 0 0 0 7 7 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 7 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 7 7 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 8 8 8 0 0 0 0 0 0 0 0 0 0 0 0 0 8 8 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 8 8 0 0
0 0 0 0 0 0 0 0 0 0 9 9 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Comme vous voyez ici. je vais effectuer une recherche dans cette matrice en diagonale mais je dois detecter la zone où il y a des 111 puis 222 puis 333 puis 444... qui se suivent.bien sur on peut trouver des cas comme le 8888.
Je dois avancer sur la ligne et je regardre la ligne suivante. et Bien sur je dois detecter juste le zone où il y a une suite maximum de 111 puis 222 puis 333 ....
J'espère que vous m'avez compris.
Merci pour votre aide.
25/04/2016, 10h08
picodev
Bonjour,
trouver des diagonales n'est pas compliqué en soi, il ne s'agit que de déplacements avec vérifications … mais as-tu des cas limites comme :
Code:

1 2 3 4 0 0 0 1 1 1 1 1 1 0 0 0 … 0 0 0 2 2 2 2 2 2 0 0 0 … 0 0 0 0 0 0 0 0 0 3 3 3 …
?

Dois-tu trouver les diagonales non complètes ? qui ne commence pas par 1 par exemple ou qui s'arrête à 4 ?
25/04/2016, 10h09
Matt_Houston

Non, je n'ai pas saisi. Quel devrait être le résultat de la recherche sur l'entrée ci-dessus ? Peux-tu donner d'autres cas d'utilisation ou une explication plus complète ?

Citation:

Envoyé par picodev

Bonjour,
trouver des diagonales n'est pas compliqué en soi, il ne s'agit que de déplacements avec vérifications … mais as-tu des cas limites comme :

Code:

1
2
3
4
 
0 0 0 1 1 1 1 1 1 0 0 0 …
0 0 0 2 2 2 2 2 2 0 0 0 …
0 0 0 0 0 0 0 0 0 3 3 3 …

?

Dois-tu trouver les diagonales non complètes ? qui ne commence pas par 1 par exemple ou qui s'arrête à 4 ?

le cas

Code:

1
2
3
4
 
0 0 0 1 1 1 1 1 1 0 0 0 …
0 0 0 2 2 2 2 2 2 0 0 0 …
0 0 0 0 0 0 0 0 0 3 3 3 …

est possible.
oui on peut trouver des cas qui ne commence pas par 1. je dois voir generalement les zones ou il y a une forte concentration.
on peut meme trouver des cas comme ça:

Code:

1
2
3
4
5
6
7
8
9
0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0
0 0 0 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 6 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 7 7 7 0 0 0 0 0 0 0 7 7 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 7 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 7 7 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 8 8 8 0 0 0 0 0 0 0 0 0 0 0 0 0 8 8 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 8 8 0 0
0 0 0 0 0 0 0 0 0 0 9 9 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

il n'y a pas de 333 apres le deux 222 absence d'une sous chaine. mais on peut tolérer ça pour une absence d'un motif.
Merci

25/04/2016, 10h28
mido1951

Citation:

Envoyé par Matt_Houston

Non, je n'ai pas saisi. Quel devrait être le résultat de la recherche sur l'entrée ci-dessus ? Peux-tu donner d'autres cas d'utilisation ou une explication plus complète ?

Je cherche des sous chaines de taille k (qui sont decoupé d'une sequence) dans une autre sequence plus longue (de taille les colonnes de la matrice). les lignes sont les sous chaines. lorsaue je trouve la sous chaine dans la sequence je mets des 1 (pour la première sous chaine et le 1 1 1 est la taille de la sous chaine.)
puis la deuxième sous chaine si je la trouve je mets 2.
comme t'as vu il y a 8888 ici j'ai trouvé la meme sous chaine. (se sont deux 888 et 888 par exemple TTT a la position 42-->44 et TTT a la position 43-->45).
voila et apres je cherche sur la matrice la zone où il y a une forte concentration de 111 puis 222 puis 333...
dans ce cas je trouve la position de la petite sequence dans la longue.(la position de commencement et la position de la fin +ou-).
voila
25/04/2016, 10h49
picodev
Peux-tu avoir des cas comme
Code:

1 2 3 0 0 0 1 1 1 0 … 0 0 0 0 2 2 2 …
?
Que fais-tu avec ?
25/04/2016, 10h56
mido1951

non! on ne peut pas avoir des cas comme ça. comme j'ai expliqué a Matt_Houston les sous chaines obtenu à partir d'une sequence de taille k sont non chevauchants.
25/04/2016, 11h09
picodev

Dans un autre de tes nombreux fils je t'ai écrit :

Citation:

Envoyé par picodev

Bonjour,
vu les fils que tu as ouvert je me pose la question si tu sais réellement ce que tu veux faire. Ce que tu demandes est simplement un tableau unidimensionnel.

Je pense qu'il serait plus simple de décrire ton besoin, non en terme de structure de données en C mais en simple français pour permettre de t'orienter vers la solution la plus adéquate. Je dis cela car le besoin de sdd que tu exprimes est généralement le symptôme d'une mauvaise conception, pour autant qu'il y en ait une.

Ici le problème que tu décris est de trouver la plus grande sous chaîne commune à deux chaînes. Ton approche va fonctionner mais n'est pas la meilleure. Regarde si tu ne peux pas utiliser les algo classiques (donc sans réinventer une roue carrée) → longest common substring.
25/04/2016, 11h15
mido1951

Citation:

Envoyé par picodev

Dans un autre de tes nombreux fils je t'ai écrit :

Ici le problème que tu décris est de trouver la plus grande sous chaîne commune à deux chaînes. Ton approche va fonctionner mais n'est pas la meilleure. Regarde si tu ne peux pas utiliser les algo classiques (donc sans réinventer une roue carrée) → longest common substring.

Je n'ai pas mis de nombreuses fils mais chaque fil pose une problème de cette façon si quelqu'un a le meme probleme que moi il touve la solution sans passer par un long nombre de message. c'est pour cette raison que j'ai mis ça. si c'est interdit je peux les effacés si vous voulez.
revenant au problème, oui je sais qu'il y a SCS mais moi je veux utiliser cette solution puis peut etre je chercherai a une optimisation mais j'ai besoin que cette idée marche.
merci pour votre aide
25/04/2016, 11h26
picodev
Ne le prends pas mal, je te dis simplement qu'il est plus facile de faire de gros changements le plus tôt possible, surtout concernant les sdd … la refactorisation dans un projet abouti est très complexe.

Les plus gros problèmes (mis à part le manque de recul) avec ton approche va être le cas :
Code:

1 2 3 1 1 1 1 0 0 0 2 2 2 2 0 0 0
Quand doit-on descendre ?

et le cas
Code:

1 2 3 4 5 6 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5
Il manque un 222 pour 111222333 ou un 444 pour un 333444555 ?
25/04/2016, 11h44
mido1951

oui c'est ça, j'ai bcp refléchis et je veux partager mon problème pour une reflexion en groupe c'est toujours mieux.
en faite on doit toujours descendre et vérifier jusqu'a trouver une suite la plus longue possible. c'est à dire trouver le maximum de sous chaines dans le bonne ordre (c'est pour ça les 1 et 2 et 3 pour garder l'ordre).
par exepmle: si on a 111rien333rienrien666rien8888. ces sous chaine nes couvre pas une bonne zone de la sequence longue donc on elimine.
si on a 111rien333444555666rien8888999. pour un manque de deux sous chaine c'est pas grave de cette façon on peut considérer que la petite sequence (de sous chaines) correspond a une zone de la longue sequence.
voila.
je sais c'est un peu compliqué mais je sais que ce n'est pas impossible c'est pour ça je cherche une solution algorithmique à ça .
Merci
25/04/2016, 11h53
picodev
Et dans ton exemple un 111rien333 peut être de la forme
Code:

1 2 3 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3
? en gros avec de 0 à la place de 2 qu'on veut ?
25/04/2016, 12h09
mido1951

oui on peut trouver des 111rienrien444555666777888. oui comme ça on peut l'accepter puisqu'il y a une suite qui couvre la zone.
25/04/2016, 12h19
Matt_Houston

Ok je pense avoir compris, c'est grosso modo de l'analyse lexicale. En utilisant un automate ça devrait bien se goupiller.
25/04/2016, 12h23
picodev

Citation:

Envoyé par mido1951

oui on peut trouver des 111rienrien444555666777888. oui comme ça on peut l'accepter puisqu'il y a une suite qui couvre la zone.

ça fait quelle taille un seul rien ? 3 ?
pourtant les «non 0» peuvent être plus long que 3, non ?

Peut-être pourrais-tu t'inspirer de documents comme Heurisitique sur les alignement se séquences qui sont adaptés à ce que tu décris.
25/04/2016, 13h15
mido1951

Citation:

Envoyé par Matt_Houston

Ok je pense avoir compris, c'est grosso modo de l'analyse lexicale. En utilisant un automate ça devrait bien se goupiller.

ça veut dire quoi? je n'ai pas compris votre réponse.
Merci

Citation:

Envoyé par picodev

ça fait quelle taille un seul rien ? 3 ?
pourtant les «non 0» peuvent être plus long que 3, non ?

Peut-être pourrais-tu t'inspirer de documents comme Heurisitique sur les alignement se séquences qui sont adaptés à ce que tu décris.

le rien peut etre de taille 3 oui. ou sinon on cherche dans la ligne suivante (s'il y a 111 on cherche le 333 mais trés loin de 111 "en colonne"). si on a 111 dans les colonnes 1 2 3 on cherche 333 dans les colonnes 7 8 9 par exemple.
merci pour le lien mais je cherche une solution a ce problème.
est-ce vous avez une petite approche? ou tu penses quoi?
25/04/2016, 14h14
picodev

1 pièce(s) jointe(s)

Citation:

Envoyé par mido1951

le rien peut etre de taille 3 oui. ou sinon on cherche dans la ligne suivante (s'il y a 111 on cherche le 333 mais trés loin de 111 "en colonne"). si on a 111 dans les colonnes 1 2 3 on cherche 333 dans les colonnes 7 8 9 par exemple.
merci pour le lien mais je cherche une solution a ce problème.
est-ce vous avez une petite approche? ou tu penses quoi?

Une autre approche … oui évidemment, petite je ne sais pas :) as-tu parcouru le document lié ?

Tu n'arrives pas à exprimer tes besoins clairement, comment aligner quoi avec quoi à quelle conditions, quels seuils, etc …
Apparemment cela a déjà été fait et une autre approche est présentée dans ce document, tu pourrais t'en inspirer car ce que tu cherches à faire correspondrait, pour ce que j'en ai compris, à l'algorithme FASTA :
Pièce jointe 207855

Mener ce genre de projet en ayant des difficultés en C est voué à produire du code spaghetti trop complexe pour pouvoir s'y retrouver. Ce genre de code tâtonnant qui va s'avérer lent et décevant par rapport à ce que d'autres algo ou sdd peuvent produire.
Avec l'aide d'algorithmes déjà existant, que l'on comprend puis que l'on implémente on arrive à mener de front et l'aboutissement du projet et l'apprentissage avancé de C.

Il n'y a aucune honte à utiliser des algo performants qu'on a pas pondus, tant qu'on arrive à les comprendre. Il vaut mieux un bon mergesort qu'un mauvais tri à bulle …

nouvelle idée

j'ai abondonné cette idée. ça marche pas et coute bcp de calcul. Je veux bien effacé la dicussion et rester sur ce messsage mais j'ai pas pu.
Pour ne pas ouvrir une nouvelle discussion je continue ici. J'ai une autre idée qui coute moins de calcul et d'espace mémoire et la meme chose je veux la partager pour avoir vos avis.
voila il faut regarder l'idée point de vue programmation et comment parcourir une matrice.
voici ma matrice:
Code:

1 2 3 4 5 6 7 8 6 14 17 20 23 26 29 32 28 30 41 41 7 3 -1 -1 11 59 -1 -1 -1 -1 36 69 35 37 42 42 25 50 -1 -1 19 64 -1 -1 -1 -1 66 -1 -1 38 43 43 47 72 -1 -1 62 -1 -1 -1 -1 -1 -1 -1 -1 -1 67 44 44 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 45 45 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
mon idee est de chercher le chemin en Gras.
la recherche est suivant la colonne suivante dans la matrice si M[i][j]=M[i][j+1]+k (dans ce cas k=3). Mais bien sur il faut vérifier toutes les valeurs de la colonne et prendre la première case qui vérifie l'equation. et se stope lorsqu'il trouve -1 comme la dernière colonne il ne va pas la prendre en compte.
j'ai fait un petit programme su ça mais ça marche pas.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 while(l<=nbcolonne) //jusqu'aux nbre colonne de la matrice { while(verif==0) { while((M[t][c+1] != -1) && (verif ==0)) //pour verifier s'il trouve -1 il stoppe ou il trouve alors il stoppe { if(M[t][c+1]==M[m][l]+k) //ici c'est pour voir la colonne suivante ici k=3 dans l'exemple. { m=t; l=c+1; t=-1; c=c+1; verif=1; } t=t+1; } if(verif==0){m=m+1;t=0;} //ici s'il ne trouve pas la première case par exemple M[0][0] alors il saut à M[1][0] } }
il verifie avec 6 --> M[0][0] avec les case de M[i][j+1] puis il saute à M[1][0] il trouve que M[1][0]=M[0][1]+k mais il ne veut pas continuer. :(
merci pour aide

27/04/2016, 09h25
picodev
La réponse est simple → file et backtracking, enfin tout dépend de ce que tu veux vraiment …

Questions :
- Un chemin doit-il toujours être commencer dans la première colonne ? peut-il commencer ailleurs ?
- Les colonnes semblent triées, du plus petit en haut au plus grand en bas, mis à part les -1. Est-ce le cas ?
- Tu veux un chemin ou tous les chemins ?
- Ta structure de donnée est-elle déjà fixée ou peux-tu la modifier ?

Citation:

Envoyé par picodev

La réponse est simple → file et backtracking, enfin tout dépend de ce que tu veux vraiment …

Questions :

Un chemin doit-il toujours être commencer dans la première colonne ? peut-il commencer ailleurs ?
Les colonnes semblent triées, du plus petit en haut au plus grand en bas, mis à part les -1. Est-ce le cas ?
Tu veux un chemin ou tous les chemins ?
Ta structure de donnée est-elle déjà fixée ou peux-tu la modifier ?

je n'ai pas compris "file et backtracking, enfin tout dépend de ce que tu veux vraiment …"
pour tes questions:
1- Non un chemin peu ne pas commencer par la première colonne comme vous avez vu les nombres de la première colonne peuvent ne pas vérifier la condition donc on saute à la deuxième et bien sur on ne saute pas à chaque fois. Par exemple on a 14 colonne je vais prendre ~90% des colonnes c'est dire il saute ~2colonnes mais pas 3 colonnes ou plus. (c'est une autre complexité de mon idée que je l'introduirerai)
2- Oui, elle sont triées. J'ai mis -1 pour qu'il stoppe et ne pas parcourir le reste de la colonne.
3- Je veux les chemins qui vérifie la condition à chaque fois et il couvre ( ou il passe) au moins par 90% des colonnes de la matrice. Si on trouve un chemin qui vérifie la condition à chaque fois de la colonne 1 à 6 donc je dois rejeté ce chamin puisqu'il ne couvre pas 90% des colonnes de la Matrice.
4- Je n'ai pas compris ici. je construis une matrice puis j'analyse cette matrice et je cherche en fonction de ma condition. Je trouve que les colonnes sont moins de l'autre idée.
Merci pour votre aide

j'ai un peu modifier le programme.
voici une novelle version avec moins de variable.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 while(verif==0) { while(M[t][c+1] != -1) //pour verifier s'il trouve -1 il stoppe ou il trouve alors il stoppe { if(M[t][c+1]==M[m][l]+k) //ici c'est pour voir la colonne suivante ici k=3 dans l'exemple. { m=t; l=c+1; t=-1; c=c+1; verif=1; } t=t+1; } if(verif==0){m=m+1;t=0;} //ici s'il ne trouve pas la première case par exemple M[0][0] alors il saut à M[1][0] }

27/04/2016, 10h05
picodev

Citation:

Envoyé par mido1951

je n'ai pas compris "file et backtracking, enfin tout dépend de ce que tu veux vraiment …"

une file pour garder les chemins, backtracking : une méthode pour parcourir ta matrice et trouver les chemins. C'est une idée de premier jet ne connaissant pas les détails de ce que tu cherches à obtenir.

Citation:

Envoyé par mido1951

pour tes questions:
1- Non un chemin peu ne pas commencer par la première colonne comme vous avez vu les nombres de la première colonne peuvent ne pas vérifier la condition donc on saute à la deuxième et bien sur on ne saute pas à chaque fois. Par exemple on a 14 colonne je vais prendre ~90% des colonnes c'est dire il saute ~2colonnes mais pas 3 colonnes ou plus. (c'est une autre complexité de mon idée que je l'introduirerai)

Tu entends par là qu'un chemin possède bien un élément par colonnes consécutives, donc sans trou = un chemin avec un élément en colonne i doit forcément avoir un élément dans la colonne i+1 si il y a un élément de la colonne i+2. Ou peut-on avoir un trou ?

Citation:

Envoyé par mido1951

2- Oui, elle sont triées. J'ai mis -1 pour qu'il stoppe et ne pas parcourir le reste de la colonne.

ça simplifie les choses :)

Citation:

Envoyé par mido1951

3- Je veux les chemins qui vérifie la condition à chaque fois et il couvre ( ou il passe) au moins par 90% des colonnes de la matrice. Si on trouve un chemin qui vérifie la condition à chaque fois de la colonne 1 à 6 donc je dois rejeté ce chamin puisqu'il ne couvre pas 90% des colonnes de la Matrice.

Là j'ai peur de comprendre qu'il faille accepter les chemins avec des trous

Citation:

Envoyé par mido1951

4- Je n'ai pas compris ici. je construis une matrice puis j'analyse cette matrice et je cherche en fonction de ma condition. Je trouve que les colonnes sont moins de l'autre idée.

Merci pour votre aide

Ça peut simplifier les choses si ta matrice est une matrice de structures plutôt que d'int.
27/04/2016, 10h14
mido1951

Citation:

Envoyé par picodev

une file pour garder les chemins, backtracking : une méthode pour parcourir ta matrice et trouver les chemins. C'est une idée de premier jet ne connaissant pas les détails de ce que tu cherches à obtenir.

Tu entends par là qu'un chemin possède bien un élément par colonnes consécutives, donc sans trou = un chemin avec un élément en colonne i doit forcément avoir un élément dans la colonne i+1 si il y a un élément de la colonne i+2. Ou peut-on avoir un trou ?

ça simplifie les choses :)

Là j'ai peur de comprendre qu'il faille accepter les chemins avec des trous

Ça peut simplifier les choses si ta matrice est une matrice de structures plutôt que d'int.

Oui on peut avoir un trou ou deux. Je vais introduire l'idée des trou (Obligé).
Mais ici j'ai un petit problème parce que je dois vérifier les autres colonnes si je ne trouve pas la condition vérifié dans la première ou deuxième ou Neme colonne.
t'as vu mon dernier code? il a marché avec des données simple mais je dois introduire les autres complexités!!
pour la matrice de structure?!! je n'ai aps compris comment c'est simple? se sont des nombres.
Merci.

Bon l'idée de départ va être de définir un peu tes besoins, tous tes besoins, car produire quelque chose pour revenir en arrière et tout changer n'est pas productif du tout.

Il te faut quelque chose qui ressemble à :

Code:

1
2
3
4
5
6
7
8
void find_path(matrix_t m, visit_func_t visit)
{
  path_max_holes = m.width * 0.1;
  path_min_length = m.width - path_max_holes;
  first_col=0;
  path_list=path_list_new();
  backtrace_path(m, first_col, path_list, path_max_holes, path_min_length, visit);
}

avec

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void backtrace( matrix_t m, int col, path_list_t path_list, int max_holes, int min_length, visit_func_t visit)
{
  if min_length>m.width-col return car il n'y a plus assez de colonnes
  if length(path_list)>=min_length visit(m, path_list);
 
  for(row=0; row<m.height && m[row][col]!=-1; ++row)
    if is_empty(path_list)
      push( (row,col) , path_list )
      backtrace(m, col+1, path_list, max_holes,min_length, visit)
      pop(path_ist)
    else if m[row][col].val=head(path_list)+3
      push( (row,col) , path_list )
      backtrace(m, col+1, path_list, max_holes,min_length, visit)
      pop(path_ist)
    else if max_holes!=0
      backtrace(m, col+1, path_list, max_holes-1,min_length, visit)
}

Enfin bon, c'est tapé à la volée, une idée à creuser

Citation:
Envoyé par picodev
Bon l'idée de départ va être de définir un peu tes besoins, tous tes besoins, car produire quelque chose pour revenir en arrière et tout changer n'est pas productif du tout.

Il te faut quelque chose qui ressemble à :
Code:

1 2 3 4 5 6 7 8 void find_path(matrix_t m, visit_func_t visit) { path_max_holes = m.width * 0.1; path_min_length = m.width - path_max_holes; first_col=0; path_list=path_list_new(); backtrace_path(m, first_col, path_list, path_max_holes, path_min_length, visit); }
avec
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 void backtrace( matrix_t m, int col, path_list_t path_list, int max_holes, int min_length, visit_func_t visit) { if min_length>m.width-col return car il n'y a plus assez de colonnes if length(path_list)>=min_length visit(m, path_list); for(row=0; row<m.height && m[row][col]!=-1; ++row) if is_empty(path_list) push( (row,col) , path_list ) backtrace(m, col+1, path_list, max_holes,min_length, visit) pop(path_ist) else if m[row][col].val=head(path_list)+3 push( (row,col) , path_list ) backtrace(m, col+1, path_list, max_holes,min_length, visit) pop(path_ist) else if max_holes!=0 backtrace(m, col+1, path_list, max_holes-1,min_length, visit) }
Enfin bon, c'est tapé à la volée, une idée à creuser
merci pour le code. je vais essayer un peu de le dechiffrer parceque c'est un peu complexe à comprendre. Merci bcp.
j'ai une petite question: J'ai une machine un peu ancienne 32bit. j'utilise un découpage des sequence de taille k=3. Mais le problème quand j'augmente la taille k( k= 4 par exemple) ça marche pas. le programme se bloque. est-ce normal?
Merci

27/04/2016, 12h40
picodev

Citation:

Envoyé par mido1951

merci pour le code. je vais essayer un peu de le dechiffrer parceque c'est un peu complexe à comprendre. Merci bcp.
j'ai une petite question: J'ai une machine un peu ancienne 32bit. j'utilise un découpage des sequence de taille k=3. Mais le problème quand j'augmente la taille k( k= 4 par exemple) ça marche pas. le programme se bloque. est-ce normal?
Merci

Si le programme se bloque alors qu'il ne devrait pas alors c'est un bug …
27/04/2016, 13h56
ternel

D'un autre coté, tu parles d'un bug quand tu passes de 3 à 4, et il y a un gros 3 dans le code.
Pour moi, le problème, c'est d'avoir un nombre magique dans le code.

Fuseau horaire GMT +2. Il est actuellement 20h02.