 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
Progetto Febbraio
Clicca QUI per vedere il messaggio nel forum |
| maddy |
Ciao ragazzi, qualcuno di voi sa quando uscirà il prossimo progetto?
Le date degli appelli sono: 18 Febbraio, 4 Marzo e si riferiscono alla prova orale. Inoltre ho visto che gli appelli sono gli stessi sia per il turno diurno che serale.
Ho visto che anche il prof. del diurno ha cambiato le modalità d'esame, cioè ha tolto la prova scritta (a parte l'appello del 10 gennaio), quindi in teoria dovrebbe essere progetto+orale come al serale no?
Ma se la prova orale è il 18 Febbraio il progetto non dovrebbe essere già uscito?
O_o |
| maddy |
Grazie Mille !!! =)
Quindi domani... |
| Giga |
Sapete dove verrà pubblicato il testo del progetto?
Sulla pagina del prof Frasca non c'è ancora nulla :sad: |
| Chobeat |
| L'ha scritto la Lonati o Goldwurm. FOTTUTI GENI, SONO DEI FOTTUTI GENI. Ho riso dall'inizio alla fine. |
| mostrielo |
| Bunga bunga... mai progetto fu così d'attualità. |
| Chobeat |
ma siamo sicuri che per la seconda consegna voglia solo la seconda parte e non entrambe? A prima vista non sembra molto più complicata della prima parte.
edit:
Questo è l'ideatore del progetto. è tutto rosso e non penso sia un caso. COMUNISTI COMUNISTI COMUNISTI. |
| number15 |
| Scusate ma è valido anche per Torelli? |
| figo1987 |
| progetto geniale! cmq qualcuno di voi ha già pensato a che struttura usare? a me vengono in mente solo i grafi... |
| Chobeat |
| io ho ancora le idee un po' confuse, ma penso che ci vada un grafo pesato per calcolare le affinità, perlomeno quelle della funzione festa(). L'idea è che l'algoritmo si giri il grafo e per ogni nodo (ogni persona), veda le affinità di tutti gli adiacenti( quindi tutti quelli di sesso opposto alla fine). Fatta questa tabella si raggruppano. Ma mi sembra un po' troppo pesante e macchinoso. Mi ci metterò bene a tavolino fra un paio di giorni. Per la semplice ricerca ovviamente albero rb. |
| figo1987 |
| infatti anche io l'ho pensata cosi'.. pero metterei negli adiacenti solo quelli che hanno i giorni compatibili.. cosi' da risparmiare spazio... non capisco xchè l'rb xro'... |
| Chobeat |
Originally posted by figo1987
infatti anche io l'ho pensata cosi'.. pero metterei negli adiacenti solo quelli che hanno i giorni compatibili.. cosi' da risparmiare spazio... non capisco xchè l'rb xro'... l'rb è un'altra cosa, ti serve per far le ricerche normali.
un'altra idea è per calcolare l'affinità tra 2: avere due alberi distinti per uomini e donne. Se devo cercare un nome, lo cerco prima in uno poi nell'altro e non è il massimo, però quando deve fare il calcolo dell'affinità, ci mette meno. In alternativa, tengo due alberi, doppio spazio ma ho sempre una ricerca ottima. |
| figo1987 |
| eh ma devi cercare le affinità migliori tra tutti.. quindi dovresti ogni volta scorrerti praticamente tutti e due gli alberi ogni volta.. |
| Chobeat |
| io parlo solo della funzione affinità, il calcolo per le altre funzioni penso sia molto più complicato. ci arriverò pian piano. |
| Guccio |
Anch'io ho pensato a un grafo pesato (i pesi sarebbero le affinità giusto?), ma visto che è parecchio connesso non converrebbe implementarlo con matrice di adiacenza?
Avevo pensato anche a mettere nelle prime 'n' posizioni gli 'n' uomini e poi fino a 'n+m' le m donne e mettergli un indice che indicasse dove cominciano le donne. Che ne pensate? |
| Chobeat |
Originally posted by Guccio
Anch'io ho pensato a un grafo pesato (i pesi sarebbero le affinità giusto?), ma visto che è parecchio connesso non converrebbe implementarlo con matrice di adiacenza?
Avevo pensato anche a mettere nelle prime 'n' posizioni gli 'n' uomini e poi fino a 'n+m' le m donne e mettergli un indice che indicasse dove cominciano le donne. Che ne pensate?
è una soluzione interessante ma sarebbe da studiare. "matrici" e "sufficienza" sono una contraddizione in un progetto di algoritmi. |
| Chobeat |
| per la ricerca di nomi, stavo leggendo, consigliano un prefix tree. dite che può andare bene? |
| Guccio |
| forse mi sono perso qualcosa ma cos'è un prefix tree? |
| Chobeat |
cerca "trie" su google. è una struttura neanche troppo complessa che in teoria dovrebbe essere la scelta migliore per questo tipo di cose.
Penso si chiami prefix perché è quella usata nella ricerca incrementale ad esempio nei siti dove ti suggerisce le parole, o nelle tastiere degli smartphone. |
| lSical |
| Ciao, stavo pensando ad un albero binario, uno dei problemi però è nella funzione festa, che prende solo gli invitati partecipanti in un determinato giorno, quindi per trovare gli invitati dovrei cercare in tutto l'albero... voi come pensate di fare ? |
| Chobeat |
come abbiamo scritto prima, la struttura dati per festa va costruita in maniera diversa per essere ottimizzata, secondo me.
l'albero binario mi sembra una struttura un po' approssimativa in ogni caso. |
| lSical |
| intendevo un albero binario di ricerca... con gli esempi dati nel testo mi viene un albero abbastanza bilanciato, a meno che non inseriscano invitati con nomi ordinati dovrebbe andare bene ?... vabbè credo che inizierò a cercare info sugli rb alberi xD |
| Chobeat |
| io adesso sono riuscito a fare tutto con gli alberi rb, l'unico problema è che non si porta dietro le info del nodo ma solo la key. sarà qualche problema di puntatori. |
| CowBoy |
| Devi allocare lo spazio in maniera corretta. Nella soluzione del progetto incastri che ho postato nella sezione Filez ho usato una funzione che convertiva un nome(stringa) in un numero, da utilizzare come key per l'albero. |
| CowBoy |
In questo sito oppure in questo, potete trovare implementazioni in C di strutture dati e algoritmi vari. Tutto è ben fatto e potete modificare il codice a vostro piacere.
Buon progetto!! |
| figo1987 |
| sembrerà stupido... ma i comandi sono letti da file vero? cosa usate per leggere la riga? scanf? e come fate per gestire gli spazi? |
| Chobeat |
Originally posted by CowBoy
Devi allocare lo spazio in maniera corretta. Nella soluzione del progetto incastri che ho postato nella sezione Filez ho usato una funzione che convertiva un nome(stringa) in un numero, da utilizzare come key per l'albero. interessante...comunque ormai son vicino alla soluzione, però l'insert dà ancora problemi. adesso vedo la tua funzione e provo ad usarla se non capisco dov'è il problema. Comunque può essere benissimo che sia lì, visto che adesso si incasina con gli insert |
| figo1987 |
Originally posted by figo1987
sembrerà stupido... ma i comandi sono letti da file vero? cosa usate per leggere la riga? scanf? e come fate per gestire gli spazi? xchè se leggete la nota 3 dice di usare la scanf... ma non doveva essere da file( e quindi fscanf)? |
| Chobeat |
ok ho utilizzato la tua funzione un pelo modificata e funziona tutto.
Ora l'unico problema che mi rimane è che...non riesco a stampare il nome. Mi stampa i giorni di presenza che sono una stringa identica, ma il nome sbarella e non riesco a capire perché.
Comunque per oggi sono soddisfatto. Domani procederò con la funzione Festa e Giorni. |
| CowBoy |
Originally posted by figo1987
xchè se leggete la nota 3 dice di usare la scanf... ma non doveva essere da file( e quindi fscanf)?
Se non ti indica il nome specifico di un file allora si intende la lettura da file tramite input redirecting... quindi va usato scanf/getchar...
Originally posted by figo1987
sembrerà stupido... ma i comandi sono letti da file vero? cosa usate per leggere la riga? scanf? e come fate per gestire gli spazi?
Sempre nel progetto incastri, sezione filez, nel metodo main trovi un ciclo for che legge i comandi, e uno switch-case che li interpreta. Usando la funzione scanf non hai bisogno di controllare gli spazi dato che la funzione gestisce in modo intelligente la lettura. Ti suggerirei cmq di controllare l'input letto. |
| Chobeat |
Ieri notte ho pensato.
Fare la matrice è una porcheria. Devo fare n operazioni per crearla ed n+logn operazioni per fare la funzione festa.
Io ho poi analizzato 2 soluzioni: grafo in cui ogni donna è connessa ad ogni uomo con il suo peso e albero contenente il dato uomo-donna-affinità.
Nel secondo caso, se uso l'affinità come chiave, al momento del calcolo dell'affinità, vado ad inserire la tripletta nell'albero che risulterà già ordinato.Mi bastano n/2 operazioni, perché una volta fatto per tutti gli uomini, non mi interessa farlo per tutte le donne. Per fare la funzione Festa(), basterà prendere gli n nodi in cima all'albero che è già ordinato.
Per la funzione del 28 febbraio potrebbe anche andare bene, se fatto con una modifica: semplicemente prendo gli n nodi, facendo un check sui nomi delle persone già estratte. Per fare il check posso basta controllare tutti i nodi sopra la coppia esaminata. Il problema è che viene n^2 e col grafo sarebbe più veloce probabilmente, perché cancello completamente i nodi coinvolti.
Per la funzione del 14 Febbraio invece, può essere che questo metodo faccia schifo, non ci ho ancora ragionato. |
| Guccio |
"4. Domanda-trucchetto: e` possibile, secondo il candidato, che gli algoritmi e le strutture dati insegnati e durante il corso non abbiano alcuna attinenza col progetto assegnato?
5. Ancora piu` chiaramente: soluzioni basate solo su ricerche lineari e altre tecniche immediate tipica mente NON risolveranno i problemi in maniera efficiente."
Ma a cosa si riferisce?
__________________
http://world2.talesofmagic.it/?c=1&u=401005097 |
| Chobeat |
la soluzione che ho detto stamattina è una cavolata. bocciata in toto.
Adesso sto provando a vedere per il grafo, ma non saprei, anche in linea teorica, che cosa fargli fare per raggruppare gli invitati. |
| zandrek |
Originally posted by Guccio
"4. Domanda-trucchetto: e` possibile, secondo il candidato, che gli algoritmi e le strutture dati insegnati e durante il corso non abbiano alcuna attinenza col progetto assegnato?
5. Ancora piu` chiaramente: soluzioni basate solo su ricerche lineari e altre tecniche immediate tipica mente NON risolveranno i problemi in maniera efficiente."
Ma a cosa si riferisce?
__________________
http://world2.talesofmagic.it/?c=1&u=401005097
ah boh bella domanda:?
se le cose dette durante il corso non servono allora ******** ****** ***** (omissis)
ma ricerche lineari intende negli array? |
| figo1987 |
| secondo me vuol dire che non devi usare array o matrici... |
| zandrek |
ah beh grande aiuto....(comunque rileggendo bene è così anche per me)
edit tra le altre cose 3 pubblicazioni in 3 giorni ..... speriamo sia la volta buona.... |
| number15 |
| Richiedo, è valido anche per Torelli? |
| plafo |
Originally posted by number15
Richiedo, è valido anche per Torelli?
si è valido anche per torelli |
| figo1987 |
| salve qualcuno ha pensato alla complessità della funzione festa? io non riesco a scendere sotto a O(n^2)... |
| Guccio |
Originally posted by figo1987
salve qualcuno ha pensato alla complessità della funzione festa? io non riesco a scendere sotto a O(n^2)...
Che struttura dati stai usando? |
| figo1987 |
| allora... tutti gli invitati sono in alberi RB ...per le n coppie più affini invece uso una lista ordinata in base all'affinità(se avete qualche altra soluzione dite pure).. poi pero' per raggrupparle in stanze devo perforza usare i grafi... e quindi O(n^2) |
| Chobeat |
| io la lista ordinata l'ho saltata a piè pari appunto perché tanto poi il grafo devi farlo comunque. |
| Guccio |
Originally posted by figo1987
allora... tutti gli invitati sono in alberi RB ...per le n coppie più affini invece uso una lista ordinata in base all'affinità(se avete qualche altra soluzione dite pure).. poi pero' per raggrupparle in stanze devo perforza usare i grafi... e quindi O(n^2)
scusa come hai fatto a fargli alberi rb? per glia lberi rb si presume che la lista sia ordinata....tu come l'hai ordinata?hashing delle strnghe dei nomi? |
| figo1987 |
| si.. ho utilizzato l'hash che c'è anche nel progetto nella sezione file... |
| Guccio |
| Non riesco a trovarlo...posteresti il link? |
| Alessio |
Ciao a tutti, ho una domanda da fare in merito alla funzione Festa. Il dubbio è su come vengono formati i gruppi: secondo quale calcolo/criterio un senatore riesce a soddisfare due o più donne? Oppure come può una donna essere soddisfatta da più uomini?
Perché tutto sarebbe lineare e chiaro se ogni uomo sceglie una SOLA donna. |
| Chobeat |
quella è la funzione per il 28 febbraio.
In realtà è molto più facile così se ragioni come abbiamo fatto noi. L'idea è di avere le n triple (uomo, donna, affinità) con l'affinità migliore e da queste costruire un grafo. Fatto questo, fai un algoritmo che si gira tutti i gruppetti del grafo e vede come stanno raggruppati. |
| Alessio |
scusami non mi è ancora chiaro ... la funzione festa (giorno, n) fa parte delle funzioni da implementare x entrambi gli appelli.
Nel testo si legge testualmente:
"La fi lantropia talvolta puo richiedere una certa privacy e quindi benefattore e bene ciata si appartano,
ma non necessariamente a coppie. Infatti, secondo la regola descritta, puo benissimo succedere che un
senatore (particolarmente generoso) aiuti piu di una popolana, o che una popolana (particolarmente in
dicolta) si faccia aiutare da piu di un benefattore."
Dunque quel che ho capito io è questo: io devo trovare per ogni senatore qual'è la donna più affine a lui. Da questa cosa risulterebbe che ogni uomo sceglie solo una donna ma può capitare che due uomini scelgano la stessa donna (in quanto è la più affine per entrambi). Fin qui mi sembra ok. Il problema nasce dall'esempio che riporta la prof nel testo. Infatti si vede che Tarquinio è in coppia sia con Tullia che con Messalina!! Come può essere possibile? |
| Chobeat |
perché un uomo si sceglie tutte le donne che vuole ("puo benissimo succedere che un
senatore (particolarmente generoso) aiuti piu di una popolana" |
| Alessio |
| però a questo punto se un senatore si sceglie tutte le donne che vuole si avrebbe che io in modo arbitrario dico che il senatore1 si sceglie 3 donne, il senatore2 ne sceglie 4 ecc... Così facendo avrei un output che non coinciderebbe più con quello fornito dalla prof. Infatti nel progetto non c'è nessuna funzione che definisca quante donne vengono scelte da ciascun senatore. Non so se mi sono spiegato bene ... |
| Guccio |
Sto leggendo l'implementazione dell'RB-tree dall'algoteam, e mi sono inbattuto in questo prototipo:
void inord(rbnode *p, rbnode *nil, void (*op)(rbnode *))
che parametro sarebbe "void (*op)(rbnode *)"??? :| è la prima volta che leggo una cosa del genere |
| zandrek |
puntatore a funzione,e quella funzione punta a void .... ha "spiegato" ste robe l'ultimo giorno di lezione....
scusa se non ti scrivo di più ma non è molto chiaro nemmeno a me... |
| Chobeat |
| allora avevo ragione... |
| Panz90 |
Modifico la domanda...
Per fare festa vi scorrete tutto l'albero tenendo già conto del giorno e salvate le affinità migliori?
Grazie. |
| Chobeat |
| io salvo tutte le affinità in un albero binario(quindi ordinato) e poi prendo le N migliori con cui costruisco il grafo. |
| Panz90 |
| Si idem, però una volta che hai le affinità migliori per festa non basta? Poi si fanno dei calcoli per stanze etc, no? Il grafo è per festa? |
| Guccio |
Originally posted by figo1987
salve qualcuno ha pensato alla complessità della funzione festa? io non riesco a scendere sotto a O(n^2)...
Bè sei riuscito a scendere sotto O(n^2)? |
| figo1987 |
| si pero' non funziona ancora bene... forse c'è un errore se poi funziona vi dico... |
| Guccio |
| E come hai fatto a scendere sotto O(n^2)? la lista di uscita del bfs dove l'hai memorizzata? |
| figo1987 |
| io ho memorizzato le n coppie in una lista ed ho creato un albero rb con liste di adiacenza.. cosi' poi per scorrerlo e contarlo il costo è quello dell'attraversamento di un grafo in profondità |
| Guccio |
| Le coppie che hai fatto uscire dal bfs sono nel formato uomo-donna o hai mantenuto anche le copie donna-uomo? |
| Guccio |
Originally posted by figo1987
io ho memorizzato le n coppie in una lista ed ho creato un albero rb con liste di adiacenza.. cosi' poi per scorrerlo e contarlo il costo è quello dell'attraversamento di un grafo in profondità
Ma per alber rb intendi albero di ricerca binaria o albero red-black? |
| number15 |
Sono abbastanza indietro sia di C sia di algoritmi quindi avrei bisogno del vostro aiuto.
Ho capito che è consigliabile usare un albero rb in quanto efficiente sulle operazioni di inserimento e cancellazione.
Ora volevo chiedervi se i passaggi son corretti:
Creo i nodi dell'albero rb con una struttura contenente:
-chiave (hash su nome)
-vari dati invitato
-puntatori left, right e padre
Creo l’abero rb
Funzioni inserimento, rimozione, stampa dipendenti da uno switch sui primi caratteri della stringa di input.
Giusto? |
| Panz90 |
Originally posted by Chobeat
io salvo tutte le affinità in un albero binario(quindi ordinato) e poi prendo le N migliori con cui costruisco il grafo.
Ho le affinità migliori.. Ma il grafo è fatto con le liste? Perchè con la matrice sarebbe una semplice somma ma ho qualche problema nel realizzarlo... |
| Utopia |
| Infatti, che tipo grafo? |
| Chobeat |
| ragazzi io lascio il progetto. ci rivediamo a Giugno |
| number15 |
Ma nei nodi si deve salvare tutto o solo l'hash del nome?
(scusate fa faccio domande del cazzo, ma ci capisco niente) |
| Utopia |
| Ragazzi io ho le n coppie con le affinità migliori, come create i gruppi ? |
| adlucio |
Ciao sono nella merda perchè ho usato gli rbtree dell'algoteam e nella funzione:
void rbdelete(rbtree *tree, rbnode *q){
rbnode *r, *s;
if(q->left == tree->nil || q->right == tree->nil)
r = q;
else
r = treesucc(tree,q);
s = r->left != tree->nil ? r->left : r->right;
s->up = r->up;
if(r->up == tree->nil)
tree->root = s;
else
if(r == r->up->left)
r->up->left = s;
else
r->up->right = s;
if(r != q){
q->v = r->v;
}
if(r->c == black)
fixup(tree, s);
free(r);
}
non riordina in modo corretto perchè scazza con le chiavi che sono di tipo stringhe. Voi cosa avete modificato? |
| number15 |
| da quanto ho capito (poco) devi trasformare il nome in un intero tramite la funzione hash (la trovi sempre nell'algoteam) |
| Utopia |
Si, per trasformare una stringa in un numero, ci sono un sacco di funzioni hash sparse su internet. Io ho fatto un merge di due e mi è uscita una funzione ottimale :)
Per quanto riguarda la creazione dei gruppi ? Qualcuno ha un idea ?
Ho le migliori coppie ... ma non riesco a trovare un modo efficiente per raggrupparle. :( |
| ciao |
Originally posted by Utopia
[
Per quanto riguarda la creazione dei gruppi ? Qualcuno ha un idea ?
Ho le migliori coppie ... ma non riesco a trovare un modo efficiente per raggrupparle. :( [/B]
Se hai trovato le coppie, confronti i nomi di uomo e donna, due coppie che hanno uguaglianza verranno inserite nello stesso gruppo. |
| number15 |
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.
Da cosa può dipendere? |
| number15 |
Mi sa che è l'ordinamento.
Qualcuno potrebbe gentilmente postarmi la parte del caso 'invitati'? |
| number15 |
Altra cosa: partendo dall'albero rb, come calcolate l'affinità delle coppie?
Va creata una qualche struttura prima con tutte le affinità? |
| number15 |
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. |
| CowBoy |
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! |
| number15 |
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. |
| CowBoy |
| Esiste un limite per la dimensione del nome, la lunghezza della stringa è fissa? |
| number15 |
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 |
| CowBoy |
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) |
| number15 |
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 |
| CowBoy |
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. |
| number15 |
| Io l'ho levato, come mi pare abbia fatto anche tu nel progetto incastri. |
| CowBoy |
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. |
| number15 |
Perfetto. Oggi pomeriggio allora provo la lista per i nomi che dovrebbe risolvermi quel problema degli invitati.
Sicuramente ti proverò a rompere ancora :D |
| CowBoy |
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 |
| CowBoy |
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 :D
Non ci sarò! :) |
| number15 |
Una cosa che non mi è chiara:
la lista la creo all'inizio e la popolo ad ogni inserimento di una persona oppure la creo quando ho bisogno di stampare le persone ordinate?
Perché nel primo caso non posso sapere a monte quanto dev'essere grande la lista |
| number15 |
Originally posted by CowBoy
Non ci sarò! :)
:cry: |
| CowBoy |
Mantieni un contatore con il numero degli elementi inseriti/cancellati nell'albero, per ogni chiamata si "sort" alloca il vettore e popolalo quando chiami l'ordinamento.
Per concludere libera lo spazio del vettore. |
| number15 |
Fatto.
Alla fine ho usato un array al posto di una lista e ordinato con mergesort.
Questo punto risolto... grazie. |
| CowBoy |
| Figurati! Una domanda, ma l'ordinamento per cosa ti serve? |
| number15 |
| Per stampare gli invitati ordinati per nome |
| CowBoy |
| Viene richiesto nel testo del progetto? |
| number15 |
| Non in modo esplicito, cioè chiede di stampare tutti gli invitati e poi nell'output lui li stampa in ordine di nome. |
| Miran |
Ciao a tutti, io sono arrivato a creare la struttura uomo,donna e affinità
relativa.... ma poi non riesco a costruire i gruppi. Sul forum dice di
usare i grafi.... come potrei strutturali?
Grazie |
| CowBoy |
Come vertici metti tutti i partecipanti alla cena, e poi collega il benefattore alla popolana affine con un arco di peso = affinità.
Ciao! |
|
|
|
|
