.dsy:it. - Progetto Febbraio

Pages (8): « First ... « 2 3 4 5 [6] 7 8 »
Show 150 posts per page

.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- Progetto Febbraio (http://www.dsy.it/forum/showthread.php?threadid=41482)

Posted by number15 on 17-02-2011 09:08:

Altra cosa: partendo dall'albero rb, come calcolate l'affinità delle coppie?
Va creata una qualche struttura prima con tutte le affinità?

__________________
Portale segnalazioni marchi-negozi di abbigliamento
http://www.ovojo.com

Posted by number15 on 17-02-2011 13:30:

Vado avanti nel mio monologo.
Pensavo di creare una matrice di adiacenze pesata con gli hash name.
Ora questa matrice quando va creata?
La cosa più semplice sarebbe crearl
Va creata all'inizio e popolata, aggiornata ad ogni inserimento, aggiornamento, cancellazione di un invitato?

Spero che qualcuno possa aiutarmi.

__________________
Portale segnalazioni marchi-negozi di abbigliamento
http://www.ovojo.com

Posted by number15 on 19-02-2011 13:30:

__________________
Portale segnalazioni marchi-negozi di abbigliamento
http://www.ovojo.com

Posted by CowBoy on 20-02-2011 11:30:

Ho un problema: inserisco gli invitati, li stampo con 'invitati' e compaiono tutti.
faccio 'out invitato' e se poi faccio 'stampa invitato' mi dice che l'ha cancellato, quindi funziona.
Se rifaccio 'invitati', ne trovo n-1, ma c'è quello che ho eliminato mentre non ce n'è un altro.

Non sempre succede, dipende dall'ordine di eliminazione.

E' praticamente impossibile(se hai usato il codice per gli alberi rb dell'algoteam) che la funzione delete ti dia questo problema, a meno di spazi allocati male(guarderei per prima cosa le stringhe salvate nell'albero) o di memoria non liberata con free().

Pensavo di creare una matrice di adiacenze pesata con gli hash name.
Ora questa matrice quando va creata?
La cosa più semplice sarebbe crearl
Va creata all'inizio e popolata, aggiornata ad ogni inserimento, aggiornamento, cancellazione di un invitato?

I nodi del grafo devono essere numerati partendo da 1, in maniera progressiva. Una matrice di adiacenza può risolvere il problema, ma in tempo n^3 se devi fare la chiusura transitiva oppure il calcolo del costo del cammino minimo.

Prova ad implementare un grafo con le liste di adiacenza, magari usando l'algoritmo di Dijkstra per il calcolo dei cammini di peso minimo(se questa implementazione risolve il tuo problema delle affinità, non ho letto il progetto).
Se ti serve a qualcosa Qui trovi il codice necessario per le strutture dati e per Dijsktra. Cerca di capire a cosa servono, il copia/incolla ossessivo ti creerà solo problemi.

Ciao!

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

Posted by number15 on 20-02-2011 11:35:

intanto grazie.
Lasciando un attimo in stand by il discorso del grafo,
ho notato che la funzione hash non mantiene l'ordinamento dei nomi (ovvero può essere che Tito venga prima di Aurelio).
E' una cosa normale o va cambiata la funzione?
Perché ora ovviamente con il comando invitati, me li stampa non in ordine.

__________________
Portale segnalazioni marchi-negozi di abbigliamento
http://www.ovojo.com

Posted by CowBoy on 20-02-2011 11:43:

Esiste un limite per la dimensione del nome, la lunghezza della stringa è fissa?

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

Posted by number15 on 20-02-2011 11:45:

Nessun limite, e la lunghezza delle stringhe varia a seconda del nome ovviamente.
Io ho utilizzato la funzione hash dell'algoteam, che converte una stringa in un numero, ma sommando i valori dei caratteri ovviamente poi l'ordinamento non è rispettato

__________________
Portale segnalazioni marchi-negozi di abbigliamento
http://www.ovojo.com

Posted by CowBoy on 20-02-2011 11:59:

Allora è tutto normale. La funzione hash ti da "il resto della divisione in modulo 27" partendo da 1 e lo converte in decimale in questo modo-> TITO = T * 27^3 + I * 27^2 + T * 27^1 + O * 27^0
mentre-> AURELIO = A * 27^6 + U * 27^5 + R * 27^4 + E * 27^3 + L * 27^2 + I * 27^1 + O * 27^0

Come portai notare, più lungo è il nome e maggiore sarà il numero decimale che lo rappresenterà. Risulterebbero ordinati a partià di lunghezza(a meno di qualche overflow ).

Soluzione? Lista + quick/merge/heap sort e confronto di stringhe...

#include <string.h>

strcmp(stringa_1, stringa_2)

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

Posted by number15 on 20-02-2011 12:02:

Si si, quello l'ho capito.
Però è giusto l'inserimento nell'albero mediante hash o non rispettando l'ordinamento non va bene.

Per la stampa degli invitati creo quindi una lista con i nomi e poi li ordino.
Ora vedo questo allora.
Grazie

__________________
Portale segnalazioni marchi-negozi di abbigliamento
http://www.ovojo.com

Posted by CowBoy on 20-02-2011 12:04:

Attenzione però che la funzione hash dell'algoteam va modificata!

code:
bigInt hash(char* w){
  bigInt val = 0;
  while(*w!='\0'){
    val = (27*val + charValue(*w)) % HASHSIZE;
    w++;
  }
  return val;
}

% HASHSIZE; definita il precedenza come 5000 indica il numero di elementi nella tabella(da 0 a 4999...) e potrebbe crearti problemi.

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

Posted by number15 on 20-02-2011 12:07:

Io l'ho levato, come mi pare abbia fatto anche tu nel progetto incastri.

__________________
Portale segnalazioni marchi-negozi di abbigliamento
http://www.ovojo.com

Posted by CowBoy on 20-02-2011 12:13:

Giusto!

Usare la funzione hash va più che bene, alla fine quello che ti serve è una struttura efficiente per effettuare inserimenti, ricerche e cancellazioni in tempo logaritmico o al massimo O(n*logn).

Per l'ordinamento vale la stessa cosa, trovare un modo efficiente(struttura+algoritmo) che faccia al caso tuo.

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

Posted by number15 on 20-02-2011 12:15:

Perfetto. Oggi pomeriggio allora provo la lista per i nomi che dovrebbe risolvermi quel problema degli invitati.
Sicuramente ti proverò a rompere ancora

__________________
Portale segnalazioni marchi-negozi di abbigliamento
http://www.ovojo.com

Posted by CowBoy on 20-02-2011 12:22:

Ho dato un'occhiata a mergesort su wikipedia e sembra perfetto.

1) alloca lo spazio per un vettore di N elementi(puntatori a stringhe), e copia le stringhe dell'albero(punta ogni nome).
2) effettua mergesort confrontando le stringhe
3) restituisci il vettore

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

Posted by CowBoy on 20-02-2011 12:23:

Originally posted by number15
Perfetto. Oggi pomeriggio allora provo la lista per i nomi che dovrebbe risolvermi quel problema degli invitati.
Sicuramente ti proverò a rompere ancora

Non ci sarò!

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

All times are GMT. The time now is 16:47.

Pages (8): « First ... « 2 3 4 5 [6] 7 8 »
Show all 110 posts from this thread on one page