Calcola occorrenze sottomatrice
Date due matrici a e b una NxN e l'altra MxM con M
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 il mio codice ma è sbagliato ,solamente non so dove
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 il mio codice 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;
}
Risposte
Intanto quel j<(N-M) andrebbe cambiato in j<=(N-M). Poi ho visto un altro punto in cui scambi le matrici a e b.
Io ti inviterei a guardare come lo farei io:
good viene incrementato quando viene trovata una sottomatrice disgiunta.
equal_found va TRUE quando si trova un match tra due elementi per cui la matrice non può essere più disgiunta.
In tutto vengono fatti $(N-M+1)^2M^4$ cicli.
Si può anche fare in un altro modo, con $2(N-M+1)^2M^2$ cicli.
Abituati anche a mettere qualcosa che eviti alla macchina di fare milioni di cicli (anche se qui è superfluo)
Io ti inviterei a guardare come lo farei io:
good viene incrementato quando viene trovata una sottomatrice disgiunta.
equal_found va TRUE quando si trova un match tra due elementi per cui la matrice non può essere più disgiunta.
In tutto vengono fatti $(N-M+1)^2M^4$ cicli.
Si può anche fare in un altro modo, con $2(N-M+1)^2M^2$ cicli.
Abituati anche a mettere qualcosa che eviti alla macchina di fare milioni di cicli (anche se qui è superfluo)
#include<iostream>
using namespace std;
const int N=5;
const int M=2;
int occorrenze(int [N][N],int [M][M]);
int _tmain(int argc, _TCHAR* argv[])
{
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);
if ((o)!=-1) cout<<o<<endl;
else cout<<"Errore"<<endl;
return 0;
}
int occorrenze(int a[N][N],int b[M][M])
{
int good = 0;
bool equal_found = false;
if (((abs(N-M)+1)*M^2) > 100000) return -1;
for (int i=0;i<=(N-M);i++){
for (int j=0;j<=(N-M);j++){
equal_found = false;
for (int q=0;q<M;q++){
for (int p=0;p<M;p++){
for (int r=0;r<M;r++){
for (int s=0;s<M;s++){
if (b[r][s]==a[(q+i)][(p+j)]) {
equal_found=true;
}
if (equal_found) break;
}
if (equal_found) break;
}
if (equal_found) break;
}
if (equal_found) break;
}
if (!equal_found) good++;
}
}
return good;
}
@Quinzio: dovrebbe essere necessario includere tchar.h per poter usare _tmain e _TCHAR. Ma non credo abbia comunque senso usare questa libreria in questo caso. Trovo poi abbastanza difficile da seguire un codice con 6 cicli annidati dai quali è possibile uscire prematuramente. Sarebbe meglio dividere il codice in diverse funzioni.
Nel seguente pezzo di codice:
hai scritto = al posto di == nel ciclo if. È voluto oppure accidentale?
In questa funzione invece manca un return alla fine della funzione. Se infatti b[j]==v non fosse mai vero si arriverebbe alla fine di tutti i cicli e il codice non saprebbe che cosa restituire. Sei poi certo che sia giusto uscire anche con false in quel punto (non sono certo che cosa tu stia cercando di ottenere da quella funzione)?
Nel seguente pezzo di codice:
if(sottomatrice(a,b,d,i,j)) {
if(a[i][j]=true)
contatore++;
}
hai scritto = al posto di == nel ciclo if. È voluto oppure accidentale?
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;
}
}
}
}
In questa funzione invece manca un return alla fine della funzione. Se infatti b[j]==v non fosse mai vero si arriverebbe alla fine di tutti i cicli e il codice non saprebbe che cosa restituire. Sei poi certo che sia giusto uscire anche con false in quel punto (non sono certo che cosa tu stia cercando di ottenere da quella funzione)?
ora rivedo il codice e domani vi faccio sapere così mi aiutate meglio
è vero c'è qualche errore ma di distrazione
è vero c'è qualche errore ma di distrazione
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.
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;
}
Eccoti una versione corretta del tuo codice. Tieni comunque conto che questo codice non trova sempre il numero massimo di occorrenze ma solo un numero di sottomatrici distinte che si possono trovare privilegiando sempre quelle che sono più in alto o più a sinistra. Una il metodo della matrice di bool.
Il mio codice ha ottimizzato il numero di visite degli elementi della matrice controllandoli non più del necessario. Nel tuo codice non hai comunque modificato d (che io ho chiamato chmat) ne ho visto controlli espliciti ai suoi valori.
Per vedere che non vale puoi provare con la matrice $ a = ( ( 0 , 1 , 2 , 0 , 0 ),( 1 , 2 , 1 , 2 , 0 ),( 2 , 1 , 2 , 1 , 0 ),( 0 , 0 , 0 , 1 , 2 ),( 0 , 0 , 0 , 2 , 1) ) $ e sottomatrice $ b = ( ( 1 , 2),( 2 , 1)) $ che ha evidentemente un massimo di 3 sottomatrici disgiunte uguali a b mentre il codice te ne darà solo 2 in quanto quella in alto prevarrà sulle altre due. Il codice per trovare il massimo è comunque più complesso e richiede di trovarle tutte.
Il mio codice ha ottimizzato il numero di visite degli elementi della matrice controllandoli non più del necessario. Nel tuo codice non hai comunque modificato d (che io ho chiamato chmat) ne ho visto controlli espliciti ai suoi valori.
#include<iostream>
unsigned int const N = 5;
unsigned int const M = 2;
int const occ_disgiunte(int const mat[N][N], int const subm[M][M]);
bool const sottomatrice(int const mat[N][N], int const subm[M][M], unsigned int const I, unsigned int const J);
void reverse_sub(bool chmat[N][N], unsigned int const subdim, unsigned int const I, unsigned int const J);
int main()
{
int const 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 const b[M][M] = {{1,4},
{1,4}};
std::cout << occ_disgiunte(a,b) << std::endl;
return 0;
}
int const occ_disgiunte(int const mat[N][N], int const subm[M][M])
{
bool chmat[N][N];
unsigned int cont = 0;
for(unsigned int i=0; i<N; ++i)
{
for(unsigned int j=0; j<N; ++j)
{
chmat[i][j] = false;
}
}
for(unsigned int i=0; i <= N-M; ++i) {
for(unsigned int j=0; j <= N-M; ++j) {
if((mat[i][j] == subm[0][0]) &&
(!chmat[i][j]) &&
(!chmat[i][j+M-1])) {
if(sottomatrice(mat, subm, i, j))
{
reverse_sub(chmat, M, i, j);
++cont;
j += (M-1);
}
}
}
}
return cont;
}
bool const sottomatrice(int const mat[N][N], int const subm[M][M], unsigned int const I, unsigned int const J)
{
bool retval = (I + M <= N);
for(unsigned int i = 0; (i < M)&&(retval); ++i) {
for(unsigned int j = 0; (j < M)&&(retval); ++j) {
retval = (mat[I+i][J+j] == subm[i][j]);
}
}
return retval;
}
void reverse_sub(bool chmat[N][N], unsigned int const subdim, unsigned int const I, unsigned int const J)
{
unsigned int const Imax = (I + subdim <= N)? I + subdim : N;
unsigned int const Jmax = (J + subdim <= N)? J + subdim : N;
for(unsigned int i = I; i < Imax; ++i) {
for(unsigned int j = J; j < Jmax; ++j) {
chmat[i][j] = !chmat[i][j];
}
}
}
Per vedere che non vale puoi provare con la matrice $ a = ( ( 0 , 1 , 2 , 0 , 0 ),( 1 , 2 , 1 , 2 , 0 ),( 2 , 1 , 2 , 1 , 0 ),( 0 , 0 , 0 , 1 , 2 ),( 0 , 0 , 0 , 2 , 1) ) $ e sottomatrice $ b = ( ( 1 , 2),( 2 , 1)) $ che ha evidentemente un massimo di 3 sottomatrici disgiunte uguali a b mentre il codice te ne darà solo 2 in quanto quella in alto prevarrà sulle altre due. Il codice per trovare il massimo è comunque più complesso e richiede di trovarle tutte.
Io dividerei prima di tutto il problema in due fasi distinte:
1. La ricerca di tutte le sottomatrici uguali ad una matrice data. Chiamo l'insieme di tutte queste matrici con \( S \).
2. La ricerca di un sottoinsieme di \( S \) di lunghezza massimo tale che le sottomatrici siano distinte.
Il primo problema può essere risolto abbastanza facilmente (e in effetti è già stato risolto in questa discussione) per cui mi soffermerei più che altro sul secondo punto. Vediamo per prima cosa un caso particolare. Supponiamo di prendere una sottomatrice \( A \in S \) e supponiamo che si intersechi con altre \(3\) sottomatrici. Eliminando questa sottomatrice, il numero totale di intersezioni tra sottomatrici di \(S\) sarà sceso di \(3\) perdendo un solo elemento della matrice. Viceversa, se decidessimo di utilizzare questa sottomatrice, dovremo eliminare dall'insieme le \(3\) sottomatrici che si intersecano con essa. Questo esempio ci permette di capire che un buon metodo per decidere quale sottomatrice conviene eliminare (quale sottomatrice ha cioè la maggior probabilità di portarci all'insieme con cardinalità massima) è quello di prendere la sottomatrice con il numero più grande di intersezioni con le altre. Considera però ora il seguente esempio:
- \(A\) ha intersezione con le sottomatrici \(B, C, D, E\).
- \(B\) ha intersezione con \( A, C, F \).
- \(C\) ha intersezione con \( A, B, G \).
- \(D\) ha intersezione con \( A, E, H \).
- \(E\) ha intersezione con \( A, D, I \).
- \(F\) ha intersezione con \( B \).
- \(G\) ha intersezione con \( C \).
- \(H\) ha intersezione con \( D \).
- \(I\) ha intersezione con \( E \).
Se eliminiamo semplicemente la prima sottomatrice con il numero massimo di intersezioni otteniamo il seguente:
1. Prima eliminiamo \(A\) che ha \(4\) intersezioni e abbassiamo il numero di intersezioni di \(B, C, D, E\) a \(2\). A questo punto eliminiamo \(B\) riducendo il numero di intersezioni di \(C\) (che arriva ad una sola intersezione) e di \(F\) che non ha più a questo punto intersezioni. Ignoriamo quindi a questo punto \(C\) ed eliminiamo \(D\) che ha \(2\) intersezioni e a questo punto \(E\) rimane con una sola intersezione e \(H\) con nessuna. La prima sottomatrice con una sola intersezione è a questo punto \(C\) che eliminiamo lasciando \(G\) senza intersezione e poi facciamo lo stesso con \(E\) e abbiamo terminato. Alla fine di questo procedimento abbiamo il seguente risultato:
ELIMINATI: \(A, B, C, D, E\)
MANTENUTI: \(F, G, H, I\)
Il sottoinsieme trovato ha quindi \(4\) elementi. Se però avessimo deciso di mantenere \(A\) ed eliminare quindi \(B, C, D, E\) saremmo arrivati ad un risultato migliore, cioè
ELIMINATI: \(B, C, D, E\)
MANTENUTI: \(A, F, G, H, I\)
che credo essere il miglior risultato possibile. Abbiamo quindi bisogno di un algoritmo migliore. Direi che ti lascerei riflettere per ora..
1. La ricerca di tutte le sottomatrici uguali ad una matrice data. Chiamo l'insieme di tutte queste matrici con \( S \).
2. La ricerca di un sottoinsieme di \( S \) di lunghezza massimo tale che le sottomatrici siano distinte.
Il primo problema può essere risolto abbastanza facilmente (e in effetti è già stato risolto in questa discussione) per cui mi soffermerei più che altro sul secondo punto. Vediamo per prima cosa un caso particolare. Supponiamo di prendere una sottomatrice \( A \in S \) e supponiamo che si intersechi con altre \(3\) sottomatrici. Eliminando questa sottomatrice, il numero totale di intersezioni tra sottomatrici di \(S\) sarà sceso di \(3\) perdendo un solo elemento della matrice. Viceversa, se decidessimo di utilizzare questa sottomatrice, dovremo eliminare dall'insieme le \(3\) sottomatrici che si intersecano con essa. Questo esempio ci permette di capire che un buon metodo per decidere quale sottomatrice conviene eliminare (quale sottomatrice ha cioè la maggior probabilità di portarci all'insieme con cardinalità massima) è quello di prendere la sottomatrice con il numero più grande di intersezioni con le altre. Considera però ora il seguente esempio:
- \(A\) ha intersezione con le sottomatrici \(B, C, D, E\).
- \(B\) ha intersezione con \( A, C, F \).
- \(C\) ha intersezione con \( A, B, G \).
- \(D\) ha intersezione con \( A, E, H \).
- \(E\) ha intersezione con \( A, D, I \).
- \(F\) ha intersezione con \( B \).
- \(G\) ha intersezione con \( C \).
- \(H\) ha intersezione con \( D \).
- \(I\) ha intersezione con \( E \).
Se eliminiamo semplicemente la prima sottomatrice con il numero massimo di intersezioni otteniamo il seguente:
1. Prima eliminiamo \(A\) che ha \(4\) intersezioni e abbassiamo il numero di intersezioni di \(B, C, D, E\) a \(2\). A questo punto eliminiamo \(B\) riducendo il numero di intersezioni di \(C\) (che arriva ad una sola intersezione) e di \(F\) che non ha più a questo punto intersezioni. Ignoriamo quindi a questo punto \(C\) ed eliminiamo \(D\) che ha \(2\) intersezioni e a questo punto \(E\) rimane con una sola intersezione e \(H\) con nessuna. La prima sottomatrice con una sola intersezione è a questo punto \(C\) che eliminiamo lasciando \(G\) senza intersezione e poi facciamo lo stesso con \(E\) e abbiamo terminato. Alla fine di questo procedimento abbiamo il seguente risultato:
ELIMINATI: \(A, B, C, D, E\)
MANTENUTI: \(F, G, H, I\)
Il sottoinsieme trovato ha quindi \(4\) elementi. Se però avessimo deciso di mantenere \(A\) ed eliminare quindi \(B, C, D, E\) saremmo arrivati ad un risultato migliore, cioè
ELIMINATI: \(B, C, D, E\)
MANTENUTI: \(A, F, G, H, I\)
che credo essere il miglior risultato possibile. Abbiamo quindi bisogno di un algoritmo migliore. Direi che ti lascerei riflettere per ora..
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo