.dsy:it. - Progetto Febbraio

Calendar

Members

Faq

Logout

.dsy:it. : Powered by vBulletin version 2.3.1

.dsy:it. > Didattica > Corsi A - F > Algoritmi e strutture dati > Progetto Febbraio

Pages (8): « First ... « 2 3 4 5 [6] 7 8 »

Last Thread Next Thread

Author

Thread Expand all | Contract all

number15

.grande:maestro.

User info:

Registered: Nov 2005
Posts: 652 (0.09 al dì)
Location:
Corso:
Anno:
Time Online: 121 Days, 13:57:11 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

17-02-2011 09:08

Click here to Send number15 a Private Message

number15

.grande:maestro.

User info:

Registered: Nov 2005
Posts: 652 (0.09 al dì)
Location:
Corso:
Anno:
Time Online: 121 Days, 13:57:11 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

17-02-2011 13:30

number15

.grande:maestro.

User info:

Registered: Nov 2005
Posts: 652 (0.09 al dì)
Location:
Corso:
Anno:
Time Online: 121 Days, 13:57:11 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

19-02-2011 13:30

CowBoy

.arcimaestro.

User info:

Registered: May 2006
Posts: 294 (0.04 al dì)
Location: Milano
Corso: F49 - Informatica
Anno: Laureato F49
Time Online: 3 Days, 13:40:27 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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 ´´-±·ø·± ..

20-02-2011 11:30

Click here to Send CowBoy a Private Message

number15

.grande:maestro.

User info:

Registered: Nov 2005
Posts: 652 (0.09 al dì)
Location:
Corso:
Anno:
Time Online: 121 Days, 13:57:11 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

20-02-2011 11:35

CowBoy

.arcimaestro.

Post actions:

Edit | Report | IP: Logged

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

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

20-02-2011 11:43

number15

.grande:maestro.

User info:

Registered: Nov 2005
Posts: 652 (0.09 al dì)
Location:
Corso:
Anno:
Time Online: 121 Days, 13:57:11 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

20-02-2011 11:45

CowBoy

.arcimaestro.

Post actions:

Edit | Report | IP: Logged

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 ´´-±·ø·± ..

Last edited by CowBoy on 20-02-2011 at 12:08

20-02-2011 11:59

number15

.grande:maestro.

User info:

Registered: Nov 2005
Posts: 652 (0.09 al dì)
Location:
Corso:
Anno:
Time Online: 121 Days, 13:57:11 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

20-02-2011 12:02

CowBoy

.arcimaestro.

Post actions:

Edit | Report | IP: Logged

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 ´´-±·ø·± ..

20-02-2011 12:04

number15

.grande:maestro.

User info:

Registered: Nov 2005
Posts: 652 (0.09 al dì)
Location:
Corso:
Anno:
Time Online: 121 Days, 13:57:11 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

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

20-02-2011 12:07

CowBoy

.arcimaestro.

Post actions:

Edit | Report | IP: Logged

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 ´´-±·ø·± ..

20-02-2011 12:13

number15

.grande:maestro.

User info:

Registered: Nov 2005
Posts: 652 (0.09 al dì)
Location:
Corso:
Anno:
Time Online: 121 Days, 13:57:11 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

20-02-2011 12:15

CowBoy

.arcimaestro.

Post actions:

Edit | Report | IP: Logged

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 ´´-±·ø·± ..

20-02-2011 12:22

CowBoy

.arcimaestro.

Post actions:

Edit | Report | IP: Logged

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 ´´-±·ø·± ..

20-02-2011 12:23

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

Pages (8): « First ... « 2 3 4 5 [6] 7 8 »

Last Thread Next Thread

Show Printable Version |

Email this Page |

Subscribe to this Thread |

Add to Bookmarks

Forum Jump:

Rate This Thread:

Forum Rules:

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

HTML code is OFF
vB code is ON
Smilies are ON
[IMG] code is ON

Pagina generata in 0.068 seconds (68.78% PHP - 31.22% MySQL) con 23 query.