Visualizzazione dei risultati da 1 a 4 su 4

Discussione: [C]ricorsione

  1. #1

    [C]ricorsione

    Salve a tutti,

    Ultimamente ho provato a cimentarmi nella risoluzione di un esercizio sulla ricorsioneche riporto di seguito:



    In un file è codificata una scacchiera sotto forma di matrice di caratteri NxM in cui il carattere ‘*’ rappresenta una barriera invalicabile mentre il carattere ‘#’ una pedina. Scrivere un programma C che determini se esiste almeno un cammino che permette alla pedina di raggiunge la cima della matrice:
    La pedina si può muovere in qualunque posizione adiacente alla sua posizione attuale (8 possibili mosse)
    123
    4#5
    678
    Esempio di configurazione:
    0000000000
    0****00000
    **00*00000
    0000**0000
    00000**000
    000000*000
    000000**00
    00#00000**
    000000000*
    0000000000
    in questo caso esiste almeno 1 percorso che permette alla pedina di raggiungere la cima della scacchiera.
    Altro esempio:
    0000000000
    0****00000
    **00*00000
    0000**0000
    00000**000
    000000*000
    000000***0
    00#00000**
    000000000*
    0000000000
    In questo caso non esiste nemmeno 1 percorso che permette alla pedina di raggiungere la cima della scacchiera.
    Parte II
    Si modifichi il programma in modo che restituisca la lunghezza del percorso più breve che permette alla pedina di raggiungere la cima della scacchiera. Eventualmente, si stampi la sequenza di coordinate che identifica tale percorso.


    Non ho avuto alcun genere di problema nella risoluzione della prima parte,in cui ho usato una funzione ricorsiva in cui ho imposto al mio codice C di visitare la prima casella a '0' a partire da '#',mediante un ciclo for da -1 a 1,contrassegnare la casella visitata e ripetere(in modo ricorsivo) l'operazione a partire dalla nuova casella sino alla prima riga della matrice,in tal caso...printf("è stato trovato un percoso");
    Quella che invece mi sta creando un significativo numero di è la seconda parte.
    Qualcuno saprebbe propormi una soluzione??
    è necessario usare uno Stack per l'aggiornamento delle lunghezze n dei percorsi?

    Di seguito il codice relativo al programma svolto:

    codice:
    int visita(char** matr,int x, int y, int row, int col);
    
    
    
    int main()
    {
    
        char** matr=NULL;
        FILE* fp=NULL;
        char str[MAX];
        int res;
        int col=0, row=0;
        int i=0, j;
         STACK s=NULL;
        int num_mosse = 0;
    
        s = STACK_init();
    
        fp=fopen("matrice#.txt","r");
    
        if(fgets(str,MAX,fp)==NULL) return -1;
        col = strlen(str);
        col--;
        do{
            matr = (char**) realloc(matr, (row+1)*sizeof(char*));
            matr[row]=(char*) calloc(col, sizeof(char));
            for(j=0;j<col;j++)
                matr[row][j]=str[j];
            row++;
        }while(fgets(str,MAX,fp)!=NULL);
    
        printf("\nla matrice ha questo contenuto");
        for(i=0; i<row ; i++){
            printf("\n");
            for(j=0; j<col ;j++){
                printf("%c",matr[i][j]);
            }
        }
    
    
        for(i=0;i<row;i++){
    
              for(j=0;j<col;j++){
    
    
            if(matr[i][j]=='#'){
                printf("\npunto di partenza: %d-%d ", i,j);
                res = visita(matr,i,j,row,col);
    
                if(res==1){
    
                   printf("\n ho trovato un percorso");
                   break;
                }else{
    
        if (res==0) printf("\n non ho trovato un percorso");
                    break;
        }
              }
        }
        }
    
    
        for(i=0;i<row;i++){
    
            printf("\n");
    
              for(j=0;j<col;j++){
    
                  printf("%c",matr[i][j]);
    
                  if(matr[i][j]=='1')
    
                    matr[i][j]='0';
    
    
              }
        }
    
        for(i=0;i<row;i++){
    
              for(j=0;j<col;j++){
    
    
                   if(matr[i][j]=='#'){
                      res=visita_2( matr,i,j,row,col,s);
                      if(res ==1){
                      STACK_pop(s,&num_mosse);
                      printf("%d",num_mosse);
                      }
    
                   }
              }
        }
    
    
    
    
    
    
    
    
    
        return 0;
    }
    
    
    
    
    
    
    int visita(char** matr,int x, int y, int row, int col){
        int i = 0;
        int j = 0;
        int res;
    
    
    
        if(x==0) return 1;
    
    
        for(i=-1 ; i<=1 ; i++){
            for(j=-1 ; j<=1 ; j++){
    
            if(((x+i)<row && (x+i)>=0) && matr[x+i][y+j]=='0'){
    
                matr[x+i][y+j]='1';
                res = visita(matr,x+i, y+j, row, col);
                  if (res==1)
                   return 1;
    
        }
            }
        }
    
    
    
        return 0;
    }
    In attesa di avere risposte,
    Saluti a tutti

  2. #2
    Moderatore di Programmazione L'avatar di LeleFT
    Registrato dal
    Jun 2003
    Messaggi
    17,303

    Moderazione

    Il codice va postato all'interno degli appositi tag CODE, come richiesto dal regolamento interno, in modo da mantenerne la formattazione che lo rende leggibile.

    Ho corretto io.

    Inoltre, non è ammessa la richiesta di soluzioni a esercizi o codice completo: prova tu a svolgere l'esercizio e posta gli errori che ottieni o le parti di codice dove hai dei dubbi.

    Ciao.
    "Perchè spendere anche solo 5 dollari per un S.O., quando posso averne uno gratis e spendere quei 5 dollari per 5 bottiglie di birra?" [Jon "maddog" Hall]
    Fatti non foste a viver come bruti, ma per seguir virtute e canoscenza

  3. #3
    codice:
    int visita_2(char** matr,int x, int y, int row, int col,STACK pt){ 
     int i,j;
     int res;
     int *n = NULL;     
     if(x==0){           
    STACK_push(pt,n);       
    for(i=0;i<row;i++){           
     for(j=0;j<col;j++){                 
     if(matr[i][j]=='#'){                    
    x = i;                   
     y = j;                     
     res=visita_2(matr,x,y,row,col,pt);        
     return 1;               
     }           
    }      
     }     
     }                     
    for(i=-1;i<=1;i++){                        
    for(j=-1;j<=1;j++){                             
    if(matr[x+i][y+j] == '0'){                                
     matr[x+i][y+j] = '1';                               
     (*n)++;                               
     res=visita_2(matr,x+i,y+j,row,col,pt);                            
       }                      
     }                    
    }    
     return 0; }
    Questo è il frammento di codice relativo alla seconda parte di esercizio che "dovrebbe" selezionarmi il percorso più breve per raggiungere la prima riga della matrice.
    L'errore che mi da è di segmentation fault dopo lo svolgimento della prima parte,nonchè la visualizzazione del percorso trovato,mentre non viene visualizzato alcun errore sul piano sintattico(0 errors 0 warnings).
    Nella istruzione banale if(X==0),cioè se sei giunto alla prima riga inserisci in uno STACK il valore di n che hai calcolato nella ricorsione(sarebbe (*n++)).L'idea è stata inserisci in Stack E FAI RIPARTIRE L'OPERAZIONE DI VISITA,ma è evidente che c'è qualche istruzione che non permette di interpretare il codice adeguatamente,ho pensato ad un problema di strutturazione della mia funzione ma senza trovare l'errore,qualcuno saprebbe darmi una spiegazione al segmentation fault??dove sta l'errore?
    Grazie a tutti.

  4. #4
    Utente bannato
    Registrato dal
    Oct 2010
    Messaggi
    1,219
    A occhio e senza pensarci molto la porzione di codice "incriminata" è questa:
    codice:
    int visita_2(char** matr,int x, int y, int row, int col,STACK pt){ 
     int i,j;
     int res;
     int *n = NULL;     
     if(x==0){           
    STACK_push(pt,n);       
    for(i=0;i<row;i++){           
       for(j=0;j<col;j++){                 
             if(matr[i][j]=='#'){                    
             x = i;                   
             y = j;                     
            res=visita_2(matr,x,y,row,col,pt);        
            return 1;
    Questi due cicli:
    codice:
    for(i=0;i<row;i++){           
       for(j=0;j<col;j++)
    Vengono eseguiti rispettivamente row volte e col volte, ma row e col sono due valori "costanti" nel senso che non vengono mai decrementati.
    Il problema sta nel fatto che :
    1. Se col e row sono positive i due cicli iniziano sempre;
    2.La chiamata ricorsiva avviene sempre e non c'è possibilità di interrompere il ciclo di chiamate ricorsive.

    Se col e row sono entrambe maggiori di zeri, esegui il ciclo finchè non arrivi a questa parte di codice:
    codice:
    res=visita_2(matr,x,y,row,col,pt);        
            return 1;
    A questo punto chiami di nuovo la funzione visita_2, ma non ritorni alcun valore finchè la funzione visita_2 non è terminata.
    La funzione visita_2 che hai chiamato ricorsivamente anch' essa non termina finchè non finisce la funzone visita_2 che a sua volta ha chiamato.E così via fino all' infinito.
    E lo stack si riempie di variabile usate per contenere i valori di ritorno delle funzioni ricorsive, finchè non diventa così grande da causare il segmentation fault.

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.