[TP 7] Matrice dans matrice

Version imprimable

26/04/2007, 10h00
kedink

[TP 7] Matrice dans matrice

Bonjour à tous je débute en tp7 et j'ai un petit problème:

je dois créer un progr en pascal qui permet de voir si une matrice m2
(2X2) est présente dans une matrice m1 (5X5).

Merci d'avance pour votre aide.

Kedink.
26/04/2007, 10h16
millie

Qu'est ce que tu as déjà fait ? Quel est exactement ton problème ?

Car on est pas ici pour te faire tes exercices ;)
26/04/2007, 11h40
krachik

bonjour

Citation:

Envoyé par kedink

je dois créer un progr.....................................
Merci d'avance pour votre aide.

Genial c'est deja dit montre ce que tu as deja fait,
j'espere que t'a deja un algo pour commencer a programmer sinon :lol:
bon est ce que tu sais deja par ou commencer et ce que tu compte faire?
@+

voilà la 1ère version

En fait le problème que j'ai avec cette version , est qu'elle n'est pas très belle visuellement , et donc le programme n'est pas sympa à l'utilisation .
Je voudrais apporter qlq modification qui rendrai le programme plus cool à l'utilisation. Merci...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
program Matrice_dans_matrice ;
 
        uses crt;
        const
             a=4 ;
             b=4 ;
             d=2 ;
             e=2 ;
             f=2 ;
        type matrice=array[0..a,0..b]of Integer;
             matricePat=array[0..d,0..e]of Integer;
             matriceIncl=array[0..a*b,0..f]of integer;
        var mat:matrice;
            pattern:matricePat;
            inclusions:matriceIncl;
            i,j:integer;
 
 
procedure matrice1(Var mat:matrice);
  var m,n:integer;
begin
     for m:=1 to a do
                   for n:=1 to b do
                                 begin
                                 write('entrer un nombre entre 1 et 4 : ');
                                 readln(mat[m][n]);
                                 end;
end;
 
 
procedure matrice2(Var pattern:matricePat);
  var l,c:integer;
begin
     for l:=1 to d do
                   for c:=1 to e do
                                 begin
                                 write('entrer un nombre entre 1 et 2 : ');
                                 readln(pattern[l][c]);
                                 end;
end;
 
 
Function matrice3(mat:matrice;pattern:matricePat;inclusions:matriceIncl):integer;
  var m,n,l,c,e,f:integer;
begin
     e:=1;
     f:=1;
     l:=1;
     c:=1;
     for m:=1 to a do
                   for n:=1 to b do
                                 if(mat[m,n]=pattern[l,c])and
                                  (mat[m+1,n]=pattern[l+1,c])and
                                  (mat[m,n+1]=pattern[l,c+1])and
                                  (mat[m+1,n+1]=pattern[l+1,c+1])then
                                                                 begin
                                                                 inclusions[e,f]:=m;
                                                                 inclusions[e+1,f]:=n;
                                                                 f:=f+1 ;
                                                                 end;
  if(mat[d,n]=pattern[l,c])and
    (mat[d,n+1]=pattern[l,c+1])and
    (mat[1,n]=pattern[l+1,c])and
    (mat[1,n+1]=pattern[l+1,c+1])then
                                 begin
                                 inclusions[e,f]:=d;
                                 inclusions[e+1,f]:=n;
                                 f:=f+1;
                                 end;
  if(mat[m,e]=pattern[l,c])and
    (mat[m+1,e]=pattern[l+1,c])and
    (mat[m,1]=pattern[l,c+1] )and
    (mat[m+1,1]=pattern[l+1,c+1]) then
                                  begin
                                  inclusions[e,f]:=m;
                                  inclusions[e+1,f]:=e;
                                  f:=f+1;
                                  end;
  matrice3:=f-1;
end;
 
 
begin
     clrscr;
     matrice1(mat);
     matrice2(pattern);
     writeln('Le nombre de couples-position de pattern dans mat sont :',matrice3(mat,pattern,inclusions));
     for i:=1 to f do
                   begin
                   for j:=1 to (d*e) do
                                     begin
                                     write (inclusions[i][j],' ',inclusions[i+1][j]);
                                     writeln(' ');
                                     end;
                   end;
     writeln(' ');
     readln; readln;
end.

Ps : Si vous voyez des erreurs , merci de me le faire savoir...

Le programme que tu as fait ne correspond pas tout à fait à l'énoncé que tu as écrit :
-> la matrice 'Pattern' est une matrice 3x3
-> tu ne testes pas si elle est présente dans une matrice 5x5 mais combien de fois elle est présente et où. Donc tu en fait plus que l'énoncé de départ (c'est pas forcément un mal mais ça complique l'exercice).

Il serait bien aussi que tes variables globales aient des noms plus parlant...

Pour que ce soit plus joli (déjà indente avec moins d'espaces, ce sera plus lisible), écrit une fonction qui teste si ta matrice pattern est présente dans une sous-matrice de la matrice initiale. Fait aussi en sorte que cette fonction te permette de résoudre un problème plus global et ne se limite pas à une matrice 2x2, tant qu'à faire.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 function contient_matrice(pattern, sousMatrice : MatricePat; ligne, colonne : integer) : boolean; var (* on suppose que nbLignesDansPattern et nbColonnesDansPattern sont des variables globales *) i, j : integer; contenue : boolean; begin contenue := true; for i :=0 to nbLignesDansPattern do (* j'ai fait commencer i à 0 parce que c'était comme ça dans ton programme, mais on commence généralement à 1 en Pascal *) begin for j := 0 to nbColonnesDansPattern do (* idem, ce qui veut dire que nbLignesDansPattern et nbColonnesDansPattern sont en fait le nb de lignes et de colonnes - 1 *) begin if (pattern[i,j] <> sousMatrice[ligne+i, colonne+j]) contenue := false; (* on ne teste que le cas d'erreur *) end; end; (* resultat : *) contient_matrice := contenue; end;
Bon, c'est juste un exemple. On peut bien sûr optimiser ça en utilisant des while à la place des for. Il faut aussi faire des tests sur la position de (ligne, colonne) dans la matrice avant d'appeler cette fonction, sinon ça plante.

Bonjour,
La sous matrice est une matrice 2*2 et la matrice pattern est une matrice 5*5
Il y aura donc un problème de dimension avec le code de Loceka.
De plus le bon algo et celui qui vérifiera tout les carrés 2*2 qu’il y a dans pattern.

Voici un exemple de programme fonctionnel :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
var
  mat55         : array [1..5,1..5] of INTEGER;
  mat22         : array [1..2,1..2] of INTEGER;
  i,j           ,
  nb_mat_detect : CARDINAL;
 
begin
  randomize;
  writeln('Matrice 5*5');
  for i:= 1 to 5 do
  begin
    for j:= 1 to 5 do
    begin
      mat55[i,j]:= random(2);
      write(mat55[i,j]:3);
    end;
    writeln;
  end;
 
  writeln('Matrice 2*2');
  for i:= 1 to 2 do
  begin
    for j:= 1 to 2 do
    begin
      mat22[i,j]:= random(2);
      write(mat22[i,j]:3);
    end;
    writeln;
  end;
 
nb_mat_detect:= 0;
 
for i:=1 to 4 do
  for j:=1 to 4 do
    if mat55[j,i] = mat22[1,1] then
      if mat55[succ(j),i] = mat22[2,1] then
        if mat55[succ(j),succ(i)] = mat22[2,2] then
          if mat55[j,succ(i)] = mat22[1,2] then
            inc(nb_mat_detect);
 
  writeln('Il y a ',nb_mat_detect,'''Matrice 2*2'' dans ''Matrice 5*5''');
end.

05/05/2007, 20h43
Loceka

Citation:

Envoyé par Ultima

Bonjour,
La sous matrice est une matrice 2*2 et la matrice pattern est une matrice 5*5

Je ne crois pas, non.

Dans son code en tout cas (et dans son énoncé) la matrice Pattern est une matrice 2x2 qu'il essaye de retrouver dans la matrice 5x5 de base.

Mon algo est une fonction qui permet de tester la présence de cette matrice Pattern dans une sous-matrice de la matrice initiale (donnée par sa première ligne et sa première colonne).

Comme je l'ai dit, cette fonction est là pour simplifier le code et pour le rendre plus générique. Après, bien entendu, il faut faire un parcours de la matrice initiale et appeler cette fonction itérativement, tant que la taille de la sous-matrice (donc la ligne et la colonne en cours) le permettent.

Autre chose : évite les nombres magiques dans un code. Je sais que les variables globales sont généralement mal vues, mais elles sont de loin préférables à des constantes en dur dans les boucles (d'ailleurs kedink avait utilisé des variables globales).
05/05/2007, 21h44
droggo

Hyk,

Citation:

Envoyé par Loceka

Autre chose : évite les nombres magiques dans un code.

Oui, il faut utiliser des définitions de constantes

Citation:

Envoyé par Loceka

Je sais que les variables globales sont généralement mal vues, mais elles sont de loin préférables à des constantes en dur dans les boucles.

Ce n'est pas la même chose.

Les valeurs en dur doivent être remplacées par des constantes définies, comme déjà dit.

Et toutes les variables utilisées par une fonction/procédure doivent être passées en paramètre.

Il faut éviter les variables globales, sources de nombreux ennuis, genre effets de bord mal gérés... et généralement code non réutilisable.

On peut presque toujours se passer de variables globales, seuls quelques rarissimes cas imposent leur présence.