Ricerca di matrice in matrice

di
lightyagami
il
1 risposte
L
lightyagami
Pochi posts
Iscritto da
ott, 2015
Messaggi:
3

Ricerca di matrice in matrice

Ciao a tutti, e grazie in anticipo a chi proverà a risolvere il mio problema.
Essenzialmente devo acquisire da tastiera una matrice NxN grande e una più piccola matrice MxM (con ovviamente M<N), per poi ricercare se e quante volte la matrice piccola è contenuta in quella grande.
La mia idea di base è : scandire ogni sottomatrice MxM della matrice grande, e confrontare ogni elemento con il corrispettivo elemento della matrice piccola, ogni volta che tale uguaglianza si verifica vera, count aumenta di una unità. Ogni volta che count raggiunge il valore NxN vuol dire che la matrice piccola è stata trovata il quella grande
In realtà mi sembra un esercizio abbastanza banale, ma non riesco a capire come impostare i valori dei cicli for vari. (Per velocizzare le prove, ho già allocato preventivamente i valori delle matrici).

#include <stdio.h>
#include <stdlib.h>
#define N 5
#define M 2

int main()
{
int matrice_grande[N][N] = {{1,23,13,22,6},{5,1,23,44,-3},{11,5,1,88,6},{88,22,11,9,15}};
int matrice_piccola[M][M] = {{1,23},{5,1}};

int i,j,k,z;
int count =0 , occorrenze=0;

/*printf("Inserisci gli elementi della matrice di dimensione %d %d\n", N , N);
for(i=0 ; i<N; i++)
for (j=0 ; j<N ; j++)
scanf("%d", &matrice_grande[j]);*/

/*printf("Inserisci gli elementi della matrice di dimensione %d %d\n", M , M);
for ( i=0; i<M;i++)
for(j=0; j<M ; j++)
scanf("%d", &matrice_piccola[j]);*/

for(i=N-M-pr ; i<N; i++)
for(j=0 ; j<N && j<pc; j++)
for( k = 0; k<M ; k++)
for (z=0 ; z<M ; z++)
{if (matrice_grande[z] == matrice_piccola[k][j])
count++;

else count=0;
if (count == M*M){
occorrenze++;
count=0;}
}

printf("La matrice di dimensione %d %d si trova %d volte nella matrice di dimensione %d %d \n", M,M, occorrenze, N , N);

return 0;
}

MATRICE GRANDE
1 23 13 22 6
5 1 23 44 -3
11 5 1 88 6
88 22 11 9 15

MATRICE PICCOLA
1 23
5 1
(In questo esempio le occorrenze sono due)
13 17 26 46 3

1 Risposte

  • minomic
    minomic
    Molto attivo
    Iscritto da
    nov, 2010
    Messaggi:
    1137

    Re: Ricerca di matrice in matrice

    Ciao,
    è passato qualche giorno ma forse sei ancora interessato al problema. Nel caso, ecco una possibile soluzione:
    
#include <stdio.h>
#include <stdlib.h>
#define N 5
#define M 2

int main()
{
    int matrice_grande[N][N] = {{1,23,13,22,6},{5,1,23,44,-3},{11,5,1,88,6},{88,22,11,9,15}};
    int matrice_piccola[M][M] = {{1,23},{5,1}};

    int i,j,k,z;
    int count = 0, occorrenze = 0;

    for(i = 0; i < N; ++i) {
        for(j = 0; j < N; ++j) {
        	// per ogni elemento della matrice grande

        	// scansiono un "intorno" corrispondente alla matrice piccola
        	// nota: i valori di 'k' e 'z' sono di fatto degli offset
            for(k = 0; k < M; ++k) {
                for(z = 0; z < M; ++z) {
                    if((i+k) < N && (j+z) < N && matrice_grande[i + k][j + z] == matrice_piccola[k][z]) {
                        ++count;
                        if (count == M*M) {
                            occorrenze++;
                            count=0;
                        }
                    } else {
                        count = 0;
                        break;    // non c'e' corrispondenza: salta all'elemento successivo
                    }
                }
            }
        }
    }

    printf("La matrice di dimensione %dx%d si trova %d volte nella matrice di dimensione %dx%d \n", M, M, occorrenze, N, N);

    return 0;
}
    Forse si può fare qualcosa di più efficiente, ma intanto questo dovrebbe funzionare. E in più è molto semplice da capire.

    Se hai qualche dubbio, chiedi pure.
    Ciao.
Devi accedere o registrarti per scrivere nel forum
1 risposte