 | |
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 "RICHIAMI"
Clicca QUI per vedere il messaggio nel forum |
| Teju |
Originally posted by p2p
e secondo te si legge il codice di tutti?
io allo scorso progetto avevo fatto un paio di errori correggibili con l' aggiunta di 1 riga di codice,era uno sbaglio su un controllo di stringhe ... beh, me l ha rifiutato!se l' avesse letto probabilmente si sarebbe accorto che l' output era errato per una banalita', non credi?
Sottoscrivo: non legge il codice ne' la relazione... :D
Sul codice mi spiace, xkè l'avevo messo tuto bene, sulla relazione un po' meno xkè l'avevo scritta proprio alla cane!! :D :D |
| LjL |
Originally posted by Skilotto83
Il problema era quello...
solo ke è un kaso limite..siete sikuri ke va konsiderato spostamento...??
Non è il kaso si mandare una mail al prof??
io il progetto lo faccio con aguzzoli e nn con fiorentini...il mio progetto nn dice nulla a riguardo...
Sicuro sicuro sicuro non lo posso essere, però per quanto mi riguarda un caso limite è un caso valido a meno che non venga detto esplicitamente il contrario...
Se vogliamo parlare di casi limite, io considero anche gli ostacoli che degenerano in rette o punti come validi. |
| LjL |
Originally posted by Teju
Sottoscrivo: non legge il codice ne' la relazione... :D
Sul codice mi spiace, xkè l'avevo messo tuto bene, sulla relazione un po' meno xkè l'avevo scritta proprio alla cane!! :D :D
Ma comunque non c'è la famosa "discussione del progetto"? Il che dovrebbe significare che almeno durante quella una sbirciatina al codice e/o alla relazione dovrà pur darla...? |
| mattcobain |
Originally posted by LjL
Sicuro sicuro sicuro non lo posso essere, però per quanto mi riguarda un caso limite è un caso valido a meno che non venga detto esplicitamente il contrario...
Se vogliamo parlare di casi limite, io considero anche gli ostacoli che degenerano in rette o punti come validi.
idem...anchio considero tutti i casi limite, compresi ostacoli che possono essere rette oppure punti....dopotutto dalla descrizione matematica che ha dato di ostacoli, anche questi casi ne rientrano e quindi non li considererei nemmeno caso limite, ma casi da trattare....
per il segnale che può trovarsi in un punto già occupato da un automa, anche questo non mi sembra un caso limite...infatti sul testo si dice esplicitamente che il segnale non può trovarsi all'interno o sul bordo di un ostacolo (altrimenti non sarebbe raggiungibile da nessun automa) e non si dice nient'altro....quindi dato che automi possono trovarsi sullo stesso punto, penso proprio che anche un segnale possa trovarsi nella posizione già occupata da un ostacolo....
cmq ormai ho stampato il codice, 14 pagine, non ho alcuna voglia di contattare il prof e chiedergli conferma....ho fatto così e amen! :D non mi sembra affatto un errore, piuttosto un controllo in piu! |
| virtual |
Quanto impiega il vostro programma ad eseguire tutto l'input delle specifiche?
Il mio 37 secondi su PIII 1GHz. |
| Teju |
Originally posted by LjL
Ma comunque non c'è la famosa "discussione del progetto"? Il che dovrebbe significare che almeno durante quella una sbirciatina al codice e/o alla relazione dovrà pur darla...?
Il prof prende il vostro codice, lo compila, prova diversi input che si è precedentemente preparato, si assicura che il programmino funzioni con tutti, poi, all'orale, ti chiede come hai implementato certe funzioni e lì, insieme a te, magari da un occhio al codice...:shock: |
| Teju |
Originally posted by Teju
Il prof prende il vostro codice, lo compila, prova diversi input che si è precedentemente preparato, si assicura che il programmino funzioni con tutti, poi, all'orale, ti chiede come hai implementato certe funzioni e lì, insieme a te, magari da un occhio al codice...:shock:
Ecco, mi è venuto in mente: per darvi la certezza di quanto detto! L'appello scorso un mio amico che aveva implementato un metodo di collisioni automi-blocchi molto bello, è riuscito a prendere decisamente meno di un altro che faceva un for con il controllo su ogni spostamento di uno di un automa rispetto a una lista dove si trovavano gli ostacoli, ovvero x ogni spostamento di n, faceva n controlli di collisione contro l'1 del mio compagno...
L'altro è riuscito a intortarsi meglio il prof e ha preso decisamente di più.... |
| Skilotto83 |
Allora modifiko anke io il codice considerando buona la situazione di automa sul punto di segnale...
Per i tempi di esecuzione.....
Virtual...
Kome fai a calcolare il tempo?
Dopo ke hai battuto il komando fai partire il cronometro???
Ma siamo proprio sikuri ke l'out deve essere kome ho gia' kiesto, e quindi bisogna andarselo a guardare tra i vari komandi dati???
Non è ke voleva memorizzassimo l'out per poi darlo tutto insieme con il comando 'f'??
Kmq...io ho fatto un programmino di input in VisualBasic...gli passo il file da linea di comando....
il mio è istantaneo in tutte le operazioni....anche con i famosi input da -10000 etc etc...quindi direi che il tempo è quello del programmino per inserire input...nn attendo mai il risultato di un calcolo...sara' ke l'algoritmo per il calcolo del percorso e tortuosita' è una bomba...:D
Certo che ci pensavo ieri...chi ha risolto con ricerca esaustiva su una ricerca di percorso da (-10000,-5000) a (10000,5000) ci mette un botto....deve spararsi migliaia di celle...
Ma la relazione???
Kome la fate???
Mettete parti di codice?? Fate il calcolo preciso di tutte le procedure? Oppure una cosa alla buona?? |
| Teju |
Originally posted by Skilotto83
Allora modifiko anke io il codice considerando buona la situazione di automa sul punto di segnale...
Per i tempi di esecuzione.....
Occhi che cmq sia ANSI-C! :-D Usa il Gcc come compilatore lui...
Originally posted by Skilotto83
Ma la relazione???
Kome la fate???
Mettete parti di codice?? Fate il calcolo preciso di tutte le procedure? Oppure una cosa alla buona??
Descrizione della struttura dati utilizzata, con motivazione "sensata", e brevissima descrizione di ogni procedura scritta. |
| elpampero |
io faccio così:
richiami<input.txt
e in output ho esattamente quello che devo avere... |
| Skilotto83 |
Originally posted by Teju
Occhi che cmq sia ANSI-C! :-D Usa il Gcc come compilatore lui...
Descrizione della struttura dati utilizzata, con motivazione "sensata", e brevissima descrizione di ogni procedura scritta.
infatti devo controllare...
io ho fatto tutto con visual studio...dovrebbe essere ok no??
e ho anche diviso il prog in 4moduli .c ...
main.c, automi.c ostacoli.c totuosita'.c....
e i 3 moduli automi.h, ostacoli.h tortuosita'.h...
dovrebbe andar bene...no?? |
| mark |
Originally posted by virtual
Quanto impiega il vostro programma ad eseguire tutto l'input delle specifiche?
Il mio 37 secondi su PIII 1GHz.
cosa impiega 37 secondi ? |
| p2p |
Virtual anche io ho un P3 1Ghz con 512 Mb di Ram ma mi impiega pochi secondi a far girare il tutto, l unico problema è l' istruzione
t 1000 2000 01 che mi manda probabilmente in loop la ricorsione... pero' spero di riuscire a correggerlo, il resto è ok |
| Skilotto83 |
raga..aiuto...
Ho scaricato gcc per compilare il mio progetto...
se uso il comando gcc -o etc etc...tutto bene...compila e funziona...
se invece uso gcc -ansi -o etc etc....succede un disastro...200 errori!!!!!!!!!
Ke kazzo è????
Deve compilare giusto con il comando -ansi??? |
| virtual |
Originally posted by Skilotto83
Virtual...
Kome fai a calcolare il tempo?
Con la libreria <time> |
| elpampero |
| Skilotto controlla che i commenti siano /*XXX*/ e non // |
| p2p |
Originally posted by elpampero
Skilotto controlla che i commenti siano /*XXX*/ e non //
infatti con l opzione -ansi anche i commenti stile C++ vengono indicati come errore,inoltre alcune dichiarazioni di variabili interne a funzioni vengono segnalate.
Io ho compilato da subito con -Wall -ansi -pedantic per evitare questo genere di sorprese, cmq vedrai che sono stupidate,comincia dall' inizio con calma e non cambiare troppe cose in una volta sola,anzi fatti proprio un backup e lavora sulla copia... |
| Skilotto83 |
Originally posted by p2p
infatti con l opzione -ansi anche i commenti stile C++ vengono indicati come errore,inoltre alcune dichiarazioni di variabili interne a funzioni vengono segnalate.
Io ho compilato da subito con -Wall -ansi -pedantic per evitare questo genere di sorprese, cmq vedrai che sono stupidate,comincia dall' inizio con calma e non cambiare troppe cose in una volta sola,anzi fatti proprio un backup e lavora sulla copia...
infatti sono i commenti..si ma è assurdo...
kmq...cosa fa in piu' wall e pedantic?? |
| p2p |
| Wall e pedantic danno un sacco di info utili che magari con una compilazione normale non verrebbero notati,tipo passaggi di parametri o altro che ti fanno risparmiare un sacco di errori |
| Petrik22 |
scusate raga, ma come cazzo avete risolto il problema della gestione degli spostamenti degli automi in base al segnale?????
volgio dire, mi sono creato una lista con tutti gli automi e relative distanze dal segnale dato. Ora, come caxxo si fa a ordinare sta lista a seconda delle distanze per scegliere quelle minime???:?:?:?
secondo: come fate a evitare gli ostacoli???
:shock::shock::shock::shock::shock:
:wall: :pc: |
| Skilotto83 |
ok...basta ke nn servano per rispettare delle specifiche...
Tutte le info su passaggiu di paramentri etc le ho funzionalissime con visual studio...
Ora compila e linka corretto con:
gcc -ansi -o Richiami Automi.c Obsts.c Percorso.c Main.c
Quindi sono a posto..giusto??? |
| p2p |
Originally posted by Skilotto83
ok...basta ke nn servano per rispettare delle specifiche...
Tutte le info su passaggiu di paramentri etc le ho funzionalissime con visual studio...
Ora compila e linka corretto con:
gcc -ansi -o Richiami Automi.c Obsts.c Percorso.c Main.c
Quindi sono a posto..giusto???
giusto. -ansi per rispettare le specifiche ansi basta. |
| p2p |
Originally posted by Petrik22
scusate raga, ma come cazzo avete risolto il problema della gestione degli spostamenti degli automi in base al segnale?????
volgio dire, mi sono creato una lista con tutti gli automi e relative distanze dal segnale dato. Ora, come caxxo si fa a ordinare sta lista a seconda delle distanze per scegliere quelle minime???:?:?:?
secondo: come fate a evitare gli ostacoli???
:shock::shock::shock::shock::shock:
:wall: :pc:
basta che scorri la lista e mentre la scorri memorizzi in una var int la distanza minore, tipo:
nodo *p;
int minimo;
for (p=testa_lista; p!=NUL; p=p->next)
if(minimo > p->distanza)
minimo = p->distanza;
alla fine avrai in minimo il valore minimo tra le varie distanze,e li ti bastera' aggiornare le coordinate degli automi,quindi riscorri la lista e poni
if(p->distanza == minimo)
aggiorna le coordinate;
ti consiglio di fare un po di prove con printf nel ciclo for e printf dell valore finale per renderti conto se stai facendo bene. |
| Petrik22 |
bene, capito.
pero per la questione degli ostacoli come la mettete? |
| LjL |
Originally posted by Teju
Ecco, mi è venuto in mente: per darvi la certezza di quanto detto! L'appello scorso un mio amico che aveva implementato un metodo di collisioni automi-blocchi molto bello, è riuscito a prendere decisamente meno di un altro che faceva un for con il controllo su ogni spostamento di uno di un automa rispetto a una lista dove si trovavano gli ostacoli, ovvero x ogni spostamento di n, faceva n controlli di collisione contro l'1 del mio compagno...
L'altro è riuscito a intortarsi meglio il prof e ha preso decisamente di più....
Più che intortare, non è che (dubbio che mi stava giá venendo ieri) il prof prova il programma con un po' di input, come hai detto tu, e tutti questi input sono di dimensioni relativamente *piccole*?
Io ho cercato di fare in modo che il mio algoritmo fosse il più efficiente possibile *asintoticamente*, ma poi è chiaro che se gli dai in input tre valori in croce è meglio un programma scritto nel modo più banale possibil! |
| p2p |
Originally posted by LjL
Più che intortare, non è che (dubbio che mi stava giá venendo ieri) il prof prova il programma con un po' di input, come hai detto tu, e tutti questi input sono di dimensioni relativamente *piccole*?
Io ho cercato di fare in modo che il mio algoritmo fosse il più efficiente possibile *asintoticamente*, ma poi è chiaro che se gli dai in input tre valori in croce è meglio un programma scritto nel modo più banale possibil!
io non so se tu ambisci a un 30 ma ti assicuro che la cosa fondamentale è che funzioni e che dia l output corretto sui suoi esempi, vai a vederti qualche orale e poi dimmi tu... |
| LjL |
Originally posted by virtual
Con la libreria <time>
O semplicemente col comando "time" di Unix:
time ilmioprogramma <ilmioinput |
| LjL |
Originally posted by p2p
io non so se tu ambisci a un 30 ma ti assicuro che la cosa fondamentale è che funzioni e che dia l output corretto sui suoi esempi, vai a vederti qualche orale e poi dimmi tu...
Non è che ambisco al 30, però mi darebbe un po' fastidio l'idea di prendere *meno* punti con un programma più efficiente che con uno meno efficiente! :(
Certo che quello di andare a vedere qualche orale non è un cattivo consiglio... vedo grande saggezza in te ;) |
| LjL |
Originally posted by p2p
infatti con l opzione -ansi anche i commenti stile C++ vengono indicati come errore,inoltre alcune dichiarazioni di variabili interne a funzioni vengono segnalate.
[snip]
Notare però che i cosiddetti "commenti stile C++" sono previsti in C dallo standard C99. Non lo sono però dal C89, che per ora è ancora quello di riferimento per GCC.
Se vogliamo proprio cavillare, comunque, sul testo c'è scritto che il codice deve essere ANSI, non c'è scritto *quale* revisione dell'ANSI! :D |
| LjL |
Originally posted by virtual
Quanto impiega il vostro programma ad eseguire tutto l'input delle specifiche?
Il mio 37 secondi su PIII 1GHz.
Ehm... non per farti preoccupare ma mi sa che c'è qualcosa che potresti rivedere =)
Per quell'input il mio programma impiega circa un decimo di secondo, su un K6 a 350MHz.
Il mio programma comincia a non farcela più (gli manca RAM, ho 256Mb) quando si superano i 2000 automi o i 1000 ostacoli. |
| LjL |
Originally posted by Skilotto83
[snip]
Certo che ci pensavo ieri...chi ha risolto con ricerca esaustiva su una ricerca di percorso da (-10000,-5000) a (10000,5000) ci mette un botto....deve spararsi migliaia di celle...
[snip]
Sì, ma c'è da dire che o sono molto tonto io oppure riuscire a fare il calcolo *senza* una ricerca esaustiva non è proprio così facile! Adesso ci sono riuscito anch'io, ma ci ho messo veramente un bel po', e comunque la complessità in spazio e in tempo è O(n²), e sono sicuro che volendo si può diminuire... tu fai meglio di così? (tra l'altro O(n²) è per ogni automa; se devi far spostare tutti gli automi, O(n³)) |
| p2p |
voi avete un idea di perchè la mia funzione va in loop con t 1000 2000 01 mentre con tutti gli altri input va?
quale potrebbe essere la causa??
sto facendo un po' di prove con valori diversi e gia' un t 50 100 01 va in loop...va in loop per valori un po' troppo grossi...se sono piccoli ok altrimenti va in loop...:? |
| LjL |
Originally posted by p2p
voi avete un idea di perchè la mia funzione va in loop con t 1000 2000 01 mentre con tutti gli altri input va?
quale potrebbe essere la causa??
sto facendo un po' di prove con valori diversi e gia' un t 50 100 01 va in loop...va in loop per valori un po' troppo grossi...se sono piccoli ok altrimenti va in loop...:?
Non ne ho idea anche perché non so (e non voglio sapere!) che algoritmo usi... non so, prova il comando 't' sullo stesso automa con tutte le coordinate da 0 in poi (facendo in modo che il rettangolo descritto da automa e punto di richiamo sia un quadrato), e guarda qual è esattamente il punto in cui comincia a bloccarsi.
Se usi una funzione ricorsiva, potrebbe essere un problema di stack, altrimenti potrebbe essere comunque un problema di memoria di qualche genere (magari vai a scrivere dove non dovresti, ma per input piccoli le probabilità che il sistema se ne accorga sono basse).
Potrebbe esserti d'aiuto un debugger.
Tra l'altro per fare prove con input un po' grossi ti consiglio il mio programmino, che se per altri tipi di test non è un granché, sulla "quantità" è abbastanza utile :) |
| elpampero |
| scusate ma su windows come faccio a calcolarmi il tempo di esecuzione? |
| LjL |
Originally posted by elpampero
scusate ma su windows come faccio a calcolarmi il tempo di esecuzione?
O ti guardi come si usano le funzioni che sono state citate, oppure
http://groups-beta.google.com/group...da01bf1525cc09a
Anche se così ad occhio non mi sembra un approccio di gran precisione. |
| elpampero |
il problema è che se io faccio
TIME programma<input mi da come output "ora specificata non valida.
Tuttavia ho provato a fare un test con cifre molto grandi e ci impiega sicuramente meno di un secondo |
| LjL |
Originally posted by elpampero
il problema è che se io faccio
TIME programma<input mi da come output "ora specificata non valida.
Tuttavia ho provato a fare un test con cifre molto grandi e ci impiega sicuramente meno di un secondo
Grazie, il comando time su Windows fa un'altra roba :)
Le funzioni a cui mi riferivo sono quelle di cui parlava qualcun altro, non io, quelle nell'header time.h o quel che è.
Fondamentalmente all'inizio della main() devi guardare che ora è, e alla fine del main() guardi di nuovo e fai la differenza.
In quel thread che ho indicato comunque c'è un metodo più semplice basato su un file .BAT.
P.S. per curiosità, per input *quanto* grandi ci mette meno di un secondo (e che processore hai)?
P.P.S. se ci mette meno di un secondo, comunque, i valori che puoi ottenere col file .BAT sicuramente non saranno molto significativi... |
| mattcobain |
Originally posted by virtual
Quanto impiega il vostro programma ad eseguire tutto l'input delle specifiche?
Il mio 37 secondi su PIII 1GHz.
37 secondi sull'input del prof?!?!?!
e la madonna!!!!!
cmq il mio, l'input del prof lo esegue in 0.03 secondi...il mio pc (non deridetemi :D ) è un malconcio pentium 2, 450 Mhz con 196 KB di ram.... sono all'antica!!! :lol:
e poi, cosa davvero strana, per fare invece l'input che ho postato qui, ci metto 0 secondi!!! per far arrivare il tempo a 0.03 devo copiare ed incollare le stesse righe di input almeno una 50ina di volte, ogni volta ricreando il piano!!!!
ho fatto un mega algoritmo della madonna supersonico (considerando su che pc lo sto facendo girare) oppure è una cosa normalissima!?!?! :) |
| LjL |
Originally posted by mattcobain
37 secondi sull'input del prof?!?!?!
e la madonna!!!!!
cmq il mio, l'input del prof lo esegue in 0.03 secondi...il mio pc (non deridetemi :D ) è un malconcio pentium 2, 450 Mhz con 196 KB di ram.... sono all'antica!!! :lol:
Figurati, io ho un 350MHz e solo perché me l'hanno regalato (altrimenti 233MHz)...
Certo, i 196 *kilo*byte di RAM un po' perplesso mi lasciano :D
e poi, cosa davvero strana, per fare invece l'input che ho postato qui, ci metto 0 secondi!!! per far arrivare il tempo a 0.03 devo copiare ed incollare le stesse righe di input almeno una 50ina di volte, ogni volta ricreando il piano!!!!
ho fatto un mega algoritmo della madonna supersonico (considerando su che pc lo sto facendo girare) oppure è una cosa normalissima!?!?! :)
Boh, è un po' strano che tu ci metta di meno col tuo input che con quello del prof, dato che il tuo sembra più grosso...
Tieni conto che time ha una certa granularità, e anch'io devo avere input di una certa dimensione prima di superare gli "0 secondi".
Io comunque per l'input del prof ci metto 0.05 secondi (tempo reale) e 0.005 secondi (tempo utente).
Per il tuo input, 0.1 e 0.005 rispettivamente.
[Non sono i numeri veri che mi vengono fuori, sono medie fatte a occhio su 4-5 esecuzioni, dato che i valori cambiano parecchio di volta in volta]
[Compilato con gcc -O3] |
| LjL |
Piuttosto comunque, quanto ci mettete voi per quest'input generato col programmino mio solito?
9182c0a200o200s200p200e200t200
Io ci metto 15 secondi (350MHz).
P.S. 15 secondi tolto il tempo per stampare l'output a video, cioè guardando il "tempo utente" sul comando time, o sopprimendo in qualche modo l'output (su Unix, aggiungendo >/dev/null alla linea di comando, su Windows, boh, forse >NIL: o >NUL: )
Ricordatevi anche di aggiungere 'f' alla fine dell'input, dato che il mio programma non lo mette ;) |
| mattcobain |
Originally posted by LjL
...Boh, è un po' strano che tu ci metta di meno col tuo input che con quello del prof, dato che il tuo sembra più grosso...
esatto, proprio quello mi ha fatto rimanere stranito!!!!
cmq ho riprovato piu volte e mi da sempre cosi....come ho detto, per fargli raggiungere un tempo nell'ordine degli 0.03 secondi devo copiare l'input e incollarlo una 50ina di volte, ogni volta facendogli ricreare il piano!!!!
e anche quello del prof....vero che la libreria time da valori non sempre uguali, ma anche qui, provando e riprovando, ottengo sempre o 0.03 o 0.04 secondi.....niente piu, niente meno!!!
ma fico....magari ho fatto davvero un buon lavoro!!! :cool:
boicottiamo i supercomputeroni degli ultimi 2 anni....torniamo ai 486!!! :D |
| LjL |
Originally posted by mattcobain
ma fico....magari ho fatto davvero un buon lavoro!!! :cool:
Se non fai dipendere il tempo di calcolo dalla distanza tra automi e richiamo, secondo me hai già fatto un buon lavoro.
Prova anche con input più grossi però, per vedere effettivamente come cresce la complessità... io ad esempio ho provato degli input che non fanno altro che creare n automi, con n da 0 a 2000 in incrementi di 10 (nel mio programma la creazioni di un'automa non è un'operazione O(1)).
Il grafico che mi viene fuori fa vedere una cosa che sembra proprio una parabola, come mi aspettavo.
Ad esempio:
500 automi = 0.5 secondi
1000 automi = 1.8 secondi
1500 automi = 4.23 secondi
2000 automi = 7.5 secondi
boicottiamo i supercomputeroni degli ultimi 2 anni....torniamo ai 486!!! :D [/B]
E chi se ne è mai andato? :D
Ok magari dai 486 me ne sono andato, però i quattro computer che uso sono un 350MHz, un 200MHz, un altro 200MHz e un 36MHz ;) |
| mattcobain |
Originally posted by LjL
Piuttosto comunque, quanto ci mettete voi per quest'input generato col programmino mio solito?
9182c0a200o200s200p200e200t200
Io ci metto 15 secondi (350MHz).
P.S. 15 secondi tolto il tempo per stampare l'output a video, cioè guardando il "tempo utente" sul comando time, o sopprimendo in qualche modo l'output (su Unix, aggiungendo >/dev/null alla linea di comando, su Windows, boh, forse >NIL: o >NUL:)
Ricordatevi anche di aggiungere 'f' alla fine dell'input, dato che il mio programma non lo mette ;)
maledetto, stai mettendo in crisi il mio pc :D
è tipo da 6 minuti che sto aspettando i risultati, ma ancora è qui che macina...poveraccio!!!! :lol:
anche perché non ho mica soppresso l'output....mica ho capito come si fa....
ma si, ormai aspetterò i risultati, magari domani riuscirò a postarli!!!!! :D |
| LjL |
Originally posted by mattcobain
maledetto, stai mettendo in crisi il mio pc :D
è tipo da 6 minuti che sto aspettando i risultati, ma ancora è qui che macina...poveraccio!!!! :lol:
anche perché non ho mica soppresso l'output....mica ho capito come si fa....
ma si, ormai aspetterò i risultati, magari domani riuscirò a postarli!!!!! :D
Ihihihi... be', di sicuro se aggiungi ">filequalsiasi" alla linea di comando l'output finisce su filequalsiasi, il che potrebbe essere comunque più veloce che farlo stampare sulla console.
Comunque stampando su console io ci metto 20 secondi. Vedete che non conta solo il tempo di esecuzione sui bassi numeri? :) O meglio, se conta o no non lo sappiamo, dato che non sappiamo che tipo di input propinerà il prof ai nostri programmi... però il senso del corso di algoritmi, sempre che io l'abbia capito, è quello di insegnarci a scrivere algoritmi asintoticamente buoni.
Se ti può consolare del fatto che il mio programma sembra meno complesso in tempo del tuo, è probabile che in spazio il tuo sia il sogno di ogni automa rispetto al mio :) Specialmente se usi liste dinamiche...
P.S. Oh, a proposito, hai detto "macina"? Sarebbe a dire semplicemente che è lì a calcolare, o macina nel senso che macina il disco fisso? Se è la seconda vuol dire che il tuo algoritmo è subottimale in *spazio* e non in tempo, o in altre parole che finisci la RAM e il sistema è costretto a usare lo swap. Se è così interrompi pure, tanto il risultato non avrebbe nessun significato. |
| Skilotto83 |
Originally posted by LjL
Sì, ma c'è da dire che o sono molto tonto io oppure riuscire a fare il calcolo *senza* una ricerca esaustiva non è proprio così facile! Adesso ci sono riuscito anch'io, ma ci ho messo veramente un bel po', e comunque la complessità in spazio e in tempo è O(n²), e sono sicuro che volendo si può diminuire... tu fai meglio di così? (tra l'altro O(n²) è per ogni automa; se devi far spostare tutti gli automi, O(n³))
devo ankora prendere confidenza con i tempi di esecuzione...
Kmq posso dire che il tempo per il calcolo di percorso e tortuosita' e relazionato solo an numero degli ostacoli sul piano...e non sul numero delle celle...il che è ottimo..
In particolare per il calcolo del percorso libero direi che il numero massimo di tentativi è pari a n ostacoli per 2(la x e la y) su cui si puo' sbattere...
La tortuosita' invece nn so di preciso...mi ha lasciato un po' di stucco il fatto che su percorsi molto complessi arrivo un percorso libero in x tentativi e per calolare invece la tortuosita' ci metto magari 10 volte di piu'...solo per riparmiare un "angolo" quindi per dim inuire di 1 la tortuosita' rispetto a quella del primo percorso libero trovato... |
| LjL |
Originally posted by Skilotto83
devo ankora prendere confidenza con i tempi di esecuzione...
Non è una cosa particolarmente difficile, se non per la confusione tra O, o, @, W, w e compagnia...
Kmq posso dire che il tempo per il calcolo di percorso e tortuosita' e relazionato solo an numero degli ostacoli sul piano...e non sul numero delle celle...il che è ottimo..
Questo significa che la tua 'n' è il numero di ostacoli presenti e non il numero delle celle coinvolte. E, sì, questa sicuramente è una buona cosa.
(Per la verità, nel caso peggiore il numero degli ostacoli potrebbe essere uguale al numero delle celle, e in quel caso il tuo algoritmo si comporterebbe come un algoritmo dipendente dal numero delle celle. Ma questo è il caso peggiore...)
In particolare per il calcolo del percorso libero direi che il numero massimo di tentativi è pari a n ostacoli per 2(la x e la y) su cui si puo' sbattere...
Sarebbe a dire O(n). Il 2 va via perché è una costante -- è inutile indicarlo, perché di costanti ce ne possono essere tante che in generale tu non puoi conoscere (ad esempio la velocità del tuo processore).
La tortuosita' invece nn so di preciso...mi ha lasciato un po' di stucco il fatto che su percorsi molto complessi arrivo un percorso libero in x tentativi e per calolare invece la tortuosita' ci metto magari 10 volte di piu'...
Questo dipende ovviamente da che algoritmo hai usato. Se hai usato un algoritmo ricorsivo senza troppi fronzoli, può anche darsi che il calcolo della tortuosità sia esponenziale (anche se per la verità non ho controllato se sia davvero probabile inventarsi un algoritmo esponenziale).
Nel caso del mio algoritmo, c'è una sola funzione per calcolare la tortuosità *e* controllare l'esistenza di un percorso, e quindi entrambe le operazioni sono O(n²).
O(n²) significa, in soldoni, che per ogni ostacolo vado a controllare tutti gli altri ostacoli: n*n=n².
Quando in C vedi una cosa del genere:
for(i=0; i<n; i++) {
...for(j=0; j<n; j++) {
......EseguiOperazione(i, j);
...}
}
è probabile che l'algoritmo che stai vedendo sia O(n²) (cioè che si esegua in tempo proporzionale a n² nel caso peggiore) o che sia @(n²) (cioè che si esegua in quel tempo in tutti i casi).
Se dentro ai for() si sono dei 'break' è più probabile che sia O(n²), se non ce ne sono è più probabile @(n²).
solo per riparmiare un "angolo" quindi per dim inuire di 1 la tortuosita' rispetto a quella del primo percorso libero trovato...
Non ho ancora capito fino a che complessità si possa riuscire a portare il calcolo della tortuosità. Sicuramente può scendere sotto il mio O(n²).
Se il tuo algoritmo è di complessità superiore a O(n²), probabilmente potrebbe aiutarti un po' di programmazione dinamica.
Se è già O(n²), boh :) ho idea che la tecnica della "memoization" possa essere una soluzione (= programmazione dinamica + consideri solo i sottoproblemi interessanti). |
| mattcobain |
Originally posted by LjL
...interrompi pure, tanto il risultato non avrebbe nessun significato.
cosa che ho fatto....anche perché ormai era passato piu di un quarto d'ora e risultati zero..... :look:
insomma....posso benissimo smentire le cazzate dette quando pensavo di aver fatto un algoritmo supersonico :D |
| Skilotto83 |
anke io usavo una sola funzione per il calcolo del percorso libero e della tortuosita'...
Ma poi ho pensato ke fosse inutile...
Quindi ho lasciato la vecchia funzione che fa la tortuosita' minima...
E ho fatto un'altra funzione molto piu' "lesta" che si ferma al primo percorso trovato...nn credi sia inutile che anche per il calcolo del percorso libero vada avanti finkè tra tutti i percorsi liberi nn ha trovato il meno tortuoso??
E' vero ke il mio algoritmo gia' smette di calcolare il percorso con tortuosita' minima quando si accorge di averne trovato uno piu' breve prima...nel senso che se il minimo è stato 3..se mentre cerca il percorso arriva a 3 lo scarta direttamente senza terminarlol...
Boh...
Kmq grazie per la lezioncina...mi è servita molto....
:D |
| LjL |
Originally posted by Skilotto83
[snip]
E ho fatto un'altra funzione molto piu' "lesta" che si ferma al primo percorso trovato...nn credi sia inutile che anche per il calcolo del percorso libero vada avanti finkè tra tutti i percorsi liberi nn ha trovato il meno tortuoso??
Sì, è inutile. Ma siccome la mia funzione *non va* a cercare percorsi liberi (proprio nel senso che non ha neanche un concetto di "percorso"), nel mio caso non è detto che la tua obiezione sia valida.
E' vero ke il mio algoritmo gia' smette di calcolare il percorso con tortuosita' minima quando si accorge di averne trovato uno piu' breve prima...nel senso che se il minimo è stato 3..se mentre cerca il percorso arriva a 3 lo scarta direttamente senza terminarlol...
Ottimo... anche a me piacerebbe riuscire a fare questo (cercare prima percorsi con tortuosità 1, e solo se ne ce ne sono cercarne con tortuosità 2, ecc.), ma per ora non ce l'ho fatta.
Io però, come ho già detto, non calcolo "percorsi" e quindi la cosa sarebbe un po' complicata da fare, anche se un'idea di come potrei farlo ce l'ho.
Se al contrario del mio il tuo algoritmo "calcola percorsi" (ed è, suppongo, ricorsivo), probabilmente per te è più difficile evitare di riesaminare lo stesso sottoproblema più di una volta, cosa che io evito, ma d'altra parte è più facile evitare di esaminare sottoproblemi inutili, cosa che io non evito.
Penso che, volendo strafare, la soluzione più utile sia per me sia per te sia quella della memoization. In pratica consiste nell'usare un algoritmo ricorsivo, ma tenendosi una tabella dove ci si segnano le soluzioni ai sottoproblemi già visti.
Se hai un po' di tempo ti consiglio di pensarci su un pochino: se il tuo algoritmo è già più che dignitoso, cosa che mi sembra che sia, IMHO lo potresti veramente rendere ottimo o quasi ottimo.
["Ottimo" nel senso di "il migliore possibile", ovviamente] |
| Skilotto83 |
Originally posted by LjL
Sì, è inutile. Ma siccome la mia funzione *non va* a cercare percorsi liberi (proprio nel senso che non ha neanche un concetto di "percorso"), nel mio caso non è detto che la tua obiezione sia valida.
Ottimo... anche a me piacerebbe riuscire a fare questo (cercare prima percorsi con tortuosità 1, e solo se ne ce ne sono cercarne con tortuosità 2, ecc.), ma per ora non ce l'ho fatta.
Io però, come ho già detto, non calcolo "percorsi" e quindi la cosa sarebbe un po' complicata da fare, anche se un'idea di come potrei farlo ce l'ho.
Se al contrario del mio il tuo algoritmo "calcola percorsi" (ed è, suppongo, ricorsivo), probabilmente per te è più difficile evitare di riesaminare lo stesso sottoproblema più di una volta, cosa che io evito, ma d'altra parte è più facile evitare di esaminare sottoproblemi inutili, cosa che io non evito.
Penso che, volendo strafare, la soluzione più utile sia per me sia per te sia quella della memoization. In pratica consiste nell'usare un algoritmo ricorsivo, ma tenendosi una tabella dove ci si segnano le soluzioni ai sottoproblemi già visti.
Se hai un po' di tempo ti consiglio di pensarci su un pochino: se il tuo algoritmo è già più che dignitoso, cosa che mi sembra che sia, IMHO lo potresti veramente rendere ottimo o quasi ottimo.
["Ottimo" nel senso di "il migliore possibile", ovviamente]
Purtroppo non ho molto tempo..quindi non saprei...
Piuttosto se posso chiederti una cosa....
Per gli automi come sai uso un array...
La fase di inserimento è fatta utilizzando la strcmp...
Ho pensato che i casi che ho si equivalgono....
Se inserisco in prima posizione ho risparmiato confronti della strcmp, ma ho bisogno di shiftare tutto l'array...
Se invece inserisco in ultima pos nn shifto nulla ma ho dovuto fare tutti i confronti con la strcmp...
Quindi il tempo è n/2 nel caso medio...no??
E la ricerca??
è lineare per forza...quindi n?
In quanto devo confrontare ogni posizione con strcmp fino al nome richiesto...no?? |
| LjL |
Originally posted by Skilotto83
Piuttosto se posso chiederti una cosa....
Come al solito mi sono un attimo dilungato (anche perché ci ragionavo mentre scrivevo...).
Se vuoi saltarti tutta la menata e leggere la conclusione, cerca ***.
Per gli automi come sai uso un array...
La fase di inserimento è fatta utilizzando la strcmp...
Ho pensato che i casi che ho si equivalgono....
Se inserisco in prima posizione ho risparmiato confronti della strcmp, ma ho bisogno di shiftare tutto l'array...
Se invece inserisco in ultima pos nn shifto nulla ma ho dovuto fare tutti i confronti con la strcmp...
Mi sa che qui ti sei espresso male da qualche parte.
In un array non si inserisce *mai* in prima posizione (o quantomeno non mi viene in mente neanche un caso plausibile).
Inserire in prima posizione ha costo O(n).
O si inserisce in ultima posizione (O(1)) o si inserisce nella posizione giusta, cioè tenendo gli elementi in ordine (O(n)).
Quindi non capisco cosa fai e che cosa invece pensi potrebbe essere meglio fare.
I casi che vedo io sono questi due:
- o inserisci in coda all'array (cioè alla fine), così l'inserimento ti costa poco, ma poi la ricerca ti costa O(n) dato che devi cercare linearmente tra n elementi,
- o inserisci nel punto giusto, così poi quando hai bisogno di ritrovare un elemento puoi fare una ricerca binaria (o dicotomica o come la vuoi chiamare), che se non ricordo male dovrebbe costarti solo O(lg(n)).
In pratica puoi:
- inserire ogni automa in tempo O(1) e cercare in tempo O(n)
- inserire in tempo O(n) e cercare in tempo O(lg(n))
Tieni conto che i tempi per l'inserimento si riferiscono a un *singolo* inserimento.
Se alla fine hai n elementi, significa ovviamente che hai inserito n elementi... quindi il costo *totale* degli inserimenti è O(n) nel primo caso e O(n²) nel secondo.
Anche i tempo per la ricerca si riferiscono ad una singola ricerca. Ma se tu sai che avendo n automi avrai sicuramente fatto n inserimenti, non puoi sapere a priori quante ricerche farai basandoti solo sul numero degli automi.
Supponi però di fare n ricerche, tanto per fare una supposizione: allora i due casi, in totale, diventeranno
- inserimento in O(n) e ricerca in O(n²)
- inserimento in O(n²) e ricerca in O(n*lg(n)).
In entrambi i casi il tempo totale è O(n²), ma nel secondo c'è un logaritmo che nel primo non compare.
*** Quindi, se il mio ragionamento è corretto, asintoticamente quello che fai è indifferente, ma su numeri piccoli tende ad essere migliore la prima scelta -- cioè, inserisci in coda all'array e poi fai una ricerca lineare.
Quindi il tempo è n/2 nel caso medio...no??
O(n). È vero, nel caso medio tenderai a fare n/2 operazioni, ma 1/2 è una costante e quindi scompare dalla notazione asintotica O().
E la ricerca??
è lineare per forza...quindi n?
In quanto devo confrontare ogni posizione con strcmp fino al nome richiesto...no??
Solo se l'array non lo tieni ordinato. Se è ordinato puoi fare una ricerca binaria, che è meno che lineare, ma l'analisi - anche se piuttosto campata per aria - che ho fatto sopra sembra suggerire che non ne vale la pena. |
| Skilotto83 |
non ci siamo capiti...
io l'array lo tengo sempre ordinato...
Pero' vista questa situaziuone...
potrebbe essere che per inserire trovo subito la posizione corrette...e allora ci ho messo poco per inserire, perchè ho fatto pochio confronti con strcmp per trovare il punto corretto di inserimento...pero' devo far shiftare tutte le altre posizioni successive per far posto al nuovo automa...
Potrebbe essere invece che la posizione giusta per il nuovo automa è l'ultima...allora ho fatto tutti i confronti con strcmp ma nn devo shifare nulla...
Kapito??
La ricerca è un altro discorso...
Sparisce la questione dello shift...
E imane solo che per cercare nell'array ordinato devo kmq scorrere con tante strcmp fino alla posizione esatta...
Quindi come dovrebbero essere i tempi??
Kmq se permetti tu ne sai di brutto... |
| Skilotto83 |
e kmq la ricerca dicotomica nn ho fatto in tempo a implementarla...:twisted::twisted::twisted:
e poi...
Quando ti ho detto del numero di tentativi per il percorso libero che era 2volte il numero di ostaoli mi hai detto che quindi è O(n)...si puo' considerare il tempo di esecuzione della funzione trovapercorsolibero??
Perkè nn mi sembra che sia un analisi corretta...il numero di tentativi nn fa il tempo di esecuzione...giusto?? |
| LjL |
Originally posted by Skilotto83
non ci siamo capiti...
io l'array lo tengo sempre ordinato...
Ah, ok. Però ho l'impressione che se poi non usi un binary search per la ricerca, tenerlo ordinato sia una cattiva idea. Comunque di questo ne parlo nella risposta all'altro messaggio.
Pero' vista questa situaziuone...
potrebbe essere che per inserire trovo subito la posizione corrette...e allora ci ho messo poco per inserire, perchè ho fatto pochio confronti con strcmp per trovare il punto corretto di inserimento...pero' devo far shiftare tutte le altre posizioni successive per far posto al nuovo automa...
Potrebbe essere invece che la posizione giusta per il nuovo automa è l'ultima...allora ho fatto tutti i confronti con strcmp ma nn devo shifare nulla...
Kapito??
Più o meno hai ragione - *se* fai finta che strcmp() impieghi sempre lo stesso tempo, hai una complessità @(n) sia se inserisci all'inizio sia se inserisci alla fine.
Però strcmp() impiega un tempo dipendente dalla lunghezza delle stringhe da comparare; in particolare strcmp() è O(n).
Supponi che *tutti* gli automi abbiano nomi di 1000 cifre: è facile rendersi conto che in questo caso costa molto meno inserire all'inizio che alla fine.
Comunque, anch'io nella risposta che ti avevo dato avevo fatto finta che la lunghezza delle stringhe fosse insignificante.
Il fatto che, almeno in teoria, può non essere insignificante è proprio il motivo per cui io ho usato un albero.
La ricerca è un altro discorso...
Sparisce la questione dello shift...
E imane solo che per cercare nell'array ordinato devo kmq scorrere con tante strcmp fino alla posizione esatta...
Quindi come dovrebbero essere i tempi??
O(n). Nel caso peggiore dovrai scorrere fino alla fine, e nel caso medio dovrai comunque scorrerere n/2 posizioni.
Con una ricerca binaria puoi ridurre questo tempo a O(lg(n)) (sempre se mi ricordo giusto), che è un gran bel miglioramento.
Kmq se permetti tu ne sai di brutto...
Ahah, insomma... diciamo che quando si scende un po' troppo nella matematica a me vien voglia di scappar via, però se non fosse per la matematica queste cose mi interessano... e poi Torelli ha un modo talmente assurdo di spiegare che seguirlo è quasi divertente ;) |
| LjL |
Originally posted by Skilotto83
[B]e kmq la ricerca dicotomica nn ho fatto in tempo a implementarla...:twisted::twisted::twisted:
In questo caso mi sa che puoi anche fare a meno di tenere l'array ordinato.
Se lo tieni ordinato, appena trovi un automa col prefisso giusto, sai già che gli altri che hanno lo stesso prefisso si trovano tutti immediatamente dopo quello.
Questo è vero, ma non fa cambiare molto le cose: il tempo per la ricerca è O(n), e sarebbe O(n) anche se gli automi non li tenessi ordinati.
Non tenendoli ordinati, in compenso, passaresti da un tempo O(n) per ogni inserimento a un tempo O(1), che sicuramente una brutta cosa non è.
Quindi, secondo me, è il caso che o implementi la ricerca binaria oppure fai a meno di tenere gli automi ordinati.
Oppure scrivi nella relazione "tengo gli automi ordinati per permettere una ricerca binaria, anche se non ho fatto in tempo a implementarla" :) Non so se il prof. apprezzi; io apprezzerei, dato che fa capire almeno che sei conscio della cosa.
e poi...
Quando ti ho detto del numero di tentativi per il percorso libero che era 2volte il numero di ostaoli mi hai detto che quindi è O(n)...si puo' considerare il tempo di esecuzione della funzione trovapercorsolibero??
Perkè nn mi sembra che sia un analisi corretta...il numero di tentativi nn fa il tempo di esecuzione...giusto??
Boh. Dipende da che cos'è un "tentativo", cosa che penso tu non mi possa spiegare dettagliatamente prima che sia finito il tempo per il progetto.
Se un "tentativo" è una cosa che impiega un tempo costante (= ci metti sempre lo stesso tempo a fare *un* tentativo), allora se fai n tentativi (o 2*n, o 3*n, o 1000*n) la tua funzione è O(n) o @(n).
Altrimenti, la complessità della tua funzione dipende dalla complessità dell'operazione "fai-un-tentativo".
Esercizio: qual è la complessità di questa funzione?
void PerdiTempo(int n) {
...int i, j;
...if(n>256) printf("Piu' di 256\n");
...else printf("Meno di 257\n");
...for(i=0; i<n; i++) {
......for(j=0; j<n; j++) {
.........printf("Perdo un po' di tempo...\n");
......}
...}
...for(i=0; i<n; i++) {
......printf("Ne perdo ancora un po'...\n");
...}
} |
| elpampero |
| Scusate, ma il prof risponde sia che il progetto vada bene sia che vada male? |
| mark |
Originally posted by elpampero
Scusate, ma il prof risponde sia che il progetto vada bene sia che vada male?
dovrebbe, altrimenti non puoi fare l'orale |
| elpampero |
| Molto bene...Aspetto un paio di giorni e poi lo contatto |
| mattcobain |
Originally posted by elpampero
Scusate, ma il prof risponde sia che il progetto vada bene sia che vada male?
ma perché, manda una mail di risposta!?
non basta il calendario degli orali per capire se devi farlo o meno?
e la risposta, se la manda, entro quanti giorni!? io il progetto l'ho inviato il 22.... |
| elpampero |
| Infatti..direi di aspettare un paio di giorni e vedere. ieri gli ho consegnato personalmente il progetto e sembrava che conoscesse già il mio nome. questo mi fa pensaer che avesse già controllato il programma e che, mancando una risposta, sia ok. |
| fdecollibus |
| scusatemi ragazzi, ma sapete se il progetto si può consegnare anche se l'output non corrisponde all'input? E' vero che in questo caso si viene automaticamente bocciati? |
| elpampero |
| Mi sembra che il prof abbia detto così..pero' puoi provare comunque... |
| Motomax |
Ciao
Io lo messo nella sua casella di posta.....sapete se è affidabile oppure NO? |
| fdecollibus |
| praticamente, da quello che ho capito, a questo esame, se l'input corrisponde all'output (ovvero con un programma adeguato dietro) si è praticamente promossi automaticamente, è vero? |
| elpampero |
| Forse detta così è un po' esagerata..però se fai il progetto ti sei tolto un bel peso..credo... |
| fdecollibus |
| io l'ho fatto ma il mio input non corrisponde all'output! Non credo neanche di consegnarlo! |
| elpampero |
| Ma scusa se l'hai fatto prova a fare un po' di debug..magari è un errore banale. Metti in giro un pò di printf e vedi cosa succede. Se sei riuscito ad implementare le ultime due funzioni sei a buon punto |
| fdecollibus |
| lo sto facendo da giorni ma non funzionano come devono forse ho fatto un errore di base nella struttura del percorso. Praticamente il metodo percorso prende la minima x1 tra gli ostacoli del piano e la minima y1 e prova a reistanziarsi a minimax1-1 e alla sua y2 e alla minimay1-1 e alla sua y2, e poi all'intersezione tra y2 e y1. Di li in poi il metodo richiama se stesso. La tortuosità è il numero di volte minimo che questo programma si richiama. Eppure non va. |
| mark |
Originally posted by fdecollibus
io l'ho fatto ma il mio input non corrisponde all'output! Non credo neanche di consegnarlo!
se l'output è ok al 90% io lo invierei comunque, e lascerei la valutazione finale al prof ;) |
| elpampero |
| Infatti..Ma perchè calcoli gli le coordianate degli ostacoli? |
| fdecollibus |
non è ok al 90%. Sballa tutte le tortuosità.
Calcolo le coordinate degli ostacoli più vicini e vedi come evitarli, se posso evitarli. Mi sembrava un ragionamento corretto. |
| mattcobain |
Originally posted by Motomax
Ciao
Io lo messo nella sua casella di posta.....sapete se è affidabile oppure NO?
non so se è affidabile, fatto sta che anchio ieri l'ho lasciata nella sua casella di posta ed era aperta!!! :look:
cmq appena avevo messo la copia cartecea, dopo neanche un minuto ho visto il prof arrivare mentre io andavo via e mi è sembrato di aver sentito il rumore che apriva la cassetta e prendeva le copie che conteneva....cmq il fatto che era aperta mi puzzava abbastanza! |
| Teju |
| Dovete mandargli anche una copia via mail del codice e della relazione!!! |
| mattcobain |
Originally posted by Teju
Dovete mandargli anche una copia via mail del codice e della relazione!!!
si chiaro...l'abbiamo letto tutti il testo del progetto!!! ;)
cmq grazie per il promemoria! |
| Teju |
Originally posted by mattcobain
si chiaro...l'abbiamo letto tutti il testo del progetto!!! ;)
cmq grazie per il promemoria!
E allora basta, state tranquilli: se ha ricevuto la mail farà i suoi test e poi vi manda una mail di conferma o di non conferma per l'orale...
Probabilmente aspetta la data di chiusura del progettino prima di mandare le mail agli studenti che han già consegnato. :-D |
| Skilotto83 |
ragazzi...
lo so ke nn è nulla di grave....
ma a voi se stampate il codice del progetto quanto vi viene...??
io sono a 40pagine!!!
un po' è il mio metodo di fare....
Uso tante funzioni anhe per calcolare un solo valore, ma il codice guadagna leggibilita'...
E poi dichiaro sempre le variabili e alla riga successiva gli assegno un valore, senza fare tutto direttamente... |
| mattcobain |
io ho stampato in 13 pagine tutto il codice, le righe (commenti compresi, moooolti) sono 1230 circa
naturalmente ho diminuito il carattere a 7, ma è leggibile....
poi ognuno ha il suo modo di scrivere....io ad esempio se devo inizializzare ed assegnare un valore lo faccio subito nella sua dichiarazione....oppure se ci sono cicli con una sola istruzione ometto le parentesi, uso spesso l'operatore ternario anzichè if-else.....ecc...ecc... |
| Skilotto83 |
ridotto a 7 anche il mio....
25pagine...compresi i moduli.h e un botto di commenti...
Cosi' va meglio.... |
| Granito |
Ciao Skilotto!! L'ho finito anch'io...
Ho utilizzato una semplice struttura a liste puntate, e mi è uscito intorno alle 14 pagine (in word). Speriamo di beccarci alla discussione allora!
Granito |
| Jacoposki |
sigh... in chiusura e ancora non va... a meno di miracoli dell'ultima ora se ne riparla ad aprile. E' stato bello... anzi no :(
Non so gli altri, ma a me i quattro giorni che non ci hanno dato avrebbero fatto non poco comodo.
Amen |
| LjL |
18 pagine, carattere 9, pagina in orizzontale.
Decisamente troppo lungo e anche troppo brutto per i miei gusti, ma spero che Fiorentini lo giudichi meglio di me ;)
E spero anche che il termine del "24 compreso" fosse rigoroso, dato che l'ho infilato nella sua casella verso le 18:30 e gli devo ancora mandare l'e-mail :D |
| Polsy |
Originally posted by LjL
18 pagine, carattere 9, pagina in orizzontale.
Decisamente troppo lungo e anche troppo brutto per i miei gusti, ma spero che Fiorentini lo giudichi meglio di me ;)
E spero anche che il termine del "24 compreso" fosse rigoroso, dato che l'ho infilato nella sua casella verso le 18:30 e gli devo ancora mandare l'e-mail :D
allora forse sei tu quello che ho incrociato oggi cercando la casella di aguzzoli...
cmq questo progetto è stato un parto...non mi sono mai sbattuta tanto x nessuna materia da quando è iniziata l'università :S |
| Skilotto83 |
Originally posted by LjL
18 pagine, carattere 9, pagina in orizzontale.
Decisamente troppo lungo e anche troppo brutto per i miei gusti, ma spero che Fiorentini lo giudichi meglio di me ;)
E spero anche che il termine del "24 compreso" fosse rigoroso, dato che l'ho infilato nella sua casella verso le 18:30 e gli devo ancora mandare l'e-mail :D
hai pm...se hai voglia di rispondere...
Kmq io gli ho mandato ieri una mail chiedendo gentilemnte sela copia cartacea si puo' lasciare domani mattina...e mi ha detto ok.,..
ora gli mando la mail.. |
| LjL |
Originally posted by Polsy
allora forse sei tu quello che ho incrociato oggi cercando la casella di aguzzoli...
cmq questo progetto è stato un parto...non mi sono mai sbattuta tanto x nessuna materia da quando è iniziata l'università :S
Forse eri quella che stava parlando col custode prima che gli chiedessi io per la casella di Fiorentini. Comunque se il tizio che hai visto non si tagliava la barba da troppo, ma veramente troppo tempo, ero io :D |
| Polsy |
Originally posted by LjL
Forse eri quella che stava parlando col custode prima che gli chiedessi io per la casella di Fiorentini. Comunque se il tizio che hai visto non si tagliava la barba da troppo, ma veramente troppo tempo, ero io :D
hmmm :S no...mi sa ke era qualcun altro... |
| LjL |
Secondo voi quand'è che si può cominciare a postare i progetti qui sopra? Solo dopo tutti gli orali o anche prima?
A parte questo... cos'ho imparato da questo progetto? (Tema di Italiano, terza elementare). Magari sono cose utili anche per qualcun altro di voi...
- Probabilmente è meglio scrivere, subito, un programma che funziona, piuttosto che farsi il sangue marcio per trovare un buon algoritmo senza nel frattempo mettere giù una linea di codice. Così si finisce per consegnare all'ultimo momento (se va bene) e per scrivere un programma che tutto sommato non è poi così più efficiente rispetto a uno che si è cominciato a scrivere *subito*. Se poi il prof guarda solo se va.....
- assert() è una Cosa Buona(tm). Anche se spesso e volentieri quando fallisce un'asserzione non si ha la più pallida idea di *perché* sia fallita, intanto comunque si *sa* che da qualche parte un errore c'è. Poi comunque i debugger sono lì per quello. Morale: appena viene in mente "ehi ma qui la variable tale sarà sempre minore della variable talaltra", metterci un'assert().
- I debugger sono Cosa Buona(tm). Questo non l'ho scoperto solo in questo progetto, ma comunque per un bel po' di tempo mi sono rifiutato di imparare a usare un debugger. Ma il tempo perso per guardarsi i comandi di GDB è niente rispetto agli errori che ti aiuta a trovare. Un semplice "where" in GDB ti fa quantomeno capire *dov'è* che quella cacchio di assert() era fallita (sempre se sai che prima devi scrivere "break abort", perché il programma non esca dopo l'assert())
- Per trovare memory leak e puntatori che si perdono nella nebbia dei tempi, usare Valgrind. Inutile stare a perdere tempo con GDB o con tecniche casereccie varie
- Tanto va la gatta al lardo che ci lascia lo zampino |
| elpampero |
| Scusate ma Fiorentini ha risposto a qualcuno di voi? |
| mattcobain |
| a me personalmente non ancora |
| elpampero |
| Mi viene il dubbio che non risponda. Se è andato bene ti trovi nell'elenco degli esami orali.. |
| Timido |
| Mha qualcuno sà più o meno se oggi pubblicherà le date dell'orale? |
| elpampero |
| Non ne ho idea. Speriamo! |
| Timido |
| Ciao qualcuno potrebbe dire cortesemente i capitoli da studiare dall libro? "indroduzzione agli algoritmi" grazie in anticipo........visto che io non ho potuto seguire le lezionei mi farebbe un enorm cortesia |
| elpampero |
| Mi ha risposto il prof dicendomi che il codice è abbastanza corretto ma che ci sono degli erroretti... Vado comunque all'orale :-) |
| Timido |
anche a me mi ha risposto cosi:
Il progetto e' poco efficiente (con input allegato non termina)
L' operazione e e' corretta, con t si hanno errori
(gia' con gli input del testo) ed e' troppo lenta
(provi a eseguire l'input allegato sostituendo e con t)
per l'orale consulti il sito.
Però sul sito non trovo nulla e voi§?? |
| elpampero |
| Penso che tra un po' metterà fuori le date degli orali |
| mattcobain |
ha risposto anche a me con un
" Il progetto funziona correttamente
Per l'orale consulti la pagina del corso "
però ancora non sono usciti i calendari...che cmq penso proprio usciranno qui http://homes.dsi.unimi.it/~torelli/algoritmi.html |
| elpampero |
mattcobain, proveresti con questo input e mi dici qual è l'output?
c
o -11 -7 -3 -5
o -12 -3 -8 -1
o -6 -3 -1 -1
o -12 2 -11 7
o -9 4 -3 7
o 0 -6 12 -4
o 18 -5 14 -4
o -6 2 -1 10
o -11 9 -8 10
o -2 6 1 9
o 8 2 12 4
o 15 2 20 6
o 4 -10 16 -8
o 18 -2 19 0
o 3 4 7 7
o 9 6 12 8
o 14 8 17 10
o 21 7 22 8
o 3 9 6 11
o 11 -2 12 -1
o 18 -8 22 -7
o 8 10 12 12
o 5 12 6 13
o 14 12 15 13
o 19 10 22 11
o 1 -2 8 1
o 15 -3 16 -2
o -4 -11 0 -9
a -12 -12 100
t -8 0 100
t 0 -8 100
t 22 0 100
t 14 0 100
t 0 0 100
t -2 -4 100
t 2 2 100
t 0 1 100
t 2 5 100
t 2 10 100
t 8 9 100
t 22 13 100
t 23 13 100
o 13 2 14 3
t 22 13 100
a -12 12 101
t 16 0 101
t 0 0 101
t 14 -7 101
t 23 -12 101
t 22 -9 101
a 23 9 110
t 0 0 110
t 0 -3 110
t 13 4 110
t -12 -11 110
a 22 -10 111
t 14 0 111
t -12 12 111
t -7 0 111
f |
| mark |
con quale metodo avete rispolto il problema ?
ricorsione oppure "dijkstra" o metodi similari ?
solo una curiosità, non mi interessa il codice :) |
|
|
|
|
