Nippolo ha scritto:
Ciao, per quanto riguarda il passaggio di matrici ad una funzione non ti preoccupare, è un "problema" di facile e immediata risoluzione; in ogni caso prima di approfondire la questione inizia a postare il codice che hai già scritto.
Passiamo quindi alla questione principale, ossia la ricerca della sottomatrice quadrata di ordine massimo:
1) innanzitutto bisogna chiarire cosa si intende per sottomatrice; la definizione formale è quella di matrice ricavata dalla matrice completa rimuovendo alcune righe e/o colonne (nel caso specifico, dal momento che si parla di sottomatrice quadrata, le righe e colonne rimosse devono essere in egual numero). Data quindi la seguente matrice A:
1 2 3 4
5 6 7 8
9 0 1 2
3 4 5 6
e considerando la suddetta definizione di sottomatrice, anche la seguente
2 4
0 2
è da considerarsi una sottomatrice di A. Sei d'accordo? O utilizzi una definizione diversa di sottomatrice?
ecco, io avevo interpretato "sottomatrice" in modo diverso.
Per esempio sono sottomatrici della matrice che hai presentato:
1 2 3
5 6 7
9 0 1
1 2
5 6
2 3 4
6 7 8
0 1 2
e così via...
Però, ora che mi ci fai pensare, potrebbe essere che il mio prof. intendesse esattamente quel che dici tu. Anche perchè altrimenti diventerebbe esageratamente complicato!
[/quote]
2) riguardo alla funzione ricorsiva a cui hai pensato, non sono sicuro che funzionerebbe. Per esempio considera la seguente matrice:
-1 -1 -1 2
-1 -1 -1 2
-1 -1 -1 2
2 2 2 2
risulta evidente che se la dividi in 4 sottomatrici, perderai per strada la sottomatrice di ordine 3.
Inoltre dividere ricorsivamente la matrice in 4 parti risulta agevole solo fin quando la dimensione N è una potenza di 2;
[/quote]
ecco qui hai ragione, ma perchè non mi sono spiegata bene (era un po' tardi, giuro di saper parlare l'iatliano ).
Intendevo creare 4 matrici:
la prima:
-1 -1 -1
-1 -1 -1
-1 -1 -1
la seconda:
-1 -1 2
-1 -1 2
-1 -1 2
la terza:
-1 -1 -1
-1 -1 -1
2 2 2
la quarta:
-1 -1 2
-1 -1 2
2 2 2
e così via, finchè non trovo la dimensione massima, utilizzando una funzione ricorsiva.
[/quote]
3) se sei d'accordo con i punti 1) e 2), il mio consiglio è quello di implementare un algoritmo che sfrutta la definizione stessa di sottomatrice data sopra.
[/quote]
penso che ora sfrutterò questa definizione.
Inoltre ieri notte ho provato ad implementare un algoritmo sulla base della mia idea.
E' uscito esageratamente complicato e non sempre funziona, di conseguenza è sbagliato.
in ogni caso, ti ringrazio moltissimo per la tua risposta.
Ti aggiornerò