 | |
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]Progetto Zoom
Clicca QUI per vedere il messaggio nel forum |
| fasa |
| io via mail ho gia consegnato!la copia cartacea mi ha spiegato aguzzoli che la posso portare anche successivamente l'importante ora è la copia via mail!!! |
| Polo |
| Be una buona notizia a voi da 1 a 10 quanto funziona il programma con gli input delle consegne? |
| aghito |
consegne 10
test dsy 10 |
| ghily |
help please
perchè quest istruzioni:
p -> next = stk -> top;
stk -> top = stk -> top -> next;
mi generano questo errore:
[Warning] assignement from incompatible pointer type
le variabili sono tutti puntatori, come si vede sul libro di algo....
se riesco a fare questo ho tutto pomeriggio per fare la funzione blocchi e stasera posso vedere il mio amore. Abbiate pietà...
:help:
chao
roby |
| fasa |
| ma come sono dichiarati ste cose? |
| ghily |
Originally posted by fasa
ma come sono dichiarati ste cose?
ho risolto, grazie. Infatti era un problema di dichiarazione.Ora devo risolvere un altro problema (olte a quello della funzione blocchi()): come faccio a reimpostare tutti i flag uguali a zero senza stare ad andare a vedere tutti gli elementi???
grazie
chao
Roby |
| fasa |
| nn credo tu possa far...devi reimpostare il flag elemento per elemento....cmq tutti sto flag usate....ma si può sapere a cosa vi serve?io nn ne uso neanche uno!la mia struttura è semplicissima...2 variabili di tipo int x le coordinate e un puntatore per puntare all'elemento successivo della lista e questo mi basta per implementare tutte le richieste del programma!!!! :) |
| aghito |
be per esempio io uso un flag per sapere se la kcella è piena e uno per sapere a che blocco appartiene..così ho solo la lista di 1celle e quella di kcelle..
se mi serve sapere le kcelle occupate faccio una scansione prendendo solo quelle col "flag" occupata a 1.
e poi non uso una struttura per i blocchi.
sono scelte e basta....
secondo voi bisogna liberare tutto prima di uscire o lo fa automaticamente?
cosa vi viene a voi con questo input?
c 5 2 6
c 25 3 5
c 25 3 5
i 1 2
i 1 2
i 1 3
i 2 4
i 5 5
i 5 6
i 5 7
i 6 5
b
e 0 0
e 1 1
e 2 0
R 1
i 1 2
i 1 2
i 1 3
i 2 4
e 0 0
p 1 0
a 1 0
b
c 25 3 5
i 1 2
i 1 2
i 1 3
i 2 4
i 5 5
i 5 6
i 5 7
i 6 5
e 0 0
f
a me
b:1
p:0
a:0
b:1 |
| Dante |
grazie fasa, però sn riuscito a far funzionare (testati) area e peso usando i flag.
Ora nn riesco a far funzionare blocchi. Il primo problema è che ho sì un lista di kcelle, ma, a differenza della funzione area, nn ho una 1-cella di partenza come in a (x y)... così ho deciso di chiamare la funzione area con la prima 1-cella della lista delle 1-celle fino a che una di queste appartiene ad un kblocco.
A questo punto vedo se ci sono kcelle fuori dal blocco trovato. Se ci sono chiamo la funzione area su di loro... finchè nn ci sn più k celle senza un kblocco di riferimento. Ah, ogni volta che chiamo area l'effetto è quello di segnarle con un flag, cmq, anche se nn appartengono a un kblocco...
il problema è questo flag: per il primo kblocco che trovo il flag è 2, poi, dal secondo in avanti dovrebbe incrementarsi di 1 (quindi diventa 3), in modo da poter distinguere gli eventuali blocchi diversi alla fine e trovare il num ero di blocchi...
Nn mi riesce quest'ultima cosa: la numerazione con numeri diversi e quindi la rilevazione alla fine... UFFAAAAA!!!! mi manca solo questo.........................................................................!!!!!!!!! |
| Dante |
grazie fasa, però sn riuscito a far funzionare (testati) area e peso usando i flag.
Ora nn riesco a far funzionare blocchi. Il primo problema è che ho sì un lista di kcelle, ma, a differenza della funzione area, nn ho una 1-cella di partenza come in a (x y)... così ho deciso di chiamare la funzione area con la prima 1-cella della lista delle 1-celle fino a che una di queste appartiene ad un kblocco.
A questo punto vedo se ci sono kcelle fuori dal blocco trovato. Se ci sono chiamo la funzione area su di loro... finchè nn ci sn più k celle senza un kblocco di riferimento. Ah, ogni volta che chiamo area l'effetto è quello di segnarle con un flag, cmq, anche se nn appartengono a un kblocco...
il problema è questo flag: per il primo kblocco che trovo il flag è 2, poi, dal secondo in avanti dovrebbe incrementarsi di 1 (quindi diventa 3), in modo da poter distinguere gli eventuali blocchi diversi alla fine e trovare il num ero di blocchi...
Nn mi riesce quest'ultima cosa: la numerazione con numeri diversi e quindi la rilevazione alla fine... UFFAAAAA!!!! mi manca solo questo.........................................................................!!!!!!!!! |
| Dante |
grazie fasa, però sn riuscito a far funzionare (testati) area e peso usando i flag.
Ora nn riesco a far funzionare blocchi. Il primo problema è che ho sì un lista di kcelle, ma, a differenza della funzione area, nn ho una 1-cella di partenza come in a (x y)... così ho deciso di chiamare la funzione area con la prima 1-cella della lista delle 1-celle fino a che una di queste appartiene ad un kblocco.
A questo punto vedo se ci sono kcelle fuori dal blocco trovato. Se ci sono chiamo la funzione area su di loro... finchè nn ci sn più k celle senza un kblocco di riferimento. Ah, ogni volta che chiamo area l'effetto è quello di segnarle con un flag, cmq, anche se nn appartengono a un kblocco...
il problema è questo flag: per il primo kblocco che trovo il flag è 2, poi, dal secondo in avanti dovrebbe incrementarsi di 1 (quindi diventa 3), in modo da poter distinguere gli eventuali blocchi diversi alla fine e trovare il num ero di blocchi...
Nn mi riesce quest'ultima cosa: la numerazione con numeri diversi e quindi la rilevazione alla fine... UFFAAAAA!!!! mi manca solo questo.........................................................................!!!!!!!!! |
| pincopallino |
Originally posted by aghito
cosa vi viene a voi con questo input?
c 5 2 6
c 25 3 5
c 25 3 5
i 1 2
i 1 2
i 1 3
i 2 4
i 5 5
i 5 6
i 5 7
i 6 5
b
e 0 0
e 1 1
e 2 0
R 1
i 1 2
i 1 2
i 1 3
i 2 4
e 0 0
p 1 0
a 1 0
b
c 25 3 5
i 1 2
i 1 2
i 1 3
i 2 4
i 5 5
i 5 6
i 5 7
i 6 5
e 0 0
f
a me
b:1
p:0
a:0
b:1
anche a me viene:
1
0
0
1
ma avevo un bug che ho trovato grazie al tuo input....io però non gestisco le righe vuote secondo voi è un problema?
ho usato una lista di adiacenza dove memorizzo k_celle e rispettive celle che le "occupano", poi ho usato tre variabili globali una per la lista di k_celle, una per k ed una per il parametro di riempimento |
| pincopallino |
Originally posted by aghito
cosa vi viene a voi con questo input?
c 5 2 6
c 25 3 5
c 25 3 5
i 1 2
i 1 2
i 1 3
i 2 4
i 5 5
i 5 6
i 5 7
i 6 5
b
e 0 0
e 1 1
e 2 0
R 1
i 1 2
i 1 2
i 1 3
i 2 4
e 0 0
p 1 0
a 1 0
b
c 25 3 5
i 1 2
i 1 2
i 1 3
i 2 4
i 5 5
i 5 6
i 5 7
i 6 5
e 0 0
f
a me
b:1
p:0
a:0
b:1
anche a me viene:
1
0
0
1
ma avevo un bug che ho trovato grazie al tuo input....io però non gestisco le righe vuote secondo voi è un problema?
ho usato una lista di adiacenza dove memorizzo k_celle e rispettive celle che le "occupano", poi ho usato tre variabili globali una per la lista di k_celle, una per k ed una per il parametro di riempimento |
| pincopallino |
| grazie aghito per il test...ho trovato un buggino nel mio programmino....cmq ora che ho risolto i risultati mi vengono come i tuoi |
| aghito |
| l'ho postato apposta perchè immaginavo di non essere il solo a trovare quel bug |
| ghily |
ragazzi una domanda:
ma l'output del prof a voi viene giusto??
Perchè a me la k-cella (5; 2,0) non la elimina perchè è occupata da tre celle e il parametro di riempimento è 4. Dove sbaglio???
:pccrash:
Ormai non penso di finirlo, quindi esco a divertirmi e domani a pranzo sono fuori.
Aguzzoli ci vediamo a gennaio :matrix:
Chao
Roby |
| contezer0 |
Originally posted by fasa
nn credo tu possa far...devi reimpostare il flag elemento per elemento....cmq tutti sto flag usate....ma si può sapere a cosa vi serve?io nn ne uso neanche uno!la mia struttura è semplicissima...2 variabili di tipo int x le coordinate e un puntatore per puntare all'elemento successivo della lista e questo mi basta per implementare tutte le richieste del programma!!!! :)
azpita! complimenti!
io e' un po' che ottimizzo ma uso comunque un po' di altra roba....
ma quindi ad esempio per calcolare il numero di blocchi, quante volte scorri questa lista? |
| contezer0 |
Originally posted by fasa
nn credo tu possa far...devi reimpostare il flag elemento per elemento....cmq tutti sto flag usate....ma si può sapere a cosa vi serve?io nn ne uso neanche uno!la mia struttura è semplicissima...2 variabili di tipo int x le coordinate e un puntatore per puntare all'elemento successivo della lista e questo mi basta per implementare tutte le richieste del programma!!!! :)
azpita! complimenti!
io e' un po' che ottimizzo ma uso comunque un po' di altra roba....
ma quindi ad esempio per calcolare il numero di blocchi, quante volte scorri questa lista? |
| VdM |
Terminato il progetto, ora mi son bloccato sulla documentazione:
in pratica ho utilizzato 2 tabelle di hash, una per le 1-celle e una per le k-celle. I tempi di inserimento e rimozione sono oltremodo efficienti. Il calcolo dell'area, peso e blocchi avviene sulla tabella di k-celle. Supposto che vi siano di norma più inserzioni/cancellazioni/modifiche che non richiame ad area,pesi e blocchi, alla chiamata di queste ultime operazioni eseguo la ricerca "al volo" delle k-celle adiacenti per ogni k-cella, controllando per ogni k-cella nell'intorno delle 8 adiacenti (se esistono); ogni cella così trovata, se non ancora visitata, viene posta in una coda ausiliaria; vengono così "espanse" le celle trovate per prime. Se la coda si svuota, vuol dire che non abbiamo più k-celle adiacenti. Ogni elemento rimosso dalla coda è marcato come "visited" nella k-tabella hash, per cui viene escluso da ulteriori ricerche.
La cosa funge (i test sono ok); per i k-blocchi basta iterare sulla k-tabella finchè ci sono k-celle piene e non ancora visitate.
Il prolema che mi si pone è il calcolo del tempo di esecuzione: a "manina" infatti risulterebbe quadratico (credo che incida la ricerca al volo delle celle adiacenti). Purtroppo 'sto tempo sembra dipendere da parecchi fattori: in primis la risoluzione impostata, poi la distribuzione dei blocchi, nonchè (la +ostica) la continua espansione/contrazione della coda...
Su quache riferimento ho trovato un algoritmo simile, di tempo O(d^2 * N^2), dove d è una costante (nel mio caso, 1/k, la risoluzione...). Ovviamente per d piccolo (= k grande) e N grande, l'algo viene praticamente considerato lineare... Ma io come diavolo lo recupero e lo scrivo il presunto tempo di esecuzione?? Gia' non ci ho dormito tutta notte, se qualcuno ha suggerimenti...
Grazie e buona domenica a tutti :)
Gabriele |
| Dante |
Caro ghily siamo in 2...
anche a me gli output del prof nn risultano più dopo r (25 4)... e le mie funzioni area e peso sono giuste... le ho provate con altri input... mah...
ci rinuncio e ripasso a gennaio... (che avrò anche reti e basi) ma è la quarta volta che ci provo... e se nn lo passo a gennaio devo rifare lo scritto........ ma siamo matti? |
| Polo |
anche a me dava l'errore di Dante. l'ho risolto mettendo in una variabile di tipo double il risultato di k * k * r (r è p/q)
perchè altrimente con alcuni valori ,25 4 ad esempio con k = 5,si mangiava can la variabile di tipo int il resto della virgola trasformando per esempio un 2,9 in 2. |
| Dante |
| Eh, ma cmq nn si deve arrotondare per difetto? |
| ghily |
Originally posted by Dante
Eh, ma cmq nn si deve arrotondare per difetto?
io non ho arrodontato per difetto. Ho approssimato all'intero più grande (non so il perchè ma almeno così il risultato veniva più vicino a quello del prof). Il fatto che tu ci abbia provato altre quattro volte non mi metto di buonumore.... A me alla fine mancava solo la funzione blocchi.Ma ormai è troppo tardi. Anche io a gennaio devo fare sia reti che basi.In più devo fare anche informatica grafica. :shock:
In bocca al lupo a chi ha consegnato e fateci sapere quali erano le strutture migliori. Almeno impariamo qualche cosa anche se non consegnamo.
Chao
Roby |
| contezer0 |
Originally posted by Polo
anche a me dava l'errore di Dante. l'ho risolto mettendo in una variabile di tipo double il risultato di k * k * r (r è p/q)
perchè altrimente con alcuni valori ,25 4 ad esempio con k = 5,si mangiava can la variabile di tipo int il resto della virgola trasformando per esempio un 2,9 in 2.
azpita ragazzuoli!
avevo postato un metodo per fare tutto con gli interi che funziona
egregiamente, qualche pagina fa...
se e' solo per quello che non consegnate e' davvero un peccato!!!
io sto per mandare...l'ho finito da un po' ma mi sono impantanato sulla relazione :)
riassumendo....ecco i miei costi
inserimento O(lgN)
eliminazione O(lgN)
cambio riempimento O(N)
cambio risoluzione O(N)
blocchi aree e peso O(N) |
| ghily |
Originally posted by contezer0
azpita ragazzuoli!
avevo postato un metodo per fare tutto con gli interi che funziona
egregiamente, qualche pagina fa...
se e' solo per quello che non consegnate e' davvero un peccato!!!
io sto per mandare...l'ho finito da un po' ma mi sono impantanato sulla relazione :)
no, non era solo quello. Anche la funzione blocchi non sapevo come farla. Per area e peso ho scritto una ritondante procedura molto brutta. Insoma era olto brutto. Poi visto che avevo un 27 nella teoria mi dispiaceva perderlo con un progetto mediocre.
Amen
Chao
Roby |
| fasa |
io nella funzione blocchi la listA delle kcelle la scorro solo una volta....prendo il primo elemento e ricreo tramite una funzioncina il blocco(qui riscorro ovviamente la lista delle kcelle) a cui appartiene la metto in una lista d'appoggio e incremento un contatore,poi prendo la seconda kcella e vedo se c'è nella lista d'appoggio,se nn c'è richiamo ancora la funzioncina crea blocchi e la lista creata la concateno con la precedente lista appoggio e incremento ancora cont se invece c'era nn fa niente e passa alla nuova kcella.
tempo di esecuzione al max O(n^2).
l'unico problema del mio codice sono appunto i tempi di esecuzione che potrebbero essere migliorati anche se xò nn vedo come si possa migliorare inserendo solo un flag nella struttura delle celle.... |
| fasa |
in pratica la mia soluzione ha:
-una struttura per le celle(1celle o kcelle che siano),formata da 2 var di tipo int e un puntatore di tipo celle al prox elemento
-2 liste(1 x le 1celle e 1 x le kcelle)globali
-3 var globali(1 per k 1 per p e 1 per q)
-le funzioni richieste dal problema
-2 funzioncine di supporto,1 per calcolare la lista delle kcelle quando inserisco una 1cella oppure quando cambio il fattore di riempimento oppure quando cambio la risoluzione
e 1 per crearmi la lista del blocco per la kcella richiesta. |
| fasa |
| chi ha consegnato come ha implementato il progetto? |
| contezer0 |
Originally posted by fasa
chi ha consegnato come ha implementato il progetto?
io lo racconto domani...o fra 4 ore :)
comunque posso anticipare che nell'applicazione reale, su sequenze di comandi abbastanza lunghe (piu' di 10mila) il mio progetto batte anche il costo logaritmico :)
spero solo di cavarmela altrettanto bene all'orale |
| contezer0 |
A proposito...io ho scritto anche un generatore di input...domani c'e' qualcuno in silab? facciamo dei test incrociati di velocita' su
input giganteschi? |
| ghily |
Originally posted by contezer0
A proposito...io ho scritto anche un generatore di input...domani c'e' qualcuno in silab? facciamo dei test incrociati di velocita' su
input giganteschi?
noooooooooooooooooooo
ho risolto il problema........ Era sbagliata la funzione di elimina. Ora ho due ore per scrivere la funzione blocchi, il main e la relazione
ci provo lo stesso....
ma c'è anche l'inter........ |
| contezer0 |
Originally posted by fasa
io nella funzione blocchi la listA delle kcelle la scorro solo una volta....prendo il primo elemento e ricreo tramite una funzioncina il blocco(qui riscorro ovviamente la lista delle kcelle) a cui appartiene la metto in una lista d'appoggio e incremento un contatore,poi prendo la seconda kcella e vedo se c'è nella lista d'appoggio,se nn c'è richiamo ancora la funzioncina crea blocchi e la lista creata la concateno con la precedente lista appoggio e incremento ancora cont se invece c'era nn fa niente e passa alla nuova kcella.
tempo di esecuzione al max O(n^2).
la funzione crea blocchi che complessita' ha? |
| fasa |
| Per contezer0:La mia funzione creablocchi ha complessità O(n^2)perchè? |
| contezer0 |
Originally posted by fasa
Per contezer0:La mia funzione creablocchi ha complessità O(n^2)perchè?
se la chiami al piu' n volte allora la complessita' totale della funzione che conta i blocchi non e' n^3? |
| fasa |
| mi hai fatto venire un dubbio e sono andato a ricontrollare...e hai ragione è n^3! |
| fasa |
| una domanda...3cicli annidati che vanno tutti da 1 a n danno come costo n^3?giusto? |
| contezer0 |
comunque domani rilascio il codice per chiunque voglia dare un'occhiata o suggerirmi qualche miglioramento...anche comincia a venirmi un po' di nausea :)
in ogni caso...sarebbe interessante verificare i vari tempi di
esecuzione dei nostri progetti su input uguali e di dimensioni
significative...che dite? facciamo un "torneo"? se non siete
troppo gelosi dei vostri sorci e me li spedite, domani in laboratorio
faccio qualche esperimento e posto qua i risultati!
sono piuttosto curioso di far gareggiare il mio con quello(i) basato(i) su tabelle hash! |
| contezer0 |
Originally posted by fasa
una domanda...3cicli annidati che vanno tutti da 1 a n danno come costo n^3?giusto?
penso proprio di si...se due cicli danno n^2, ne annidi un altro e moltiplichi ancora per n |
| fasa |
| grazie contezer.per quanto riguarda i tempi io credo di nn essere un gran che però la struttura che ho usato è semplicissima da implementare e questo mi piace! |
| aghito |
PANICO!!
stavo trasformando la relazione in pdf finita la partita ma acrobat ha crashato..riavvio e non parte più il pc!!!
ho provato varie volte ma niente.non mi mostrava niente a parte una schermata blu..alla fine da li l'unica cosa che va è il task manager.killando il processo explorer poi si è ripreso...nel frattempo avevo spedito le cose dal pc di mio zio che abita 2 piani sotto...
che paura però!!
ciao |
| contezer0 |
ola'!
spero di non aver fatto una vaccata a postare il mio progetto in area filez a soli 20 minuti dalla scadenza...ma ormai i giochi son fatti no?
a richiesta posso anche fornire la versione grafica, ma quest'ultima fuziona solo sotto linux/unix con X11 e non in console |
| sirio |
| Non si sa ancora nulla......, mi tocca consegnare il cartaceo senza sapere se l'ho passato :-( |
| d0k |
Ho consegnato, per la discussione dove come quando? Qualcuno sa info a riguardo???
d0k |
| aghito |
| bella fiorentini mi ha risposto che funziona il mio programma!!! |
| bat-erika |
Anche a me ha detto che funziona.
C'è qualcuno che sa qualcosa riguardo alle date della discussione?
Non è che tutti abbiamo espresso la stessa preferenza vero? :D |
| skorpius |
| credo che per le date bisogni tenere d'okkio il sito di Fiorentini.... |
| sirio |
Ok sono uscite le date sul sito di fiorentini.
Non ho capito una cosa, ma il progetto si discute sempre? Oppure si baypassa e si va direttamente all'orale con Torelli? |
| daddyrho |
Originally posted by sirio
Ok sono uscite le date sul sito di fiorentini.
Non ho capito una cosa, ma il progetto si discute sempre? Oppure si baypassa e si va direttamente all'orale con Torelli?
Ma x le date di Aguzzoli si sa qualcosa?:? |
| Eruyomë |
Qualcuno ha già fatto l'orale con Aguzzoli e sa dire, per favore, che genere di orale sia?
Del tipo per vedere se hai copiato, orale tranquillo o un po' più impegnativo? |
| Lunik |
Originally posted by contezer0
ola'!
spero di non aver fatto una vaccata a postare il mio progetto in area filez a soli 20 minuti dalla scadenza...ma ormai i giochi son fatti no?
ehm infatti è stato tolto xè il progetto era ancora in corso... anche se mancavano 20 minuti, è il regolamento.
cmq quando il prof dirà che nessun altro può consegnare il progetto, ripostalo pure...
ciao! :) |
| daddyrho |
| Calendario orali Prof. Aguzzoli link |
| Polo |
| ma anche Aguzzoli manda le Mail se il progetto funziona perchè a me non è ancora arrivato nulla??? |
| Bloody |
Originally posted by Eruyomë
Qualcuno ha già fatto l'orale con Aguzzoli e sa dire, per favore, che genere di orale sia?
Del tipo per vedere se hai copiato, orale tranquillo o un po' più impegnativo?
non e' per niente impegnativo..... ti fa praticamente rifare su carta gli algoritmi che hai implementato in c e ti chiede alcuni dettagli sul loro funzionamento, niente di impossibile, vai tranquillo! |
| Eruyomë |
| grazie, ah anche a me non ha rispedito nulla Polo |
| beyonce_21 |
| invece l'orale di fiorentini e torelli com'è ? |
|
|
|
|
