[C] Esercizio 3

[dan952]

Purtroppo non mi viene un'idea ho provato ricorsivamente richiamando la funzione d(i,j,..) distanza, tipo:

int d(i,j,n){
             % dichiaro variabili
      for (m=2;m<n+1;m++){
            for (k=?;k<n;k++){
                 
                 if (b[i][k]==1 && d(i,j,n)==m){ true=1;}
                     if (b[i][k]==1){
                        cont_1=cont_1+1;
                        if (d(i,j,n)>=m){
                            cont_2=cont_2+1;
                        }
                    }
                    
           }
                if (cont_1==cont_2 && true==1){
            
            
                    return m;
                    break;
                }
          }
         return -1;
    
    
}

[dan952]

Vict avevi dato un suggerimento ma non ho ben capito.

[vict85]

Si, ma in realtà è meno efficiente del metodo diretto, ma utilizzava la composizione. Aveva una complessità di \(O(n^4)\). Ho implementato entrambe le versioni quindi più tardi magari ti mostro del codice.

Il principio è quello di procedere iterativamente. Ad ogni ciclo calcoli i percorsi fino ad una certa lunghezza. Nota che il percorso minimo non passa due volte dallo stesso punto. Nota che siccome ad ogni passaggio la distanza massima raddoppia sono sufficienti \(log n\) iterazioni. Nota che ogni aggiornamento ha una complessità di \(O(n^3)\) e che puoi aggiornare sulla stessa matrice.

[dan952]

Niente Vict...la complessità non importa basta che funzioni, intanto ho modificato l'es.2 e ne approfitto postando l'es. 1 per un tuo controllo:
Es.1

void ContrMatrix(int **a, int n){ 	
    int i,j,k; 	
     	 	
    for(i=0; i<n; i++){ 		
        for(j=0; j<n; j++){
            
            for (k=0;k<n;k++){
                if (a[i][j]==1 && a[j][k]==1){
                    if (a[i][k]==0){
                        printf("\n");
                        printf("0");
                        return;
                    }
                }
             }
            
        }
     } 
    	printf("1");
    return;
}

Es.2 modificato

int **CompMatrix(int **a, int n){ 	
    int **b,i,j,k; 	
    b=AllocMatrix(n, n); 	 	
    for(i=0; i<n; i++){ 		
        for(j=0; j<n; j++){
            b[i][j]=0;
            for (k=0;k<n;k++){
                if (a[i][k]==1 && a[k][j]==1){
                    b[i][j]=1;
                    break;
                }
             }
            
        }
     } 
    	return b; 
} 

[apatriarca]

@dan95: sarebbe stato meglio se avessi postato questa discussione in coda all'altra o avessi postato nuovamente il pdf del tuo professore con gli esercizi. Per chi non avesse letto l'altra discussione il link è il seguente: http://twiki.di.uniroma1.it/pub/Info_gen/Homework/2016-homework2.pdf.

L'idea della soluzione è la seguente:
1. Inizializzi la matrice in modo da avere \(0\) sulla diagonale principale, \(1\) dove era già presente un uno nella matrice della relazione e \(-1\) dove era invece presente uno zero.
2. Iteri quindi su tutti i valori della matrice. Per ogni valore positivo nella posizione \((i,j)\), se \((i,k)\) è uguale a \(-1\) o maggiore della somma dei valori in \((i,j)\) e \((j,k)\), aggiorni questo valore uguale a quella somma. Conti il numero di modifiche fatte alla matrice.
3. Se non ci sono state modifiche alla matrice hai la soluzione finale, in caso contrario torni al punto 2.

[dan952]

Non funziona, cosa sbaglio?

int **dist(int **a, int n){
    int i,j,k,**d,cont;
    
    d=AllocMatrix(n);
    
    for (k=1;k<n;k++){
        
        for (i=0;i<n;i++){
            for (j=0;j<n;j++){
                if (i==j) d[i][j]=0;
                else if (a[i][j]==1) d[i][j]=1;
                else d[i][j]=-1;
                
            }
        }
        
        
        
    }
    for (i=0;i<n;i++){
        for(j=0;j<n;j++){
            cont=0;
            
            if (d[i][j]>0){
                
                for (k=0;k<n;k++){
                    if (d[i][k]==-1 || d[i][k]>d[i][j]+d[j][k]){
                        d[i][k]=d[i][j]+d[j][k];
                        
                        cont=cont+1;
                    }
                }
               if (cont==0) return d;
            }
        }
    }
    
}

[kobeilprofeta]

@dan
[ot]Scusa l'ot...
che università/corso stai frequentando?[/ot]

[dan952]

@kobe
Sapienza/ matematica (di certo non informatica)

[apatriarca]

Ero convinto di averti risposto.. Perché inizializzi \(n\) volte la matrice? I punti 2 e 3 sono poi completamente sbagliati. cont va definito e verificato al di fuori dell'iterazione sulla matrice e devi iterare sulla matrice più volte..

[dan952]

Il fatto di aver iterato n volte la matrice è stata una svista, comunque credo di non aver capito ancora.
Inizializzo la matrice come prima (levando il ciclo in k frutto della svista), provo a mettere quello che ho fatto:

cont=1;
    while (cont!=0){
    cont=0;
    for (i=0;i<n;i++){
        for(j=0;j<n;j++){
            
            
            if (d[i][j]>0){
                
                for (k=0;k<n;k++){
                    if (d[i][k]==-1 || d[i][k]>d[i][j]+d[j][k]){
                        d[i][k]=d[i][j]+d[j][k];
                        
                        cont=cont++;
                    }
                }
               
            }
        }
    }
    }
    return d;
}

[dan952]

Ho seguito alla lettera quello che hai suggerito, so che magari qualcuno più attento e intelligente avrebbe già capito, ma con me ci vuole più pazienza, quindi chiedo a te o a chi ti ha capito se possibile di chiarirmi meglio la questione.

[dan952]

Alla fine sono riuscito a risolverlo bastava iterare il secondo esercizio, "grazie" a tutti per l'aiuto e per la "pazienza". Per chi fosse interessato posto la soluzione:

int **dist(int **a, int n){
    int i,j,k,**d,**aa;
    d=AllocMatrix(n);
    aa=AllocMatrix(n);
    
    
    for (i=0;i<n;i++){
            for (j=0;j<n;j++){
                if (i==j){
                
                d[i][j]=0;
                
                }
                else if (a[i][j]==1 && i!=j) d[i][j]=1;
                else d[i][j]=-1;
            }
        }
    aa=CompMatrix(a,a,n);
    for (k=1;k<n;k++){
        for (i=0;i<n;i++){
            for (j=0;j<n;j++){
                if (aa[i][j]==k && i!=j && a[i][j]!=1) d[i][j]=1+k;
            }
                
        }
        aa=CompMatrix(a,aa,n);
        
    }
    return d;   
        
    
}

Edit: Macché risolto

[vict85]

In questa riga

aa=CompMatrix(a,aa,n);

c'è un grave bug. La memoria precedentemente puntata da aa non viene infatti distrutta. Bisogna sempre essere abbastanza attenti quando si lavora con i puntatori. Questo è soltanto uno dei tanti pericoli che si possono creare in funzioni di questo tipo.
Il tutto si può ovviamente risolvere con un paio di passaggi in più

int ** temp_mem = CompMatrix(a,aa,n);
free(aa); 
aa = temp_mem;

Inoltre a me sembra che la condizione

aa[i][j]==k && i!=j && a[i][j]!=1

sia sembra falsa. Infatti se CompMatrix fa la composizione delle relazioni allora aa è ancora una relazione e pertanto ogni suo elemento è 0 o 1. Non capisco inoltre la condizione finale relativa al fatto che a[j] debba essere diverso da 1.

Sinceramente non penso che funzioni. Fornisce il risultato corretto?

[dan952]

Sì con quelle due matrici della scheda sembra funzionare, ormai comunque ho consegnato, quel che è fatto, è fatto. Grazie lo stesso.

[dan952]

Sì comunque credo di aver scritto un'assurdità, quelle vengono perché k non va sopra 1