[C] Matrice triangolare...

[^Jack_Sparrow^]

Salve raga devo implementare l'algoritmo di Floy-Warshal su di una matrice triangolare :

 
    0
    1 0
    1 2 0
    3 4 5 0

Dato che mi sembra inutile sprecare tutta quella memoria per dati non utilizzati, vorrei implementarla tramite la matrice "packed" (il nome preciso non lo conosco).

Quella che utilizza un vettore unimodulare invece della classica matrice a due dimensioni!!!

Sono riuscito a ricavarmi solo le due dimensioni (banale):

(n * (n - 1) ) / 2 => Senza la diagonale (quello che serve a me!!!)

(n * n) / 2 => Con la diagonale

Come faccio ad accedere ai vari elementi???

Dovrebbe esserci una legge tipo i * j o qualcosa così!!!

Fatemi sapere!!! ^_^

[aenigma]

Vediamo se ho capito...
Tu metti tutti i valori in un array monodimensionale e vuoi indicizzarli, e pescarli in base al bisogno. In tal caso io farei cosi:

Preso come esempio la tua matrice triangolare. La posizione di un elemento é data da fattoriale(riga-1)+colonna

Per esempio prendiamo l'elemento che contiene "4" la sua posizione é in riga 4 colonna 2

se prendiamo gli elementi in sequenza esso occupa il posto:

(4-1)!+2=6+2=8

Facendo attenzione che in C gli array parono da 0 e dunque dovrai sottrarre 1 dal risultato finale.

Spero di aver intuito giusto il tuo problema.

[^Jack_Sparrow^]

Grazie!!!

[^Jack_Sparrow^]

Scusa ma se la diagonale degli zeri non esiste???

tipo la matrice è

    MATRICE 
 
    riga 0 | X
    riga 1 | 1 X
    riga 2 | 2 3 X
    riga 3 | 4 5 6 X
 
   ARRAY  [1 2 3 4 5 6]

La regola che mi hai detto non vale +, giusto? Che modifica dovrei fare???

[anx721]

Originariamente inviato da aenigma
[B]Preso come esempio la tua matrice triangolare. La posizione di un elemento é data da fattoriale(riga-1)+colonna

Questo è sbagliato.

La posizione di un elemento (i, j) é data da

(Somma dei primi i numeri) + j

se ci sono gli zeri, o

(Somma dei primi (i - 1) numeri) + j

se gli zeri no nci sono.

[^Jack_Sparrow^]

Originariamente inviato da anx721
Questo è sbagliato.

La posizione di un elemento (i, j) é data da

(Somma dei primi i numeri) + j - 1

se ci sono gli zeri, o

(Somma dei primi (i - 1) numeri) + j - 1

se gli zeri no nci sono.

Ancora + grazie allora!!!

[^Jack_Sparrow^]

Quindi se lavoro in C il "-1" non c vuole! Giusto???

[anx721]

Si, il meno uno non ci vuole, ho corretto la formula

Tieni presente che se non ci sono gli zeri, per l'elemento (0, 0) non puoi accedere alla matrice con la frmula, perche l'elemento, essendo uno zero della diaginale, non è presente nellla matrice.

[iguana13]

Quindi si tratta di numeri triangolari, non fattoriali.
Il triangolare di un numero n si ottiene con la formula

triangolare = n * (n + 1) / 2;

[aenigma]

Originariamente inviato da anx721
Questo è sbagliato.

La posizione di un elemento (i, j) é data da

(Somma dei primi i numeri) + j

se ci sono gli zeri, o

(Somma dei primi (i - 1) numeri) + j

se gli zeri no nci sono.

Ma quanto son rintronato... hai troppo ragione, il bello é che ho scritto fattoriale ma pensavo alla somma, e infatti nelle prove che ho fatto ho sommato i numeri....

bah, chissa a che stavo pensando...