Discussion :

[lynaranya]

bonjour;
j'ai une matrice de taille (n*m) de type binaire (0, 1)
deux vecteurs ligne sont similaire si un vecteur ligne est un sous ensemble d'un autre vecteur ligne

je veux écrire un algorithme qui permet de vérifier si deux vecteurs ligne sont similaire ou non
exemple:
exemple.doc

voici l'algorithme que j'ai creer:

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
 
pour i=1 à n faire
  pour j=i+1 à n faire
      pour k=1 à m faire
       si (V[i,k]==1) alors
            d=d+1
           si(V[j,k]==1) alors
                R=R+1
           finsi
      finsi
 
     finpour
  finpour
 
   si (d>R) alors
        v[j] est inclu dans V[i]
   sinon
        V[i] est inclu dans V[j]
   finsi
finpour

le probleme me que je rencontre dans le cas où par exemple si (V[1,4]=0, V[2,4]=1) et (V[1,4]=1, V[2,4]=0)

aussi l'utilisation de la fonction booleene


merci d'avance

[tbc92]

Je n'ai pas compris la question, mais voici déjà quelques corrections :

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
21
22
 
pour i=1 à n faire
  pour j=i+1 à n faire
      d=0  // Ajouté
      R=0  // Ajouté  
      pour k=1 à m faire
       si (V[i,k]==1) alors
            d=d+1
           si(V[j,k]==1) alors
                R=R+1
           finsi
      finsi
 
     finpour k 
 
   si (d>R) alors
        v[j] est inclu dans V[i]
   sinon
        V[i] est inclu dans V[j]
  finsi
 finpour j  // Déplacé.
finpour i

Quand tu commences le traitement d'un couple i,j), il faut remettre à 0 toutes les variables. Sinon, ce que tu calcules, ce n'est pas la comparaison de i et j , c'est la comparaison de plein de colonnes avec plein d'autres colonnes.

Et à la fin, pour afficher le bilan de la comparaison de i et j, il faut le faire au bon endroit.
Là où tu l'avais mis, il y avait un bilan pour chaque valeur de i ; n bilans seulement, alors qu'il en faut beaucoup plus.
Pour la lisibilité, j'ai mis Finpour i au lieu de Finpour.

Sur le reste, je ne suis pas d'accord non plus, mais je ne sais pas trop ce que tu veux faire, donc j'ai un vague doute.
Dans ce que tu fais, tu as forcément soit i inclus dans j, soit j inclus dans i. Et à mon avis, il y a aussi des cas où on n'a ni l'un ni l'autre.

[Guesset]

Bonjour,

Sans rentrer dans le fond du sujet la première boucle devrait s'arrêter à n-1.
Certes dans beaucoup de langages la deuxième boucle ne sera pas exécutée si l'indice de début est supérieur à l'indice de fin.
Mais dans un algorithme (ie sans hypothèse de langage) cette supposition n'a pas lieu d'être.

Salutations

[Guesset]

Bonjour,

Par ailleurs, sauf erreur de ma part, la réponse ne peut être systématiquement une inclusion. Exemple 0b11101000 et 10000111 ne sont pas inclus dans un sens ou l'autre.

En fait c'est assez simple, il suffit de créer un vecteur temporaire Vtmp := V(i) & V(j) (& pour un ET binaire bit à bit qui peut se traduire - mal - par Vtmp(k) := v(i,k) * v(j,k) ).

Code :

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

Si Vtmp == V(i) alors V(i) inclus dans V(j) sinon si Vtmp == V(j) alors V(j) inclus dans V(i) sinon pas d'inclusion

C'est certainement la solution la plus simple si les vecteurs élémentaires sont représentés par des entiers dont chaque bit est un élément du vecteur.

Sinon il est peut être plus efficace de travailler avec un flag F à 4 valeurs ; -1 pour i dans j, 0 pour i = j, 1 pour j dans i, 2 pour i et j sans relation. La boucle la plus interne devient :

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
F = 0
pour k = 1 à m faire
   si v(i,k) > v(j,k) alors
      si F == -1 alors
         F = 2
         fin de boucle // break
      sinon
         F = 1
      fin_si
   sinon si v(i,k) < v(j,k) alors
      si F == 1 alors
         F = 2
         fin de boucle // break
      sinon
         F = -1
      fin_si
   fin_si

Salutations