Esame Di Programmazione

di il
23 risposte

Esame Di Programmazione

Salve a tutti!
Sono nuova nel forum e sono una studentessa di matematica. Sto studiando per poter sostenere un esame di programmazione.
Mi chiedevo se qualcuno di voi potesse aiutarmi.
La traccia dell'esercizio è questa:
"Scrivere un programma in C che generi una matrice casuale M di dimensione NxN (N costante arbitraria definista all'inizio del programma) con elementi interi appartenenti all'intervallo [-5,5]. Quindi restituisca la massima dimensione di una sottomatrice quadrata di M che risulti formata esclusivamente da numeri negativi."

avevo pensato di scrivere una funzione ricorsiva, in cui ogni volta dividevo la matrice in 4 sottomatrici e controllavo ognuna di esse, se fosse formata tutta da numeri negativi.
Ma mi risulta eccessivamente macchinoso.
Pensate che sia la soluzione migliore? Un ulteriore dubbio che mi viene è che, quando si definisce una funzione in C che prende in input una matrice, la sua seconda dimensione deve essere costante, mentre l'altra va inserita. Riesco ad arginare questo problema?
Scusate l'ignoranza, ma mi sono approcciata da poco alla programmazione.

23 Risposte

  • Re: Esame Di Programmazione

    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?

    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;

    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.

    Inizia a chiarire i punti di cui sopra e poi magari se ne può discutere insieme.
  • Re: Esame Di Programmazione

    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:
    le righe e colonne rimosse devono essere in egual numero). Data quindi la seguente matrice
    Credo che valga solo se la matrice di partenza e' quadrata, ma l'esercizio dice NxM.
    Non e' che il problema sia la conoscenza dell'algoritmo per l'estrazione delle sottomartrici, piuttosto che la conoscenza del linguaggio di programmazione ?
  • Re: Esame Di Programmazione

    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ò
  • Re: Esame Di Programmazione

    HATFIELD ha scritto:


    ma l'esercizio dice NxM
    In realtà dice NxN, mentre M è il nome della matrice!

    SonoUnaMatematica ha scritto:


    ecco, io avevo interpretato "sottomatrice" in modo diverso.
    ...
    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!
    In realtà è più complicato basarsi sulla mia definizione (in quanto contempla un maggior numero di casi) che sulla tua interpretazione.
    Ad ogni modo per proseguire bisogna innanzitutto stabilire la definizione di sottomatrice che si vuole abbracciare.
    Se cerchi su internet una definizione formale troverai quella da me riportata nel precedente post, ossia "matrice ricavata dalla matrice completa rimuovendo alcune righe e/o colonne". In pratica la suddetta definizione consente di avere sottomatrici formate da righe/colonne non consecutive (consecutive nella matrice completa intendo), mentre la tua interpretazione no.
    Quindi in definitiva su quale delle due interpretazioni vuoi costruire l'algoritmo? Magari vale la pena chiedere al prof per fugare ogni dubbio?!

    SonoUnaMatematica ha scritto:


    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ò
    In effetti non si tratta di un problema proprio semplicissimo, in ogni caso una volta chiarito cosa si intende per sottomatrice, proverò a ragionarci un po' anche io!
  • Re: Esame Di Programmazione

    Sisi, é la definizione formale che va considerata.
  • Re: Esame Di Programmazione

    Nippolo ha scritto:


    HATFIELD ha scritto:


    ma l'esercizio dice NxM
    In realtà dice NxN, mentre M è il nome della matrice!

    SonoUnaMatematica ha scritto:


    ecco, io avevo interpretato "sottomatrice" in modo diverso.
    ...
    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!
    In realtà è più complicato basarsi sulla mia definizione (in quanto contempla un maggior numero di casi) che sulla tua interpretazione.
    Ad ogni modo per proseguire bisogna innanzitutto stabilire la definizione di sottomatrice che si vuole abbracciare.
    Se cerchi su internet una definizione formale troverai quella da me riportata nel precedente post, ossia "matrice ricavata dalla matrice completa rimuovendo alcune righe e/o colonne". In pratica la suddetta definizione consente di avere sottomatrici formate da righe/colonne non consecutive (consecutive nella matrice completa intendo), mentre la tua interpretazione no.
    Quindi in definitiva su quale delle due interpretazioni vuoi costruire l'algoritmo? Magari vale la pena chiedere al prof per fugare ogni dubbio?!

    SonoUnaMatematica ha scritto:


    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ò
    In effetti non si tratta di un problema proprio semplicissimo, in ogni caso una volta chiarito cosa si intende per sottomatrice, proverò a ragionarci un po' anche io!
    Io credo che l'algoritmo per determinare tutte le sottomatrici secondo la definizione canonica sia complicato , probabilmente ne esiste uno specifico che si insegna nella teoria del corso.

    In realtà è più complicato basarsi sulla mia definizione (in quanto contempla un maggior numero di casi) che sulla tua interpretazione.
    [/b]Infatti e' proprio cosi' e internet e' piena di quesiti da parte di studenti che chiedono aiuto su questo tipo di problema: determinare tutti i minori di una matrice.Secondo me e' un problema compesso , ma potrebbe esistere gia' un algoritmo noto che lo risolve.
    Gia' trovare tutte le combinazioni possibili di righe/colonne che possono essere eliminate non e' un problema banale.
  • Re: Esame Di Programmazione

    HATFIELD ha scritto:


    [/b]Infatti e' proprio cosi' e internet e' piena di quesiti da parte di studenti che chiedono aiuto su questo tipo di problema: determinare tutti i minori di una matrice.Secondo me e' un problema compesso , ma potrebbe esistere gia' un algoritmo noto che lo risolve.
    Gia' trovare tutte le combinazioni possibili di righe/colonne che possono essere eliminate non e' un problema banale.
    [/quote]

    Purtroppo durante il corso non abbiamo fatto niente del genere. Ed il rpofessore ha assegnato questo esercizio in una prova d'esame precedente.

    (scusate ancora non ho capito come si citano i messaggi )
  • Re: Esame Di Programmazione

    Purtroppo durante il corso non abbiamo fatto niente del genere. Ed il rpofessore ha assegnato questo esercizio in una prova d'esame precedente.
    Sicuro che non si riferisse ai "minori principali" ?
    Quelli sono piu' facili da determinare, trovare tutti i minori non mi sembra un esercizio sensato.
    Infatti in tutti gli esempi che si trovano su internet le matrici sono 3x3 perche' in quel caso e' facile trovare i mirori di ordine 2, dato che si devono sempre togliere 1 riga ed una colonna.
    https://www.andreaminini.org/matematica/algebra-lineare/minore-della-matrice
    Gia' con quattro la cosa esplode in complessita' perche' si possono togliere sia una linea ed una colonna alla volta, sia due linee e due colonne alla volta.
    MATHLAB non include una funzione integrata in grado di catturare il minore di una matrice,
    E' strano, se e' davvero cosi', si pretende da uno studente di realizzare una cosa che non c'e' in una libreria specializzata.
    Pero' mathlab riesce a calcolare il rango della matrice, quindi o determina i minori (ma a quanto pare non ce li fa conoscere) o segue un'altra strada.Sicuramente quelli della sezione Mathlab ne sanno di piu'.
  • Re: Esame Di Programmazione

    Tu dici:

    Gia' trovare tutte le combinazioni possibili di righe/colonne che possono essere eliminate non e' un problema banale.

    Invece lo è

    Basta elimiminare, volta per volta, una colonna e una riga, creare la sottomatrice e passarla per ricorsione
    Rimettere una colonna e togliere la successiva
    All'ultima colonna rimettere la prima e togliere la riga successiva

    Per una matrice HxH richiede appunto H per H chiamate ricorsiva

    Ma qui viene il bello:
    Se si trova una sottomatrice tutta negativa si può abortire direttamente quel ramo di sottomatrici

    E una volta trovata una sottomatrice di grandezza N si possono abortire tutti i restanti rami di pari dimensione
  • Re: Esame Di Programmazione

    StandardOil ha scritto:


    Tu dici:
    Gia' trovare tutte le combinazioni possibili di righe/colonne che possono essere eliminate non e' un problema banale.
    Invece lo è
    Basta elimiminare, volta per volta, una colonna e una riga, creare la sottomatrice e passarla per ricorsione
    Rimettere una colonna e togliere la successiva
    All'ultima colonna rimettere la prima e togliere la riga successiva
    Per una matrice HxH richiede appunto H per H chiamate ricorsiva
    Ma qui viene il bello:
    Se si trova una sottomarine tutta negativa si può abortire direttamente quel ramo di sottomatrici
    E una volta trovata una sottomatrice di grandezza N si possono abortire tutti i restanti rami di pari dimensione
    Basta elimiminare, volta per volta, una colonna e una riga, creare la sottomatrice e passarla per ricorsione
    Rimettere una colonna e togliere la successiva
    All'ultima colonna rimettere la prima e togliere la riga successiva
    Per una matrice HxH richiede appunto H per H chiamate ricorsiva
    [/b]E' banale una volta che si conosce l'algoritmo,pero' non capisco una cosa: ammettiamo una matrice 4x4, secondo il tuo ragionamento sono 16 chiamate ricorsive, se ognuna di queste genera un solo minore, il conto non mi tornerebbe perche' i minori di una matrice di ordine 4 sono piu' di sedici.
    O sono proprio 16 ?
    Non sono abituato a ragionare per ricorsione.
    Se la soluzione e' ricorsiva, e' chiaro allora che l'esercizio richiede quello e sonounadimatematica aveva subodorato l'inghippo.
    Anche la disposizione di N elementi su N posti senza ripetizione credo di possa risolvere per ricorsione, ma con N=10 non si ottiene uno stack overflow (almeno in C) ?
  • Re: Esame Di Programmazione

    Volendo c'è una soluzione con un tempo computazionale osceno
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <math.h>
    
    #define MAX 5
    
    int count(int n){
        int c = 0;
        while(n > 0){
            if(n & 1)
                c++;
            n >>= 1;    
        }
        return c;
    }
    
    int main(){
        int M[MAX][MAX], i, j, k, l, bits, order, non_negative, solution = 0, sol_k = 0, sol_l = 0;
        
        srand(time(NULL));
        for(i = 0; i < MAX; i++){
            for(j = 0; j < MAX; j++)
                printf("%2d ", M[i][j] = rand() % 11 - 5);
            printf("\n");
        }
        
        bits = (int)pow(2, MAX);
        for(k = 0; k < bits; k++)
            for(l = 0; l < bits; l++){
                order = count(k);
                if(order == count(l)){
                    non_negative = 0;
                    for(i = 0; i < MAX; i++)
                        for(j = 0; j < MAX; j++)
                            if(k & 1 << i  &&  l & 1 << j)
                                if(M[i][j] >= 0)
                                    non_negative = 1;
                    if(!non_negative && order > solution){
                        solution = order;
                        sol_k = k;
                        sol_l = l;
                    }
                }
            }    
        
        printf("\nSolution = %2d\n", solution);
        for(i = k = 0; i < MAX; i++)
            for(j = 0; j < MAX; j++)
                if(sol_k & 1 << i  &&  sol_l & 1 << j){       
                    printf("%2d ", M[i][j]);
                    if(++k >= solution){
                        printf("\n");
                        k = 0;
                    }
                }    
                
        return 0;
    }
    
  • Re: Esame Di Programmazione

    A quest'ora non comincio nemmeno a leggere il programma

    Sono troppo stanco
  • Re: Esame Di Programmazione

    Cito:

    O sono proprio 16 ?

    No, saranno di più
    Ma io trovo i 16 3x3
    Lascio che la ricorsione trovi per ognuno di questi i
    9 di dimensione 2
  • Re: Esame Di Programmazione

    La difficoltà sta nel tenere traccia delle colonne e righe già bloccate quando si scende nella ricorsione.
Devi accedere o registrarti per scrivere nel forum
23 risposte