Discussion :

[mido1951]

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.

[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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[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 ?

[mido1951]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[mido1951]

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

[picodev]

Peux-tu avoir des cas comme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

?
Que fais-tu avec ?

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

[picodev]

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

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.

[mido1951]

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

[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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[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

[picodev]

Et dans ton exemple un 111rien333 peut être de la forme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[mido1951]

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

[Matt_Houston]

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

[picodev]

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.

[mido1951]

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

ç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?

[picodev]

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 :


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 …

[mido1951]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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 ?

[mido1951]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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]
}