Trovare una sequenza numerica all'interno di una matrice

di il
1 risposte

Trovare una sequenza numerica all'interno di una matrice

Salve a tutti, sono una studentessa di ingegneria e, esercitandomi in vista dell'esame, mi sono imbattuta in questo esercizio, in cui non riesco a venirne a capo.

il testo è il seguente:
'Scrivere un programma che, data una matrice M(n, n)di numeri ed una sequenza di numeri S(m) m<n, sia capace di individuare tra gli elementi di M quelli da cui parte la sequenza S procedendo in orizzontale (0), in verticale (1) o in obliquo (-1). Se K sono gli elementi individuati, costruire partendo da essi, la matrice A(K,3)in cui ogni riga contiene gli indici del corrispondente elemento (colonna 1 e 2) e la direzione (colonna 3)0,1, -1 in cui la sequenza S si sviluppa.'

La prima parte (ovvero creazione e definizione della matrice e del vettore) sono riuscita a farla, il problema sorge nel controllo della matrice: il mio codice entra in loop e non riesco a trovare il modo per sistemarlo.

il primo metodo che ho utilizzato è questo:
while j<=n
    while k<=n
        if A(j,k)==v(z)
            while A(j,k+1)==v(z+1) || a(j,k-1)==v(z+1) && z<=m  %controllo per colonne
                if A(j,k+1)==v(z)
                    k=k+1;
                else 
                    k=k-1;
                end
                if z==m
                    tr=1;
                end
                z=z+1;
            end
            while A(j+1,k)==v(z+1) || A(j-1,k)==v(z+1) && z<=m %controllo per righe
                if A(j+1,k)==v(z+1)
                    j=j+1;
                else
                    j=j-1;
                end
                if z==m
                    tr=0;
                end
            end
            while(A(j-1,k-1)==v(z+1) || A(j-1,k+1)==v(z+1) || A(j+1,k-1)==v(z+1) || A(j+1,k+1)==v(z+1)) && z<=m %controllo in obliquo
                if A(j-1,k-1)==v(z+1) || A(j-1,k+1)==v(z+1)
                    j=j+1;
                    k=k+1;
                else
                    j=j-1;
                    k=k-1;
                end
                if z==m
                    tr=-1;
                end
            end
        end
        k=k+1;
    end
    j=j+1;
end
Per ovviare al problema, ho provato anche a separare i cicli, ma anche così il programma entrava in loop.
while j<=n
    while A(j+1,k)==v(z+1) || A(j-1,k)==v(z+1)&& z<=m %controllo per righe
                if A(j+1,k)==v(z+1)
                    j=j+1;
                else
                    j=j-1;
                end
                if z==m
                    tr=0;
                end
    end
end
while k<=n
     while A(j,k+1)==v(z+1) && z<=m  %controllo per colonne
                if A(j,k+1)==v(z)
                    k=k+1;
                else 
                    k=k-1;
                end
                if z==m
                    tr=1;
                end
                z=z+1;
     end
end
while j<=n && k<=n
    while(A(j-1,k-1)==v(z+1) || A(j-1,k+1)==v(z+1) || A(j+1,k-1)==v(z+1) || A(j+1,k+1)==v(z+1)) && z<=m %controllo in obliquo
                if A(j-1,k-1)==v(z+1) || A(j-1,k+1)==v(z+1)
                    j=j+1;
                    k=k+1;
                else
                    j=j-1;
                    k=k-1;
                end
                if z==m
                    tr=-1;
                end
    end
end
Ringrazio già in anticipo a chi mi darà una risposta a questo problema!

1 Risposte

  • Re: Trovare una sequenza numerica all'interno di una matrice

    Una soluzione relativamente semplice che consente di limitare i cicli for / while potrebbe essere:
    [*] cercare con la funzione "find" le occorrenze (numero di riga e colonna) del primo valore della sequenza
    [*] per la ricerca della sequenza in "orizzontale" e "verticale" all'interno della matrice
    [*][*] creare un ciclo "for" che scorra le occorrenze individuate al passo precedente
    [*][*] estrarre dalla matrice un vettore della lunghezza della sequenza a partire dalla posizione della i-esima occorrenza
    [*][*] calcolare il vettore differenza tra la sequenza ed il vettore estratto
    [*][*] usare la funzione "any" (preceduta dal segno "~") per verificare se tutti gli elementi del vettore differenza sono uguali a "0"
    [*][*] se questa condizione è verificata, la i-esima occorrenza della sequenza è stata trovata

    Per le "direzioni" oblique, non è chiara, nella domanda, la direzione, visto che esistono quattro direzioni possibili "NE, NW, SW, SE"
    A prescindere, sarà sufficiente una piccola modifica alla procedura precedente.
    Bisogna infatti, stabilita la direzione desiderata, estrarre un vettore diagonale e confrontarlo con la sequenza.

    Di seguito, una possibile implementazione; per le direzioni "oblique" è stato modificato il codice identificativo da "-1" a "-1", "-2", "-3" e "-4" in modo da indicare la specifica direzione.
    I commento nel codice dovrebbero chiarire i vari passaggi.
    
    
    % Define an input matrix
    m=[14    4   12   15    1   23   31   16    2    6
       21    6   25   23   18   21   25   18   13   25
       14   10   12   25   15   33   19    6    8   23
        6   25   23   29   24   18    6   25   23   18
       25   22    3    6   25   23   25    2   21   19
       23   10   25   18   25    4   23   14    3    6
       20   23   25   11    6   23   11    7   16   25
       30   23    8    4   25    6   25   23   28   23
        7   32    4    6   17    7   25   19   18   33
       31   31   18   22   28    7   12   23   16   18
       ];
    % Clear the output variable
    clear f*
    % Get the size of the input matrix
    [mr,mc]=size(m);
    % Define the sequence of number
    s=[6 25 23];
    % Get the lenght of the sequence of numbers
    n=length(s);
    % Finde all the occurrence of the first element of the sequence of numbers
    [r,c]=find(m == s(1));
    % Initialize the counter
    cnt=0;
    % Search for the sequence in the matrix
    % North-Est direction
    % Loop over the occurrence of the sequence in the matrix
    for i=1:length(r)
       % Reset the temporary array
       v=[];
       % Avoid accessing element of the matrix outside its bound
       if(r(i)-n+1 > 0 && c(i)+n-1 <= mc)
          % Store in the temporary array n numbers of the input matrix starting
          % from the i-th occurrence of the first number of the sequence being "n"
          % the lenght of the sequence
          for j=0:n-1
             v=[v m(r(i)-j,c(i)+j)]
          end
          % If the difference between the sequence and the values in the temporary
          % array is "0" then the sequence has been found in the matrix
          if(~any(v-s))
             % Increment the counter and store the positiion indices (rew, column)
             % and the directionb identifier in the output matrix
             cnt=cnt+1;
             f_c(cnt,1)=r(i);
             f_c(cnt,2)=c(i);
             f_c(cnt,3)=-1;
          end
       end
    end
    % North-West
    % Same logic as per the previous section
    for i=1:length(r)
       v=[];
       if(r(i)-n+1 > 0 && c(i)-n+1 > 0)
          for j=0:n-1
             v=[v m(r(i)-j,c(i)-j)]
          end
          if(~any(v-s))
             cnt=cnt+1;
             f_c(cnt,1)=r(i);
             f_c(cnt,2)=c(i);
             f_c(cnt,3)=-2;
          end
       end
    end
    % South-West
    % Same logic as per the previous section
    for i=1:length(r)
       v=[];
       if(r(i)+n-1 <= mr && c(i)-n+1 > 0)
          for j=0:n-1
             v=[v m(r(i)+j,c(i)-j)]
          end
          if(~any(v-s))
             cnt=cnt+1;
             f_c(cnt,1)=r(i);
             f_c(cnt,2)=c(i);
             f_c(cnt,3)=-3;
          end
       end
    end
    % South-Est
    % Same logic as per the previous section
    for i=1:length(r)
       v=[];
       if(r(i)+n-1 <= mr && c(i)+n-1 <= mc)
          for j=0:n-1
             v=[v m(r(i)+j,c(i)+j)]
          end
          if(~any(v-s))
             cnt=cnt+1;
             f_c(cnt,1)=r(i);
             f_c(cnt,2)=c(i);
             f_c(cnt,3)=-4;
          end
       end
    end
    
    % Horizontal
    % Loop over the occurrence of the first value of the sequence in the matrix
    for i=1:length(c)
       % Avoid accessing element of the matrix outside its bound
       if(c(i)+n-1 <= mc)
          % If the difference between the sequence and the corresponding number 
          % of values in the input matrix (starting from the i-th occurrence
          % of the first number oif the sequence is "0" then the sequence has been
          % found in the matrix
          if(~any(m(r(i):r(i),c(i):c(i)+n-1)-s))
             % Increment the counter and store the positiion indices (rew, column)
             % and the directionb identifier in the output matrix
             cnt=cnt+1;
             f_c(cnt,1)=r(i);
             f_c(cnt,2)=c(i);
             f_c(cnt,3)=0;
          end
       end
    end
    % Vertical
    % Same logic as per the previous section
    for i=1:length(r)
       if(r(i)+n-1 <= mr)
          if(~any(m(r(i):r(i)+n-1,c(i):c(i))-s'))
             cnt=cnt+1;
             f_c(cnt,1)=r(i);
             f_c(cnt,2)=c(i);
             f_c(cnt,3)=1;
          end
       end
    end
    
Devi accedere o registrarti per scrivere nel forum
1 risposte