Re: [C] Ultimo Homework

[dan952]

Ironia della sorte gli esercizi di questa ultima scheda hanno a che fare con l'es. 3 della scheda precedente.
Ho provato a fare il primo ieri sera:

// a è la matrice simmetrica di relazione 
// b la matrice inizializzata alla matrice nulla 
int Cam(int **a, int **b, int n, int nodo, int cont){
for (i=1;i<n;i++){ 
        for (j=0;j<cont;j++){
              if (b[i][j]!=1) k++; // controllo se il cammino è stato già percorso
        if (k==cont && a[nodo][i]==1){
                  b[nodo][i]=1;  //registro i cammini percorsi
                  b[i][nodo]=1;
                  if  (Cam(a,b,n,i,cont+1)==1 || cont==n) return 1; \\parte incerta anche perché non so se la matrice b viene modificata quando richiamo la funzione.
                  else return 0;
          }
}
return 0;

[vict85]

Non aprire due discussioni uguali.

Ti potrebbe convenire provare a rifare l'ultimo esercizio della settimana precedente. Infatti in quel caso basta vedere se il valore in quella matrice è diverso da \(\displaystyle -1 \).

Sinceramente, al contrario del tuo professore, non utilizzerei una funzione ricorsiva e trovo che che la funzione soluzione debba ricevere in input la sola matrice (con la dimensione[nota]Un migliore organizzazione del codice richiederebbe di inglobare puntatore e dimensione in un unica struttura (ed eventualmente altri dati).[/nota]) o, se si vuole fare una funzione più generica, la matrice e i due nodi. Il vettore che controlla le visite (ed eventualmente altri fattori) dovrebbe essere creato e distrutto direttamente all'interno della funzione di ricerca perché è logicamente una sua variabile locale.

[dan952]

Questo topic mi si è aperto modificando il primo...

Ora provo a farlo senza usare l'esercizio 3, seguendo il tuo secondo consiglio.

[dan952]

La "strada" ricorsiva potrebbe però aiutare, comincio dal nodo 0 supponiamo esista un certo $i$ tale che $a[0]=1$ modifico la variabile $nodo=i$ ecc... il problema è che in generale potrebbe non esistere un solo $i$ tale che $a[0]=1$ e ognuno di questi descriverà in generale un cammino diverso, con la ricorsività posso controllare ognuno di questi con un solo ciclo.

[vict85]

Come va il tentativo di risoluzione?

La versione non ricorsiva risulta una variante dell'esercizio 3 del compito precedente. La versione ricorsiva procede in questo modo (il codice è in simil-python e suppone che Visitato sia stato già definito):

def Func(start, end, Visitato) :
    Visitato[start] = True
    if end in start.connections :
        return True
    for N in start.connections :
        if Visitato[N]:
            continue
        b = Func(N, end, Visitato)
        if b :
            return True
    return False

Siccome Visitato va definito ti conviene definire due funzioni. La prima che inizia il processo e lo conclude (eliminando la memoria dinamica di Visitato) e l'altro che naviga il grafo. Ovviamente la funzione C sarà differente in vari aspetti (per esempio la tua funzione sostituirà il start ed end con il grafo + i due indici), ma questa è l'idea generale. Il comando continue, che esiste anche in C, dichiara che tu vuoi saltare il resto del ciclo e rifarlo partire dall'inizio con il prossimo elemento.

[dan952]

Scusa ti rispondo adesso perché non ero più entrato nella sezione. Ho provato a fare i primi due, il terzo sono indeciso se farlo perché tanto avendo fatto bene tutti quelli passati [nota]Il 3 della scheda precedente ha dato solo un errore su 5 prove mi pare, che c***o![/nota] più uno di prova quindi di punti bonus all'esame ce ne ho abbastanza.
Posto i primi due:

int Cam(int **a, int **b, int n, int nodo){
    int i;
    
    if (a[nodo][n-1]==1) return 1;
          
    for (i=0;i<n-1;i++){
        if (b[nodo][i]!=1 && a[nodo][i]==1){
            b[nodo][i]=1;
            b[i][nodo]=1;
            
            if (Cam(a,b,n,i)==1)
                return 1;
            else return 0;
            
        }
     }
     return 0;
   
}

int Cam(int **a, int **b, int n, int nodo){
    int i;
    if (a[nodo][0]==1 && b[nodo][0]!=1) return 1;
           
    for (i=0;i<n-1;i++){
        if (b[nodo][i]!=1 && a[nodo][i]==1){
            b[nodo][i]=1;
            b[i][nodo]=1;
            if (Cam(a,b,n,i)==1)     
                 return 1;
            else return 0;
        }
     }
     return 0;
   
}