 | |
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 |
[Algoritmi - Torelli] Appello Luglio
Clicca QUI per vedere il messaggio nel forum |
| lino |
Volevo chiedere a tutti i ragazzi che come me devono fare l'appello di luglio con Torelli, se poteva andar bene creare un gruppo di studio, per studiare insieme il progetto e decidere quale struttura dati utilizzare.
Intanto se ci sono problemi relativi allo studio parliamone.
ciao |
| osnes6 |
Condivido l'idea.
Ciao |
| York |
| Se va bene mi associo anch'io.... |
| mitnik |
Ottima idea. Così uno scambio di opinioni porta a buoni risultati.
Fatevi sentire qui sul dsy. |
| lino |
| Perfetto, teniamoci in contatto.... voi nel frattempo studiate la teoria? Che esercizi fate per provare a implementare le strutture dati studiate? ciao |
| sirio |
Ok, mi associo anch'io.
Ma è solo la mia impressione o il prog. di giugno era molto complesso? |
| lino |
Avete provato ad implementare qualche esercizio tramite rb alberi?
com'è stato il risultato? |
| maynard80 |
anche io e AllXXX ci associamo all'idea
Un unica domanda: dove posso scaricare il compilatore gcc aggiornato? ho sempre usato come ambiente grafico per Win il DevC++, non ho mai usato linux per compilare C, l'ho installato per l'esame di sistemi operativi, dove posso trovare il compilatore e un ambiente grafico interessante per Linux?? |
| York |
Per il compilatore C ---> gcc.gnu.org
Per Linux il compilatore è sempre il gcc ma non sò se ci sono ambienti grafici di sviluppo... |
| maynard80 |
| ah ma voi sotto linx che editor usate? non mi dite VI !!? |
| Gusher |
Originally posted by maynard80
ah ma voi sotto linx che editor usate? non mi dite VI !!?
Gedit su Gnome |
| allxxx |
ci sono alla grande grazie maynard80!!!
ciao allxxx |
| loreste |
Ho dato questo esame ad aprile, vi consiglio di sviluppare sotto linux (perchè Fiorentini controlla con linux) ed ho visto persone che dopo la consegna hanno scoperto che sotto linux o non compilava o c'erano problemi.
Io utilizzo Mandrake 10, e come editor c'e' KDenvelop e mi sono trovato benissimo.
Un altro consiglio è scaricate gli appunti di Fiorentini, troverete diverso codice pronto per l'uso (gestione dell'input, inserimento in una lista/albero, quicksort, elimina elemento, trova elemento etc) farete il 30% del progetto con un bel copia ed incolla.
Ciao ed in bocca al lupo |
| York |
Originally posted by maynard80
ah ma voi sotto linx che editor usate? non mi dite VI !!?
No..io uso vim... :-D
Il progetto l'ho scaricato ora....devo ancora leggemelo bene... |
| mitnik |
Che casino sto progetto.
Mi sa che ci metterò un pò a capire cio che si deve fare. Voi che dite? |
| LazerPhEa |
| ...Io dico che è allucinante. |
| dirkpitt |
| E' uscito il progetto di luglio: "Banchetto". Consegna il 19 luglio. |
| LazerPhEa |
| ...Il thread sotto a questo tratta il medesimo argomento... |
| yoruno |
Intervento del moderatore:
Grazie, Lazer, ho unito i thread :) |
| dirkpitt |
Originally posted by mitnik
Che casino sto progetto.
Condivido perfettamente! Mi sa che non sarà proprio una passeggiata.... |
| dirkpitt |
Originally posted by lino
Volevo chiedere a tutti i ragazzi che come me devono fare l'appello di luglio con Torelli, se poteva andar bene creare un gruppo di studio, per studiare insieme il progetto e decidere quale struttura dati utilizzare.
Mi associo! :D |
| mitnik |
| Da quando è uscito il progetto stamattina solo adesso sono riuscito a capire cosa vuole che si faccia (o almeno spero) però è un po un casino e non so da dove partire per pensare ad una struttura dati approrpiata. |
| York |
Anch'io ho capito cosa bisogna fare...
Consiglio di provare a simulare a mano l'esempio e si capisce tutto (o quasi)!!
Quanto a implementarlo la vedo dura!!
Per la struttura dati uno può usare quello che preferisce tra alberi e liste (anche una lista semplice) poi quale sia quella migliore non sò...
Ci penso.... |
| PuNk-MaD |
| ragazzi apro il Thread...ho già delle difficoltà sulla spirale per beccare gli spazi liberi :( |
| yoruno |
Intervento del moderatore:
Penso ti riferissi a questo stesso progetto, se ho sbagliato ad unire dimmelo che provvedo. :) |
| maynard80 |
| madonna santa non ci ho capito nulla, qualcuno riesce a spiegarlo magari semplificando il contenuto del testo? (si sono abbastanza ottuso) |
| dirkpitt |
Originally posted by York
Consiglio di provare a simulare a mano l'esempio e si capisce tutto (o quasi)!!
Ho schematizzato l'esempio, spero sia corretto. Potete scaricarlo qui
E' un file in Excel.. |
| pincopallino |
Originally posted by dirkpitt
Ho schematizzato l'esempio, spero sia corretto. Potete scaricarlo qui
E' un file in Excel..
già...io ho provato a simularlo a mano...ed effettivamente si capisce tutto decisamente meglio rispetto a tutte le formalità con cui le cose sono descritte nel testo....
rimane che così a prima vista mi sembra un casotto implementare sta roba, cmq siamo ancora al primo giorno ed il tempo porta consiglio...speriam bene :shock: |
| mitnik |
Una domanda.
Supponiamo di avere una configurazione tale per cui un invitato ha 4 insiemi di tavoli adeguati e tutti e quattro con la stessa distanza d(S), quale insieme considero per il calcolo della pozizione ottimale dell'invitato? (è come nell'esempio del prof)
Io direi di considerare l'insieme con il tavolo inserito per prima, voi che dite? |
| storm |
| Che roba.....ieri l'ho letto e mi è venuto il mal di testa !!...Caz è peggio dell'altra volta ! Mi piace solo il titolo..:asd: |
| dirkpitt |
Originally posted by mitnik
Supponiamo di avere una configurazione tale per cui un invitato ha 4 insiemi di tavoli adeguati e tutti e quattro con la stessa distanza d(S), quale insieme considero per il calcolo della pozizione ottimale dell'invitato? (è come nell'esempio del prof)
Io direi di considerare l'insieme con il tavolo inserito per prima, voi che dite?
Suppongo di sì. Comunque penso che adesso il problema maggiore sia capire quale struttura dati utilizzare per implementare il tutto :? |
| mitnik |
Si ma anche il controllo a spirale non è banale.
Per la struttura dati io penso di utilizzare delle liste; una per i tavoli, una per gli invitati messi in base all'ordine di arrivo. Ora vedrò .... |
| giuze80 |
Originally posted by mitnik
Si ma anche il controllo a spirale non è banale.
Per la struttura dati io penso di utilizzare delle liste; una per i tavoli, una per gli invitati messi in base all'ordine di arrivo. Ora vedrò ....
verissimo! la funzione che restituisce le coordinate dell'i-esimo step della visita a spirale non e' affatto banale, sto partendo da li' perche' credo che potrebbe essere uno dei nodi 'ammazza efficienza' del listato.....
per il resto, sono daccordo nell'implementare con una lista l'insieme degli invitati (che vanno aggiornati e si muovono secondo una logica FIFO), non altrettanto per i tavoli: non credo fosse indicato come significativo in nessun punto delle specifiche l'ordine di inserimento del tavolo....boh! iniziamo con la spirale.....
.....che belli che erano gli specchi!!!!! |
| dirkpitt |
Originally posted by mitnik
Per la struttura dati io penso di utilizzare delle liste; una per i tavoli, una per gli invitati messi in base all'ordine di arrivo. Ora vedrò ....
Niente RB-alberi? :?
Nonostante l'inserimento in una lista abbia un tempo di esecuzione minore rispetto agli RB-alberi (O(1) rispetto a O(lg n)), la ricerca (che dovrà essere eseguita abbastanza spesso) ha un tempo di esecuzione di TetaGrande(n) nelle liste e di O(lg n) negli RB-alberi (idem per la cancellazione).
Non ho però idea di come (e se) implementare le celle... |
| dirkpitt |
Originally posted by giuze80
verissimo! la funzione che restituisce le coordinate dell'i-esimo step della visita a spirale non e' affatto banale, sto partendo da li' perche' credo che potrebbe essere uno dei nodi 'ammazza efficienza' del listato.....
Certo, ma se prima non sai quale struttura dati utilizzare per le celle, potrebbe essere difficoltoso ideare un algoritmo per la visita a spirale da applicare su di esso. O sbaglio?
|
| dirkpitt |
Ma ogni singolo invitato, deve avere:
- nome : stringa
- posizione : coppia di valori (a,b) interi
- cibi : lista :?
Ma se ogni invitato ha una lista di cibi, l'insieme degli invitati diventa una lista (o un RB-albero) di invitati a loro volta contenenti una lista. Non è un po' pesante come cosa?
Inoltre: qualcuno conosce il tempo di elaborazione per ricerca, inserimento ed eliminazione in liste ordinate? |
| sirio |
Originally posted by dirkpitt
Ma ogni singolo invitato, deve avere:
- nome : stringa
- posizione : coppia di valori (a,b) interi
- cibi : lista :?
Ma se ogni invitato ha una lista di cibi, l'insieme degli invitati diventa una lista (o un RB-albero) di invitati a loro volta contenenti una lista. Non è un po' pesante come cosa?
Inoltre: qualcuno conosce il tempo di elaborazione per ricerca, inserimento ed eliminazione in liste ordinate?
Se la lista è ordinata nel caso peggiore cioè quando l'elemento che si sta cercando è nell'ultima posizione il tempo diventa n a cui aggiungi il tempo di inserimento o cancellazione che è costante, per cui alla fine si ha O(n)O(1)=O(n)
:-o |
| giuze80 |
Originally posted by dirkpitt
Certo, ma se prima non sai quale struttura dati utilizzare per le celle, potrebbe essere difficoltoso ideare un algoritmo per la visita a spirale da applicare su di esso. O sbaglio?
beh, si', ma credo che non usero' nessuna struttura per la cella!!! o meglio, se noti, operativamente cella e punto sono omogenei (due coordinate, stop), quindi possono essere gestite allo stesso modo; se sai che il commensale <i>i</i> sta nel punto (o cella :) di coordinate (x,y) la tua ricerca a spirale puo partire considerando incrementi unitari, senza bisogno di fare riferimenti ad altre strutture. no?
Inoltre non capisco l'esigenza di ordinare gli invitati per cibi di preferenza: l'unico ordinamento significativo per l'invitato e' quello di inserimento. Per i tavoli, riparliamone |
| mitnik |
Idee sulla spirale?
Io ci sto ragionando un po e mi sembra che possa venire una cosa molto dispendiosa in termini di tempo, perchè se lo spazio è indefinito, prima o poi il tavolo sarà inseribile quindi la struttura dati che contiene i tavoli continuerà a crescere e così anche il tempo di verifica. Certo che nel nostro utilizzo non si inseriscono molti tavoli però non si sa mai che nei test del prof ne vengano inseriti parecchi.
Bho |
| storm |
| ... non ho proprio idea di come fare la visita...sono ferma da 2 ore già...che palle sto progetto ! :? :cry: |
| yeffa |
qualcuno ha idee per la visita a spirale?
se c'è un gruppo di lavoro in laboratorio mi unisco subito
in modo da mettere assieme le idee.
ciao |
| giuze80 |
| boh! io mi sto facendo degli schemini, cerco delle regolarita', lo sto approcciando come un quesito della settimana enigmistica..... prima o poi emergera' qualcosa.... |
| sirio |
Da quello che leggo sul forum mi sembra che quasi tutti hanno già capito quale sia la struttura dati più efficente e soprattutto come gestire la ricerca di una cella che riguarda sia la posizione dei tavoli (e di tutte le celle vicine) che quella degli invitati.
:( |
| yoruno |
Intervento del moderatore:
Mmm.... ti riferivi a che thread esattamente? :D |
| bono vox U2 |
Ciao ragazzi!
qlc1 è riuscito a calcolare il baricentro di 1insieme di tavoli??? |
| storm |
| ....Visita a spirale :help: |
| dankan |
| Un grosso consiglio: pensate ad una struttura che sia di facile implementazione e non pensate ai tempi. |
| yeffa |
in pratica mi risulta (13,28,3) invece che (15,28,3) come
nell'esempio sul testo nel calcolo delle nuove coordinate
con il metodo a spirale
correggetemi se sbaglio o se è già stato notato questo
errore.
nel caso il risultato giusto sia (13,28,3) forse ho trovato
il modo per il calcolo a spirale.
GRAZIE! |
| dirkpitt |
Originally posted by yeffa
in pratica mi risulta (13,28,3) invece che (15,28,3) come
nell'esempio sul testo nel calcolo delle nuove coordinate
con il metodo a spirale correggetemi se sbaglio o se è già stato notato questo errore.
Nel caso il risultato giusto sia (13,28,3) forse ho trovato
il modo per il calcolo a spirale.
Brutte notizie, il calcolo del prof mi sembra corretto, ho provato a farlo graficamente e viene giusto! |
| mitnik |
ma voi usate due strutture diverse per tavolie celle oppure una sola considerando una cella come un tavolo di lato 1?
Poi come fate a verificare se un tavolo è inseribile o meno?
Ultima cosa, dove si trova il calcolo a spirale sul libro?
Grazie. Dobbiamo tenerci in "contatto" se vogliamo fare sto progetto malefico |
| sirio |
Originally posted by mitnik
ma voi usate due strutture diverse per tavolie celle oppure una sola considerando una cella come un tavolo di lato 1?
Poi come fate a verificare se un tavolo è inseribile o meno?
Ultima cosa, dove si trova il calcolo a spirale sul libro?
Grazie. Dobbiamo tenerci in "contatto" se vogliamo fare sto progetto malefico
Io ho pensato a una struttura per i tavoli e una per gli invitati, i tempi di ricerca non sono eccellenti, però è facile da capire e implementare. |
| mitnik |
che controlli fai per verificare se un tavolo è inseribile?
conreolli se le coordinate a,b sono gia presenti e poi?
della spirale sul libro sai niente? |
| sirio |
Originally posted by mitnik
che controlli fai per verificare se un tavolo è inseribile?
controlli se le coordinate a,b sono gia presenti e poi?
della spirale sul libro sai niente?
usando un albero di ricerca per il baricentro inizio la ric. poi controllo l'intorno. |
| yeffa |
sono riuscito a implementare la visita a spirale
ma ora ho grandi difficoltà con la creazione degli insiemi
di tavoli adeguati.Qualcun altro ha idee su come fare
questi insiemi?
Se qualcuno vuole sapere info sul calcolo spirale
posso darle
grazie |
| dirkpitt |
Originally posted by mitnik
che controlli fai per verificare se un tavolo è inseribile?
controlli se le coordinate a,b sono gia presenti e poi?
Controllo, non solo la cella data dalle coordinate (a,b), ma anche tutte quelle comprese all'interno dell'area del tavolo. Se almeno una cella è occupata da un altro tavolo o invitato, allora si effettua la visita a spirale (sempre tenendo conto di TUTTE le celle che costituiscono il tavolo).
Originally posted by yeffa
Se qualcuno vuole sapere info sul calcolo spirale
posso darle
Direi che la cosa non sarebbe male... :-D
Originally posted by yeffama ora ho grandi difficoltà con la creazione degli insiemi
di tavoli adeguati.
Spiega meglio il problema... |
| yeffa |
t 20 0 4 10 birra
t 40 20 4 10 birra
t 20 20 4 10 salsiccie
t 40 0 4 10 salsiccie
i bruno salsiccie birra
dalla lista dei tavoli con cibi che piacciono a bruno bisogna creare un insieme
{S1,S2,S3,S4}
dove :
S1=(20,0),(20,20)
S2=(20,0),(40,0)
S3=(40,20),(20,20)
S4=(40,20),(40,0)
ho grossi difficoltà a creare quest'insieme...la vedo dura,qulache idea?
ciao |
| yeffa |
l'idea di partenza :
calcolare i coefficienti(tra parentesi la posizione nell'array):
k=1 cf=1(1) ,0(2) ,-1(3)
k=2 cf=2(1) ,1(2) ,0(3) ,-1(4) ,-2(5)
usare questi coefficienti per incrementare(o decrementare) le coordinate (a,b)
es,parto da (20,20),k=1:
(20,21) = (a+cf[2],b+k)
(21,21) = (a+cf[1],b+k)
(21,20) = (a+k,b+cf[2])
(21,19) = (a+k,b+cf[3])
.........................ecc |
| bono vox U2 |
Ciao!
ank'io ho seri problemi con la creazione di insiemi adeguati! Ci sono fermo ormai da 6 ORE e nn riesco a trovare 1soluzione!
Il problema è k nn riesco a trovare l'algoritmo nel caso in cui l'invitato ha tanti cibi preferiti e ci sono tanti tavoli(qndi doppi o trili) con qsti cibi.
E' 1CASINOOOOO!!!
RAGAZZI QLC1 K LO ABBIA TROVATO MI DIA 1MANO!!!!! |
| yeffa |
io sono fermo da due giorni a forza di prove senza successo.
Se qualcuno vuole lunedi della settimana prossima ci si potrebbe trovare in laboratorio a Comelico.Io ci posso essere solo la mattina.
Attendo notizie dagli interessati
ciao |
| dinada |
Originally posted by yeffa
io sono fermo da due giorni a forza di prove senza successo.
Se qualcuno vuole lunedi della settimana prossima ci si potrebbe trovare in laboratorio a Comelico.Io ci posso essere solo la mattina.
Attendo notizie dagli interessati
ciao
Ciao, io ho sistemato la visita a spirale e gli invitati , ma sto sbattendo la testa sugli insiemi adeguati :?
direi che lunedì mattina in comelico io ci sarò :) |
| sirio |
Anche io sto sbattendomi un pò,
qualcuno sa come deve essere definita struct 'visita' presente quando si fa una ricerca simmetrica in un albero?
Sulle dispense de l prof non è descritta ma solo mensionata eppure a me da un errore di mancata referenziazione
:( |
| mitnik |
| Ciao, io sono bloccato sulla creazione degli insiemi adeguati, voi come ragionate per ottenerli? |
| sirio |
Per trovare l'insieme adeguato sto pensando a una struttuta ausiliari, es. lista cibi con dei puntatori ai tavoli, per cui se avrò un oggetto
struct cibo
char *c (cibo della lista)
puntatore prossimo cibo
puntatore tavolo
Confronto ogni cibo presente sul tavolo con il cibo della lista cibi se non è presente creo un nuovo elemento nella lista (con il cibo del tavolo)o cancello se un cibo non è più presente.
P.S. Non riesco a legg. da stan imput (anche se il file compila correttamente) mi potete dare qualche suggerimento. Sia nel tavolo che per gli invitati ho un puntatore a char, per cui ho:
tavolo(a,b,s,q,*c) |
| mitnik |
non mi è molto chiaro. Ma su un tavolo si trova massimo un cibo.
per leggere da standard input;
printf("inserisci.....\n");
scanf("%d %d %d %d %s\n",a,b,s,q,c); |
| sirio |
Vediamo se mi spiego meglio, nella lista cibi associo ad ogni cibo tutti i tavoli che contengono quel cibo. In realtà è solo un idea visto che non l'ho ancora realizzata :-(
**************************************************
**
Credo che il problema che ho sia in questa parte di codice
for( c=getchar() ; isspace(c);c=getchar());
switch(c){
case 'i':
if(c=='\n')
scanf("%d %d %d %d %s\n",a,b,s,q,cibo); |
| mitnik |
alcune domande:
se piu insiemi hanno la stessa distanza d(S), quale scelgo per i calcoli?
nell'esempio del prof, dopo aver eliminato con e 16 -2 come è possibile che bruno sia in 35 19?
Come implementate il calcolo di insiemi adeguati?
grazie |
| sirio |
| Ma qualcuno è riuscito a finirlo questo progetto? Io non ancora, la vedo veramente dura!!!! |
| inqbo |
| io sono a buon punto ma sono bloccato da un giorno e mezzo sul calcolo del baricentro... |
| bono vox U2 |
ragazzi io sono 1 di qlli k l'ha finito, proprio 10min fa!! e nn ci credo ancora ovviamente! ;)
Io direi di fare 1bel sondaggino, x vedere qnti siamo all'orale (qllo di giugno l'hanno consegnato IN 2!!!)...
ALZI LA MANO CHI L'HA FINITO!!! |
| bono vox U2 |
Qlc1 ha provato a testarlo??? ma a voi le celle vengono uguali all'output del prof o qlc1 diversa?? a me qlle diverse sono:
il primo Carlo -->42 -5 anzichè 41 -5
Anna --> -7 -5 anzichè -8 -6
Le ho fatte ank a mano su un foglio, e vengono così! nn è k ha cannato il prof??? |
| LazerPhEa |
| (Sorry, avevo detto una cazzata :D) |
| jekyll |
io mi sa che nn ho capito bene qlcosa...l'ho finito ma nn va molto :(
i problemi del prof xò sembrano sbagliati anche a me...
il primo tavolo è messo in 20,0 con semilato 4,qdi nn verrà mai spostato.
il pirmo invitato che fa visualizzare è: aldo 20 4....
ma scusa...il arriva fino a 24...si sovrappone....cosa sbaglio?!?!?! |
| jekyll |
scusate...l'ultima frase era:
il tavolo arriva fino a 24 (20 + semilato)..qdi si sovrappone...cosa sbaglio? |
| LazerPhEa |
| No, io l'ho finito e tutti i risultati mi vengono... magari prova a ricontrollare l'algoritmo per il movimento a spirale, oppure le condizioni da soddisfare affinchè due celle si sovrappongano. |
| yeffa |
Originally posted by bono vox U2
Qlc1 ha provato a testarlo??? ma a voi le celle vengono uguali all'output del prof o qlc1 diversa?? a me qlle diverse sono:
il primo Carlo -->42 -5 anzichè 41 -5
Anna --> -7 -5 anzichè -8 -6
Le ho fatte ank a mano su un foglio, e vengono così! nn è k ha cannato il prof???
-----------------------
anche a me viene (42,5).Mi puoi spiegare dove sbaglio??
L''invitato carlo deve scegliere tra la posiz (40,3)dist=30 e la (39,-3)dist=70.
Devo scegliere la (40,3) perchè ha distanza minima,ma probabilemente ho capito male il testo.qualcuno me lo può spiegare?
grazie |
| PuNk-MaD |
Per quelli di voi che consegneranno il progetto ad Aguzzoli .
Ragazzi oggi è il giorno della consegna quanti siamo a consegnarlo? |
| giuze80 |
io credo di doverlo consegnare a Fiorenti, comunque oggi....
....sono un po' sul filo del rasoio, ma forse riesco a mandarlo.
Sapete se ci sono problemi se la copia cartacea non la consegno oggi (non riesco a venire giu')?
Tanto se gli mando lo zip e non cambio nulla....
o no? |
| inqbo |
| io ho chiesto ad aguzzoli via mail e mi ha detto che il cartaceo posso portarlo domani, l'importante è consegnare il progetto oggi |
| inqbo |
ma chi è al primo turno dovrà spedire il progetto a fiorenti@dsi.... com'è scritto nel testo oppure ad aguzzoli??
grazie |
| sirio |
Ciao a tutti, visto che non ho completato il progetto in tempo propongo di organizzare un gruppo di studio con l'obiettivo di risolvere insieme i problemi incontrati, credo di non essere l'unico ad averne!!!
Comunque a settembre dovremo affrontare un'altro progetto ed aiutarsi vicendevolmente non mi sembra una brutta idea. :-) |
| bono vox U2 |
Ciao ragazzi,
qnti fanno l'orale e qndo (data e ora) e dove così si viene a vedere com'è l'orale e ci si fa 1idea??? |
|
|
|
|
