Calcola occorrenze sottomatrice

di
masaniello
il
15 risposte
M
masaniello
Utente Attivo
Iscritto da
mar, 2011
Messaggi:
189

Calcola occorrenze sottomatrice

Date due matrici a e b una NxN e l'altra MxM con M<N scrivere una funzione che calcola quante sono le occorrenze disgiunte della matrice b nella matrice a(disgiunte significa che esse non devono avere elementi in comune altrimenti conta una sola volta).
Faccio un esempio
sia b[M][M]={{1,4},{1,4}} e a={{2,1,4,3,2},{0,1,4,-5,10},{4,-5,7,1,4},{10,9,1,1,4},{8,8,8,8,8}}
in questo caso le occorrenze sono due

sia b[M][M]={{1,4},{1,4}} e a={{2,1,4,3,2},{0,1,4,-5,10},{4,1,4,-5,7},{10,9,7,-9,0},{8,8,8,8,8}}
in quest'altro caso è un sola perchè le due sottomatrici hanno degli elementi in comune

ecco quello che sono riuscito a scrivere io ma è sbagliato solamente non so dove 

#include<iostream>
using namespace std;
const int N=5;
const int M=2;
bool occ(int,bool [(N-M)][(N-M)],int [N][N],int [M][M]);
bool sottomatrice(int [N][N],int [M][M],bool [(N-M)][(N-M)],int,int);
int occorrenze(int [N][N],int [M][M]);
int main()
{
    int a[N][N]={{2,1,4,3,2},{0,1,4,-5,10},{4,-5,7,1,4},{10,9,1,1,4},{8,8,8,8,8}};
    int b[M][M]={{1,4},{1,4}};
    int o;
    o=occorrenze(a,b);
    cout<<o<<endl;
return 0;
}
int occorrenze(int a[N][N],int b[M][M])
{
    int contatore=0;
    bool d[(N-M)][(N-M)];
    for(int i=0;i<(N-M);i++)
    {
        for(int j=0;j<(N-M);j++)
        {
            d[i][j]=false;
        }
    }
    for(int i=0;i<(N-M);i++)
    {
        for(int j=0;j<(N-M);j++)
        {
            if(occ(a[i][j],d,a,b))
            {
                a[i][j]=true;
                if(sottomatrice(a,b,d,i,j))
                {
                    if(a[i][j]=true)
                    contatore++;
                }
            }
        }
    }
    return contatore;
}
bool occ(int v,bool d[(N-M)][(N-M)],int a[N][N],int b[M][M])
{
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            if(b[i][j]==v)
            {
                if(d[i][j]==false)
                return true;
                else return false;
            }
        }
    }
}
bool sottomatrice(int a[N][N],int b[M][M],bool d[(N-M)][(N-M)],int i,int j)
{
    while(i<M)
    {
        while(j<M)
        {
            if(a[i][j]==false)
            {
                if(occ(a[i][j],d,a,b))
                a[i][j]=true;
                else
                return false;
            }
            j++;
        }
        i++;
    }
    return true;
}

15 Risposte

  • JollyJoker
    JollyJoker
    Utente Attivo
    Iscritto da
    set, 2011
    Messaggi:
    57

    Re: Calcola occorrenze sottomatrice


    Ciao,
    ho letto il tuo post e vorrei provare ad aiutarti..
    Se ho capito bene ti occorre solo il numero di occorrenze non individurle. 
    
if(sottomatrice(a,b,d,i,j))
                    {
                        if(a[i][j]=true)
                        contatore++;
                    }
    Non noti nulla di strano? C'è un lapalissiano type mismatch. Avendo definito gli elementi della matrice a come interi perchè poi tenti di assegnargli un tipo booleano?
    Esaminiamo quest'altra porzione di codice: 
    
bool occ(int v,bool d[(N-M)][(N-M)],int a[N][N],int b[M][M])
    {
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                if(b[i][j]==v)
                {
                    if(d[i][j]==false)
                    return true;
                    else return false;
                }
            }
        }
    }
    Così com'è scritta, questa funzione non va bene; infatti ogni volta che: 
    b[i][j]==v
    la funzione termina forzando la terminazione dei due cicli for innestati. Procedura non molto ortodossa direi.
    In ogni caso, oggi rivedo il codice.
    Buona giornata.
    [/color]
  • JollyJoker
    JollyJoker
    Utente Attivo
    Iscritto da
    set, 2011
    Messaggi:
    57

    Re: Calcola occorrenze sottomatrice


    Ciao, ti lascio a seguire la soluzione al tuo problema: 
    
#include <iostream>
using namespace std;
#include <iomanip>

//---------------------------------------------------------------------------
const unsigned int N= 5;
const unsigned int M= 2;

//---------------------------------------------------------------------------
bool CercaSottoMatrice(bool App[N][N],
                       const unsigned int,
                       const unsigned int,
                       int A[N][N],
                       int B[M][M]);
unsigned int Occorrenze(int A[N][N],
                        int B[M][M],
                        bool App[N][N]);

int main(int argc, char* argv[])
{
   //int A[N][N]={{2,1,2,3,2},{0,3,4,-5,10},{4,-5,7,1,2},{10,9,1,3,4},{8,8,8,8,8}};
   //int A[N][N]={{2,1,2,3,2},{0,3,4,-5,10},{4,3,4,-5,7},{10,9,7,-9,0},{8,8,8,8,8}};
   //int A[N][N]={{2,1,2,3,2},{0,3,4,-5,10},{4,-5,7,1,2},{1,2,1,3,4},{3,4,8,8,8}};
   //int B[M][M]={{1,2},{3,4}};
   int A[N][N]={{1,0,0,1,1},{1,0,0,1,1},{1,0,0,0,0},{1,0,0,0,0},{1,1,1,1,1}};
   int B[M][M]={{0,0},{0,0}};
   unsigned int i,
                j;
   bool App[N][N];

   cout <<"La matrice A:\n";
   for (i= 0; i<N; i++)
   {
      for (j= 0; j<N; j++)
         cout <<setw(6) <<A[i][j];
      cout <<"\n";
   }
   cout <<"La matrice B:\n";
   for (i= 0; i<M; i++)
   {
      for (j= 0; j<M; j++)
         cout <<setw(6) <<B[i][j];
      cout <<"\n";
   }
   for (i= 0; i<N; i++)
      for (j= 0; j<N; j++)
         App[i][j]= false;
   cout <<"Il numero di occorrenza di B in A e': " <<Occorrenze(A,B,App) <<"\n";
   
   cout <<"La matrice App:\n";
   for (i= 0; i<N; i++)
   {
      for (j= 0; j<N; j++)
         cout <<setw(6) <<App[i][j];
      cout <<"\n";
   }
   system ("PAUSE");
   return 0;
}
//---------------------------------------------------------------------------

bool CercaSottoMatrice(bool App[N][N],
                       const unsigned int r,
                       const unsigned int c,
                       int A[N][N],
                       int B[M][M])
{
   unsigned int i,
                j;
   bool fine;
   unsigned int count;
   bool found;

   i= 0;
   fine= false;
   count= 0;
   found= false;
   while ((!fine) && (i<M))
   {
      j= 0;
      while ((!fine) && (j<M))
      {
         if ((!App[(r+i)][(c+j)]) && (A[(r+i)][(c+j)]==B[i][j]))
            count++;
         else
            fine= true;
         j++;
      }
      i++;
   }
   if (count==(M*M))
   {
      found= true;
      for (i= 0; i<M; i++)
         for (j= 0; j<M; j++)
            App[(r+i)][(c+j)]= true;
   }
   return found;
}
//---------------------------------------------------------------------------

unsigned int Occorrenze(int A[N][N],
                        int B[M][M],
                        bool App[N][N])
{
   int elem;
   unsigned int count,
                i,
                j;

   elem= B[0][0];
   count= 0;
   for (i= 0; i<=(N-M); i++)
      for (j= 0; j<=(N-M); j++)
         if (A[i][j]==elem)
            if (CercaSottoMatrice(App,i,j,A,B))
               count++;
   return count;
}
    Questa non è certamente la soluzione più brillante ma assolve allo scopo.
    Spero d'esserti stato utile.
    Buona serata.
    [/color]
  • M
    masaniello
    Utente Attivo
    Iscritto da
    mar, 2011
    Messaggi:
    189

    Re: Calcola occorrenze sottomatrice

    Guarda non posso usare nè i char nè i puntatori per risolvere l'esercizio
    me lo ha detto il professore visto che prima dell'esame non li ha spiegati
    cme si può scrivere altrimenti?
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Calcola occorrenze sottomatrice

    Mi spieghi dove sono usati i puntatori e i char?
  • M
    masaniello
    Utente Attivo
    Iscritto da
    mar, 2011
    Messaggi:
    189

    Re: Calcola occorrenze sottomatrice

    Ho provato a riscriverlo per contare le occorrenze non disgiunte, ma niente non funziona
    perchè ?
    e come posso aggiungere la condizione occorrenze disgiunte?
    io avevo pensato di creare un array bidimensionale di booleani inizializzare tutti i suoi elementi a false e se la funzione sottomatrice è verificata, metto uguale a true ogni suo elemento. 
    
#include<iostream>
using namespace std;
const int N=5;
const int M=2;
bool sottomatrice(int [N][N],int [M][M],bool [N][N],int ,int );
int occ_disgiunte(int [N][N],int b[M][M]);
int main()
{
    int a[N][N]={{2,1,4,3,2},{0,1,4,-5,10},{4,1,4,1,4},{10,1,4,0,0},{8,7,9,10,0}};
    int b[M][M]={{1,4},{1,4}};
    cout<<occ_disgiunte(a,b);
return 0;
}
bool sottomatrice(int a[N][N],int b[M][M],bool d[N][N],int r,int c)
{
    bool trovata=true;
    int row,col;
    row=0;
    while(row<M && trovata)
    {
        col=0;
        while(col<M && trovata)
        {
            if(b[row][col]==a[r][c])
            {
                c++;
            }
            else return false;
            col++;
        }
        r++;
        row++;
    }
    return trovata;
}
int occ_disgiunte(int a[N][N],int b[M][M])
{
    bool c[N][N];
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            c[i][j]=false;
        }
    }
    int cont=0;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            if(a[i][j]==b[0][0])
            {
                if(sottomatrice(a,b,c,i,j))
                cont++;
            }
        }
    }
    return cont;
}
  • JollyJoker
    JollyJoker
    Utente Attivo
    Iscritto da
    set, 2011
    Messaggi:
    57

    Re: Calcola occorrenze sottomatrice


    Ciao,
    onestamente non capisco la tua risposta del: 27/9. Dici che non bisogna utilizzare nè char nè puntatori, ma come ti ha fatto notare anche skynet, mi dici dove vengono utilizzati..
    In secondo luogo il codice che mi hai riproposto ricalca fortemente le logica del mio a parte qualche inezia (vedi combio nomi) e quindi proprio non capisco.
    In ogni caso il problema è sugli indici in sottomatrice.
    Buona giornata.
  • M
    masaniello
    Utente Attivo
    Iscritto da
    mar, 2011
    Messaggi:
    189

    Re: Calcola occorrenze sottomatrice

    Scusami se nn ti ho risposto ma solo ora ho provato il codice.Ma calcola direttamente le occorrenze disgiunte?
    Ora vedo se capisco e poi ti faccio sapere se ho bisogno di chiarimenti.
  • M
    masaniello
    Utente Attivo
    Iscritto da
    mar, 2011
    Messaggi:
    189

    Re: Calcola occorrenze sottomatrice

    Guarda due cose non ho capito
    la prima riguarda il main

    int main(int argc, char* argv[])

    perchè hai messo questi parametri formali, non capisco e volendo si possono scrivere in altro modo
    perchè io nel main non li ho mai messi, quindi se potresti darmi una spiegazione veloce, così capisco meglio il perchè.

    la seconda cosa riguarda l'array bidimensionale di booleani bool App[N][N] nella riga seguente

    if ((!App[(r+i)][(c+j)]) && (A[(r+i)][(c+j)]==B[j]))

    non capisco perchè vai a negarlo se è già inizializzato a false
    solo se l'elemento non è stato visitato dovremmo andare avanti altrimenti no
    negandolo il booleano diventerebbe true, perchè questo?
  • JollyJoker
    JollyJoker
    Utente Attivo
    Iscritto da
    set, 2011
    Messaggi:
    57

    Re: Calcola occorrenze sottomatrice


    Ciao, provo a spiegermi meglio che posso...
    1) in questo caso (dato che il progr. non accetta parametri da riga di comando) è possibile riscrivere la funzione come: int main(void). Meglio questa forma che non mettere nulla tra le parentesi, dato che in casi particolari può creare problemi.
    2) Nella funzione Occorrenze si inizia un ciclo doppio alla ricerca del 1° elemento di B in A. Appena trovato la corrispondenza, la funzione CercaSottoMatrice provvede a cercare il resto degli elementi di B in A. Se vengono trovati (tutti) allora si provvede a porre le posizioni di App a true; come a dire "...si gli elementi settati a true fanno parte di una sotto-matrice e se ci sono altri elementi settati le 2 sotto-matrici NON hanno elementi in comune".
    Nella prima parte della condizione !App[(r+i)][(c+j)] in effetti "dico" di considerare solo gli elementi non comuni (cioè quelli settati a false). C'è un problemino però il test (l'if) ha esito favorevole se questo è vero avendo a disposizione elementi falsi sono costratto a negarli.
    Spero di essere stato sufficientemente chiaro, in ogni caso se hai dubbi fammi sapere.
  • M
    masaniello
    Utente Attivo
    Iscritto da
    mar, 2011
    Messaggi:
    189

    Re: Calcola occorrenze sottomatrice

    Io siccome devo trovare le occorrenze disgiunte vado a vedere se tutti glie elementi di b sono uguali ad M*M elementi di A e li pongo tutti uguali a true nell'array bidimensionale di booleani.Una volta trovata la prima occorrenza vado a vedere se ce ne sono altre ,controllando però(siccome devo trovare le occorrenze disgiunte)tutti gli elementi non visitati, per i quali l'array di booleani è uguale a false.Ma se ho inizializzato l'array di booleani con tutti i suoi elementi a false e poi nella condizione che ti dicevo prima vado a negarlo così andrei a prendere gli elementi già visitati.E' questo che proprio non riesco a capire!!!Io per esempio ho provato a rifarlo e a definire l'array di booleani all'interno della funzione cercaSottomatrice.Cambia qualcosa facendo così, dato che tu lo hai inizializzato nel main?
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Calcola occorrenze sottomatrice

    Se hai tempo prova ad eseguire questo piccolo programma e ti toglierai (spero) i tuoi dubbi 
    
#include <iostream>

int main()
{
   bool val = false;
   if(!val)
       std::cout << "Forse c'è qualcosa che mi sfugge";
}
    Se vedi la scitta in output e non hai capito il perche forse devi ripassare il capitolo delle espressioni condizionali.
  • M
    masaniello
    Utente Attivo
    Iscritto da
    mar, 2011
    Messaggi:
    189

    Re: Calcola occorrenze sottomatrice

    Infatti non ho capito il perchè di questo programma
    se è stata inizializzato a false e poi la nego, nell'if perchè stampa l'output?
    ma riguardo l'altra mia domanda , se definisco l'array bidimensionale all'interno della funzione cercaSottomatrice cambia qualcosa?

    ***rispondetemi ad entrambe le domande
    grazie mille
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Calcola occorrenze sottomatrice

    Io ti rispondo alla mia. l'altra la seguito joker.
    if(espressione) significa if( espressione == true) quindi

    if(!val) significa if(!val == true)

    sviluppiamolo sotto.

    val = false
    !val = true

    if(true == true) ed eccoti il tuo dubbio.

    con if(!val) si verifica se una variabile booleana è in stato false qualsiasi sia lo stato della variabile.
  • JollyJoker
    JollyJoker
    Utente Attivo
    Iscritto da
    set, 2011
    Messaggi:
    57

    Re: Calcola occorrenze sottomatrice


    Ciao masaniello,
    credo, a questo punto che il problema non stia nel codice, ma nel capire il costrutto di selezione come opera.
    Per prima cosa ti consiglio di eseguire ed analizzare il comportamento del codice che molto gentilmente skynet (che saluto) ti ha postato.
    Cerchiamo di analizzare il costrutto di selezione nella sua forma più generale: 
    
if (cond)
   Block 1
else
   Block 2
    Partendo dagli assunti seguenti:
    a) quello proposto NON è codice ma solo un modello
    b) Block 1 e 2 sono due blocchi contenenti un certo numero di linee di codice
    c) cond è la condizione da testare
    cerchiamo di capire come opera l'entità oscura if.
    La cosa è semplice:
    - se cond è vera allora eseguo Block 1
    - se cond è falsa allora eseguo Block 2
    Il "problema" è solo capire il test su cond..
    Come giustamente diceva skynet, se esplodiamo l'istruzione if, otteniamo:
    if (cond==VERO)
    Block 1
    else
    Block 2
    Allora ipotizziamo che:
    a) cond sia stata inizializzata a falso; 
    bool cond = false;
    in questo caso il test (cond==TRUE) dà come risultato FALSO (FALSE==TRUE? -> NO=FALSE), verrà eseguito Block 2
    b) cond sia stata inizializzata a true; 
    bool cond = true;
    in questo caso il test (cond==TRUE) dà come risultato VERO (TRUE==TRUE? -> SI=TRUE), verrà eseguito Block 1
    Sino a qui non dovrebbero esserci più problemi, credo.
    Ora vorrei fare qualcosa di diverso (invertire la logica) e cioè vorrei che venga eseguito il Block 1 anche se cond è inizializzato a falso, come si può fare?
    Ovviamente si può fare e ci sono ben due soluzioni:
    1) inverto l'if, 
    
if (cond==VERO)
   Block 2
else
   Block 1
    questo fa sì che:
    - se cond è vera allora eseguo Block 2
    - se cond è falsa allora eseguo Block 1
    2) inverto la condizione nell'if, 
    
if (!cond==VERO)
   Block 1
else
   Block 2
    Non ci resta che ripetere quando detto prima ed allora ipotizziamo che:
    a) cond sia stata inizializzata a falso; 
    bool cond = false;
    in questo caso il test (!cond==TRUE) dà come risultato VERO (!(FALSE) ->TRUE==TRUE? -> SI=TRUE), verrà eseguito Block 1
    b) cond sia stata inizializzata a true; 
    bool cond = true;
    in questo caso il test (!cond==TRUE) dà come risultato FALSO (!(TRUE) -> FALSE==TRUE? -> NO=FALSE), verrà eseguito Block 2
    Mi sembra scontato, ma forse è meglio specificarlo che la prima soluzione pur essendo possibile NON è la soluzione ottimale poichè costringe la rescrizione del codice e non è detto che la cosa sia così semplice; la seconda invece, comporta SOLO l'aggiunta di un simbolo di negazione. Tira tu le somme .
    Per chiudere la questione aggiungo solo che il C ed C++ (in questo caso) ma anche altri linguaggi come JAVA ad esempio permettono una semplificazione sintattica che nulla toglie alla semantica del costrutto e cioè il sotto-intendimento del test nell'if, per cui si giunge alla forma arci-nota del costrutto di selezione in C o C++ che è: 
    
if (cond)   //Ometto, perchè sottointeso "==true".
   Block 1
else
   Block 2
    Credo si veramente tutto; non saprei come spiegarlo più semplicemente .
    Per quanto concerne l'array bidimensionale (per noi matrice) di booleani App (Appoggio), io mi sono regolato considerando che tale matrice viene effettivamente modificata solo nella funzione CercaSottoMatrice, mentre è sostanzialmente di "passaggio" tanto nella funzione main quanto in Occorrenze.
    Tutto questo comporta che per:
    - CercaSottoMatrice, App è un parametro di uscita
    - main e Occorrenze, App è un parametro di ingresso-uscita
    Se consideri la possibilità di definire App in CercaSottoMatrice poi come fai ad effettuare la stampa della matrice nel main? Nascerebbe un probleme di campo di visibilità delle variabili. In pratica il main non "conoscerebbe" più App e quindi non potrebbe stamparla.
    [/color]
Devi accedere o registrarti per scrivere nel forum
15 risposte