[C] Ricerca percorso all'interno di una matrice di interi

**xglobusx** · 10-06-2007, 17:41

Il problema consiste nel cercare all'interno di una matrice di interi già definita un percorso che partendo casella di posizione [0][0] raggiunga la casella di posizione [n][n]. La somma dei valori contenuti nelle caselle deve essere per es 250.

Qualcuno ha voglia di guardare la soluzione? C'è un errore nell'uso delle matrici.. e poi non so se funziona la procedura ricorsiva che ho scritto. Grazie

codice:

#include <stdio.h>



int v[100]={0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0};

int k=0;
int nr=8, nc=8;
int somma=0;

int inCastello( int M[][], int nr, int nc, int r, int c );

int main(void){

    int M[8][8]={{1,17,1,5,41,6,75,54},
                  {12,65,1,15,7,4,45,12},
                  {9,23,1,45,41,12,75,43},
                  {32,2,87,4,7,8,37,53},
                  {23,37,6,76,21,38,52,36},
                  {9,5,1,13,23,19,12,7},
                  {21,25,34,65,1,45,29,35},
                  {41,9,5,12,35,12,17,2}};
    int i, j;
                   
    for(i=0; i<8; i++){
        for(j=0; j<8; j++){
            printf("%5d ", M[i][j]);
        }         
        printf("\n");
    }
    
    if(percorri(M, nr, nc, 0, 0)){
        printf("Uscita trovata\n");               
    }
    
    //Stampare v
    
    system("pause");
}

int inCastello( int M[][], int nr, int nc, int r, int c ) {
  return ( 0 <= r && r < nr && 0 <= c && c < nc );
}

int percorri(int M[][], int nr, int nc, int r, int c){
    
   int uscita=0;
   
        if(inCastello(M,nr,nc,r,c)){
            somma=somma+M[r][c];
            if(somma==250 && r==nr && c==nc){
                uscita=1;
            }
            else if(somma<250){
                v[k]=M[r][c];
                k++;
                if(   percorri(M,nr,nc,r+1,c) 
                   || percorri(M,nr,nc,r-1,c) 
                   || percorri(M,nr,nc,r,c+1) 
                   || percorri(M,nr,nc,r,c-1))
                {
                    uscita=1;
                }
                   
            }
            else{
                 v[k]=0;
                 k--;
            }
        }
        else{
             v[k]=0;
             k--;
        }
    return uscita;
}

**andbin** · 10-06-2007, 18:29

Originariamente inviato da xglobusx
C'è un errore nell'uso delle matrici..

Sì, c'è un errore di fondo: il parametro di una funzione non lo puoi dichiarare int M[][]. La seconda dimensione deve sempre essere specificata, la prima dimensione invece è opzionale (se sai come sono organizzati gli array bidimensionali e come il compilatore "traduce" l'espressione m[i][j], capisci anche il perché).

Quindi visto che nel main l'array è dichiarato di 8 x 8, il parametro della funzione lo puoi dichiarare come:

A) int M[][8]
B) int M[8][8]
C) int (*M)[8]

Quest'ultima pur essendo equivalente alle altre due, non è molto comprensibile, quindi sconsigliata.

Se invece ti interessa poter passare ad una funzione una matrice bidimensionale di dimensione "arbitraria", allora è un'altra cosa e tra l'altro se ne è già parlato sul forum.

**xglobusx** · 10-06-2007, 18:59

grazie ora non da errori, ma la funzione ricorsiva non funziona.

**andbin** · 10-06-2007, 19:12

Originariamente inviato da xglobusx
la funzione ricorsiva non funziona.

Vorrei capire meglio ..... tu devi cercare in questa matrice un percorso (il primo che trovi, immagino) tale per cui la somma dei valori sia 250???
Ma il percorso come può essere? In qualunque direzione muovendosi solo per celle adiacenti?

**xglobusx** · 10-06-2007, 19:57

si è vero non ho spiegato tutto.
va bene qualsiasi percorso (uno solo se ne sono 2 o più), si può passare più volte sulla stessa casella e ci si può muovere in tutte le direzioni, ma non in diagonale.
la somma deve fare 250 e tale percorso esiste sicuramente, almeno uno.

**andbin** · 11-06-2007, 10:59

Originariamente inviato da xglobusx
si è vero non ho spiegato tutto.
va bene qualsiasi percorso (uno solo se ne sono 2 o più), si può passare più volte sulla stessa casella e ci si può muovere in tutte le direzioni, ma non in diagonale.
la somma deve fare 250 e tale percorso esiste sicuramente, almeno uno.

Ok, allora innanzitutto io sono riuscito a scrivere la funzione (ed è più semplice e lineare della tua) ... naturalmente non la posto per ovvi motivi ...

Vediamo però di fare alcune considerazioni: questo è un classico problema di ricerca in "profondità". Che si risolve molto bene appunto con una funzione ricorsiva.

Senza avere altre specifiche più precise legate alla ottimizzazione della ricerca come ad esempio "cercare il percorso più breve" oppure "cercare il percorso per cui non si ripassa sulla stessa casella" o altre specifiche del genere, si rischia di ottenere la soluzione più "stupida" e banale. Quella più "grezza" cioè.

Spiego meglio: la funzione deve essere tale per cui se con la somma del valore della cella referenziata in quel momento non si raggiunge 250, allora bisogna "provare" con altre celle.
Ora, escludendo come hai detto i movimenti in diagonale, risulta che da una cella puoi muoverti in 4 direzioni, con la eccezione di bordi e angoli, per cui rispettivamente si possono avere solo 3 o 2 movimenti.

Ora ... le chiamate in modo ricorsivo per provare altre celle le si dovrà fare in un certo ordine, no? Immaginiamo ad esempio:

codice:

if (posso_andare_a_destra) { func (..... r, c+1, ...); }
if (posso_andare_in_basso) { func (..... r+1, c, ...); }
if (posso_andare_a_sinistra) { func (..... r, c-1, ...); }
if (posso_andare_in_alto) { func (..... r-1, c, ...); }

Cosa succede con una cosa del genere? Che partendo da (0,0) il primo path sarà sempre quello di andare a destra ... finché o si è raggiunta la colonna più a destra o la somma calcolata più in profondità va oltre 250 e quindi si "torna indietro" cercando altre strade.

Nella mia funzione ho voluto far stampare il path che ha avuto successo. Essendo in ricorsione, la prima cella stampata è l'ultima trovata:

codice:

[0][5] = 6    (sum=250)
[1][5] = 4    (sum=244)
[1][6] = 45   (sum=240)
[1][5] = 4    (sum=195)
[1][6] = 45   (sum=191)
[0][6] = 75   (sum=146)
[0][5] = 6    (sum=71)
[0][4] = 41   (sum=65)
[0][3] = 5    (sum=24)
[0][2] = 1    (sum=19)
[0][1] = 17   (sum=18)
[0][0] = 1    (sum=1)

Cosa noti? che la funzione ha fatto la cosa più stupida, ovvero partendo da [0][0] è andato sempre verso destra. L'ultimo valore nell'angolo [0][7] (54) non l'ha preso perché più in profondità deve aver superato 250. Quindi è andato sulla riga sotto e si è messo a "ballare" tra la cella [1][5] e [1][6]. Arrivato prossimo a 250, la prima cella che ha trovato che forniva il totale di 250 è stata la cella [0][5].

Questo è successo in sostanza perché non sono stati inseriti criteri di ottimizzazione e perché la visita nelle altre celle adiacenti è "pilotata" con una sequenza precisa nel codice.

**xglobusx** · 11-06-2007, 18:24

grazie per l'aiuto

ho provato una soluzione simile alla tua, ma non funziona bene, sempre meglio della prima

Il percorso però deve andare dalla casella [0][0] a [n][n] cioè dalla prima casella in alto a sinistra all'ultima in alto a destra.

ho scritto questa funz, ma

codice:

int percorri(int M[8][8], int nr, int nc, int r, int c){
    
    somma=somma+M[r][c];
    if(somma==250 && r==8 && c==8){
        printf("%d", M[r][c]);
        return 1;
    }
    else if(somma < 250){
        if(c<7)
            if(percorri(M,nr,nc,r,c+1)==1){
                printf("casella %d, somma %d\n", M[r][c], somma);
                return 1;
            }else{
                  somma=somma-M[r][c+1];
            }
        if(r<7)
            if(percorri(M,nr,nc,r+1,c)==1){
                printf("casella %d, somma %d\n", M[r][c], somma);
                return 1;
            }else{
                  somma=somma-M[r+1][c];
            }
        if(c>0)
            if(percorri(M,nr,nc,r,c-1)==1){
                printf("casella %d, somma %d\n", M[r][c], somma);
                return 1;
            }else{
                  somma=somma-M[r][c-1];
            }
        if(r>0)
            if(percorri(M,nr,nc,r-1,c)==1){
                printf("casella %d, somma %d\n", M[r][c], somma);
                return 1;                               
            }else{
                  somma=somma-M[r-1][c];
            }
    }  
}

non so se sbaglio la posizioni dei controlli..
la mia mente ha difficoltà a ragionare ricorsivamente la ricorsione.

**andbin** · 11-06-2007, 21:00

Originariamente inviato da xglobusx
grazie per l'aiuto

Prego ... faccio quello che posso.

Originariamente inviato da xglobusx
ho provato una soluzione simile alla tua, ma non funziona bene, sempre meglio della prima

Il percorso però deve andare dalla casella [0][0] a [n][n] cioè dalla prima casella in alto a sinistra all'ultima in alto a destra.

ho scritto questa funz, ma

Intanto è ancora molto più complessa rispetto alla mia (e comunque la mia funzione non ha la pretesa di essere perfetta).

Poi nella tua ci sono degli errorini. Innanzitutto gli indici vanno da 0 a 7, quindi non ha senso comparare r==8 e c==8. Poi se noti, la funzione non ritorna nulla se sum supera 250.

**xglobusx** · 11-06-2007, 23:16

La sequenza di operazioni

-aggiungo alla somma il valore M[r][c]

-controllo se la somma è 250 e sono nella posizione M[7][7] ritorno 1

-se la somma è inferiore a 250 provo dx, sotto, sx, sopra

-se la somma è superiore a 250 non so cosa fare.. faccio somma=somma-M[r][c] e ritorno -1?

è giusta?

**xglobusx** · 11-06-2007, 23:55

per esempio in questo modo, ritorna una sequenza di spostamenti, ad un certo punto si interrompe, ma non con un percorso corretto.

codice:

int percorri(int M[8][8],int r, int c){
    
    somma=somma+M[r][c];
    if(somma==250 && r==7 && c==7){
        printf("%d", M[r][c]);
        printf(" somma %d", somma);
        return 1;
    }
    else if(somma < 250){
        if(c<7){
            if(percorri(M, r,(c+1))==0){
                somma=somma-M[r][c+1];
            }else{
                  printf("\n%d", M[r][c+1]);
                  printf(" somma %d", somma);
                  return 1;      
            }
        }
        if(r<7){
            if(percorri(M,(r+1),c)==0){
                somma=somma-M[r+1][c];
            }else{
                  printf("\n%d", M[r+1][c]);
                  printf(" somma %d", somma);
                  return 1;      
            }
        }
        if(c>0){
            if(percorri(M, r,(c-1))==0){
                somma=somma-M[r][c-1];
            }else{
                  printf("\n%d", M[r][c-1]);
                  printf(" somma %d", somma);
                  return 1;      
            }
        }
        if(r>0){
            if(percorri(M,(r-1),c)==0){
                somma=somma-M[r-1][c];                              
            }else{
                  printf("\n%d", M[r-1][c]);
                  printf(" somma %d", somma);
                  return 1;      
            }
        }
    }
    else if(somma>250){
         somma=somma-M[r][c];
         return 0;     
    }  
}

fra l'altro in output la somma è sempre 151

Discussione: [C] Ricerca percorso all'interno di una matrice di interi

Strumenti discussione

Ricerca discussione

Visualizza

[C]problema ricorsione e matrici

Re: [C]problema ricorsione e matrici

Permessi di invio