 | |
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 |
| aghito |
facendo una lista delle 1-celle conviene farla con inserimento in coda perchè bisogna controllare che la 1 cella che inserisco non sia già nella lista..con l'inserimento in coda dato che devo controllare il campo next per vedere l'ultimo elemento controllo anche il valore di key e se è uguale a quello da inserire mi fermo...
avete del codice per liste con inserimento in coda o siti di riferimento? |
| lino |
| Come faccio UNA LISTA CON |
| mitnik |
| IO sto procedendo come Dante, ho una lista con le 1-celle, poi creo una lista con le k-celle che hanno come figli le 1-celle che contengono. Per l'area devo creare un'altra lista con le k-celle che sono occupate. Il problema è sul calcolo dei blocchi, avete qualche idea? |
| Dante |
bravo! sto scrivendo questa parte di codice.... una volta funzionante aggiungo le funzioni area, peso e blocchi... sperem....
tu sei già lì? |
| ghily |
Originally posted by mitnik
IO sto procedendo come Dante, ho una lista con le 1-celle, poi creo una lista con le k-celle che hanno come figli le 1-celle che contengono.
Finalemtne ho dato editoria ed ora posso concentrarmi sul progetto.Il tempo è poco ma speriamo in bene.Una cosa ancora non ho capito: ma queste 1-celle sono veramente così importanti? Mi spiego meglio: quale è l'utilità di sapere che nella k-cella (k,x,y) è contenuta percisametne quella cella? Se non mi sfugg eniete nel testo non c'è nessuna funzione che ti chiede di ritornare 1-celle.L'importante è sapere QUANTE (non quali) celle sono contenute nella k-celle selezionata. Sbaglio??
Altra cosa che non mi è chiara.Nella funzione elimina (k,x,y) la cella che è da andare a trovare è la cella che ha coordinate (kx,ky) ecc. ? Oppure la 1-cella (k,y???
Grazie
Chao
Roby |
| eskimo |
se la funzione ti dice di eliminare k x y devi eliminare la cella di coordinate x, y quando la risoluzione è k: si parla direttamente di 1celle solo se ti chiede la kcella(1, x, y).... se invece quel k ha un valore diverso da 1 devi eliminare TUTTE le 1celle comprese (e presenti) nell'intevallo kx <= ascissa < k(x+1) e
ky <= ordinata < k(y+1)
ascissa e ordinata sono le coordinate della 1cella
chiaro??? spero di esserlo stato! :) :) |
| ghily |
Faccio un esempio pratico,sperando che sia chiaro, perchè mi sembra sempre la cosa migliore.Ammettiamo che la mia risoluzione sia 3. La chiamata elimina (2,3) va a chiamare la cella che ha vertice in basso a sinistra (6,9) e non quella che ha (2,3), giusto? Una volta trovata questa cella vedo se questa cella è occupata.Questo lo vedo regolandomi col parametro di riempimento (nessuna menzione sulle 1-celle ancora).In caso affermativo la svuoto, cioè le sue 1-celle occupate saranno zero. IN caso contrario non faccio nulla.
Quello che mi domando io è:
ammettiamo che la cella (7,9) sia occupata e che la k-cella che la contiente sia anch'essa occupata.Mi interessa sapere che vado a liberare proprio quella cella? oppure mi interessa solo che ho liberato la k-cella, cioè che la k-cella ora non contiene più celle occupate. Praticamente sulle 1-celle non si lavora mai in maniera diretta.
Spero sia chiaro.
Chao
Roby |
| Skilotto83 |
Originally posted by ghily
Finalemtne ho dato editoria ed ora posso concentrarmi sul progetto.Il tempo è poco ma speriamo in bene.Una cosa ancora non ho capito: ma queste 1-celle sono veramente così importanti? Mi spiego meglio: quale è l'utilità di sapere che nella k-cella (k,x,y) è contenuta percisametne quella cella? Se non mi sfugg eniete nel testo non c'è nessuna funzione che ti chiede di ritornare 1-celle.L'importante è sapere QUANTE (non quali) celle sono contenute nella k-celle selezionata. Sbaglio??
Altra cosa che non mi è chiara.Nella funzione elimina (k,x,y) la cella che è da andare a trovare è la cella che ha coordinate (kx,ky) ecc. ? Oppure la 1-cella (k,y???
Grazie
Chao
Roby
Per sapere se due celle sono adiacenti(e quindi hanno un punto in comune) devi sapere la posizione di tutte le singole celle della k-cella....e il diskorso vale anke se improvvisamente cambi risoluzione...altrimenti dovresti ripetere tutto ogni volta... |
| contezer0 |
Originally posted by Skilotto83
Per sapere se due celle sono adiacenti(e quindi hanno un punto in comune) devi sapere la posizione di tutte le singole celle della k-cella....e il diskorso vale anke se improvvisamente cambi risoluzione...altrimenti dovresti ripetere tutto ogni volta...
io pensavo che due k celle fossero adiacenti se occupate (ovvero il numero di 1 celle contenute supera la "soglia di carico") e se si "toccano" almeno in un angolo!
almeno...nell'esempio del testo del progetto ci sono delle 3-celle adiacenti le cui 1-celle pero' non lo sono... |
| contezer0 |
Originally posted by eskimo
oppure mantenere una lista semplice, sulla quale cercherei in questo modo: ogni kcella ha una x, y di base; questo indice lo memorizzo in un puntatore (che modifico ogni volta che la mia attenzione si sposta su una nuova kcella), così so che per cercare le altre 1celle parto sempre da quel punto e non ogni volta dall'inizio della lista.
Seocondo voi quale metodo è più performante o comunque migliore???
Spero di esser stato chiaro
P. thx!!!! :) :)
Ma in questo modo devi mantenere ordinata la lista delle 1-celle, giusto? quindi hai un costo N per inserimento e cancellazione, e poi in che modo terresti ordinata questa lista per renderla "consistente" col puntatore alla x,y di base di una k-cella?
io tifo albero binario...ma suppongo ci voglia una variante bilanciata, se no si ha sempre un costo N nel caso peggiore. |
| contezer0 |
gia' che ci sono...
ma qualcuno allora la usa la tabella hash?
la fate a indirizzamento aperto e dimensione variabile oppure con concatenazione e dimensione fissa?
e per calcolare il blocco c'e' qualche metodo meno costoso del "prendo una cella, cerco tutti i suoi eventuali adiacenti, di questi cerco i *loro* adiacenti e cosi' via"? |
| Skilotto83 |
Originally posted by contezer0
io pensavo che due k celle fossero adiacenti se occupate (ovvero il numero di 1 celle contenute supera la "soglia di carico") e se si "toccano" almeno in un angolo!
almeno...nell'esempio del testo del progetto ci sono delle 3-celle adiacenti le cui 1-celle pero' non lo sono...
E' esattamente cosi'...ma devi sapere le coordinate dei punti della K-cella...altrimenti kome sai se tokka un altra k cella?? |
| contezer0 |
Originally posted by Skilotto83
E' esattamente cosi'...ma devi sapere le coordinate dei punti della K-cella...altrimenti kome sai se tokka un altra k cella??
beh a meno di un fattore k (la risoluzione) una k-cella non si comporta esattamente come una 1-cella?
quindi se abbiamo una risoluzione =1, chiamo la funzione che calcola i blocchi sulla struttura delle 1 celle.
la struttura che memorizza le k celle, che viene costruita quando si cambia la risoluzione, si puo' fare uguale, mettendo per ogni k-cella una x e una y (che nel piano sara' kx e ky), ovviamente dopo aver guardato quante 1 celle contiene.
In questo modo la funzione che calcola i blocchi puo' essere la stessa, no? |
| d0k |
Ho scelto la via + semplice. Liste linkate e passa la paura. Ora vi domando. Indipendentemente dalla struttura dati qualcuno ha idea della procedura (pseudocodice sarebbe troppo) che dalle k-celle passa ai k-blocchi? Avete qualche consiglio? Codice riciclabile che avete visto in giro? Attendo ansiogeno..
***
un uomo a 2 passi dal bruciarsi uno scritto. |
| Eruyomë |
Ciao volevo chiedere se nessuno ha avuto problemi con il confronto del peso di una k-cella con il p/q*k*k; poiché il primo è unsigned o int mentre il secondo è duoble o float e nel confonto mi escono risultati pazzi: del tipo un 3 che è 2.9 e diventa 2, un 3 che risulta minore di 3.0, approssimazioni che non fanno girare il programma a dovere, etc...
nessuno di voi sa come si può fare ad evitarlo? |
| Eruyomë |
| Occhei, come non detto! Ho risolto manipolando manualmente la parte dopo la virgola del double (un lavoraccio)... |
| attila79 |
| Una curiosità, piu o meno quante righe di codice vi sta uscendo il progetto? Spero di non essere l'unico ad amare il codice rindondante ...io viaggio intorno alle 900 righe, devo preoccuparmi? |
| Skilotto83 |
Originally posted by attila79
Una curiosità, piu o meno quante righe di codice vi sta uscendo il progetto? Spero di non essere l'unico ad amare il codice rindondante ...io viaggio intorno alle 900 righe, devo preoccuparmi?
No...vanno bene anke 2000...basta ke me lo passi e me lo fai kopiare...
:D |
| contezer0 |
Originally posted by Eruyomë
Occhei, come non detto! Ho risolto manipolando manualmente la parte dopo la virgola del double (un lavoraccio)...
ma non bastava un cast?
cmq mi hai messo la pulce nell'orecchio...ora lavoro un po' su sta cosa! |
| contezer0 |
Originally posted by Eruyomë
Occhei, come non detto! Ho risolto manipolando manualmente la parte dopo la virgola del double (un lavoraccio)...
mi pare un po' inutile passare per i float o i double visto che tutto il resto e' basato sugli interi.
io ho fatto cosi',anche se non mi piace tanto (supponendo che p sia il minore)
k*k*p / q e memorizzo il risultato
k*k*p%q se e' diverso da 0, aggiungo 1 al risultato
in questo modo, se il fattore di riempimento ha un quoziente che divide k, la soglia sara' "precisa"...ad esempio se p/q e' 1/2 con risoluzioni pari (ovvero devo riempire almeno per meta' le k-celle)
altrimenti arrotondo per eccesso (tanto non potro' mai avere un "pezzo di 1-cella").
ci sono per caso dei metodi piu' carini? |
| contezer0 |
Originally posted by attila79
Una curiosità, piu o meno quante righe di codice vi sta uscendo il progetto? Spero di non essere l'unico ad amare il codice rindondante ...io viaggio intorno alle 900 righe, devo preoccuparmi?
ops...chiedo scusa per i post di sopra ma mi si e' impalato il browser....
io sono intorno alle 400 ma con un paio di funzioni per il debug e un casino di linee vuote o con le graffe...spero con un po' di pulizia di rimanere cosi'...mi manca ancora qualcosina |
| contezer0 |
Originally posted by Eruyomë
Occhei, come non detto! Ho risolto manipolando manualmente la parte dopo la virgola del double (un lavoraccio)...
az io ero convinto che bastasse un cast...
beh per non pasticciare con i float, si fa la divisione tra p e q e si memorizza il risultato...poi si fa il modulo e se e' diverso da zero, si incrementa il risultato di 1. |
| mitnik |
chi ha usato le liste mi darebbe una mano sulla funzione blocchi? come ha ragionato?
Grazie |
| Eruyomë |
| Si anch'io ho fatto una roba così contezer0, viaggio poco più sulle 400 righe usando liste di liste (una specie di grafo), ma ho ancora qualche scaramuccia con la cancellazione delle stesse in memoria che mi fa venire un 6 al posto di un 5 nell'esempio, che odio---- |
| contezer0 |
Originally posted by Eruyomë
Si anch'io ho fatto una roba così contezer0, viaggio poco più sulle 400 righe usando liste di liste (una specie di grafo), ma ho ancora qualche scaramuccia con la cancellazione delle stesse in memoria che mi fa venire un 6 al posto di un 5 nell'esempio, che odio----
wow! lista di adiacenza? e' molto veloce sul calcolo dei blocchi, direi!
ma un po' piu' lenta per inserire e togliere le celle
cmq oggi sono arrivato a circa 600 linee |
| ghily |
So che non è prudente paralre già di consegna visto chenessuno di noi ha finito(anzi io sdevo ancora iniziare....), però avevo un apio di curiosità:
- La consegna deve avvenire entro il tre settembre ma a che ora?
-la relazione scritta che va consegnata ad aguzzoli è da consegnare entro venerdì? O il dipartimento è aperto acnhe di sabato? dove va portata? Secondo voi se consegno relazione e progetto in carta cartacea venerdì poi durante il week-end psso andare avanti a lavorare??
Grazie
Chao Roby |
| aghito |
perchè la carta può anche non essere cartacea?
cmq è il 3 ottobre e le modalità sono ben spiegate nel pdf.. |
| ghily |
Originally posted by aghito
perchè la carta può anche non essere cartacea?
caspita hai ragione... Vabbè piccolo errore.Ma la mia curiosità era sapere se il dipartimento è aperto anche di sabato.Come faccio ad imbucare il progetto nella casella di posta di aguzzoli se il dipartimento è chiuso?
Chao
Roby |
| Skilotto83 |
Nn dice da nesuna parte ke bisogn consegnare copia cartacea...
Anzi...dice chiaramente che i file devono essere zippati e deve esserci Codice+Relazione...
Poi all'orale porterai una copia cartacea... |
| contezer0 |
Originally posted by Skilotto83
Nn dice da nesuna parte ke bisogn consegnare copia cartacea...
Anzi...dice chiaramente che i file devono essere zippati e deve esserci Codice+Relazione...
Poi all'orale porterai una copia cartacea...
veramente dice di consegnare una copia cartacea lunedi' 4...
dice anche di non usare variabili globali per informazioni di carattere locale...
io in un UNA SOLA occasione uso UNA SOLA variabile globale...quando inserisco una 1cella manualmente (la funzione di inserimento che uso pasticcia comunque la struttura anche se la cella e' gia' presente). Tutte le altre volte non mi serve...e il valore di ritorno della funzione mi serve sia un indirizzo...avranno pieta' di questa piccola imperfezione?
di certo non mi metto a passare un indirizzo a un int ogni volta...gia' cosi' passo tanti parametri! |
| contezer0 |
un momento di attenzione.....
HO FINITOOOOOOOOOOOOOOOOOO
era oraaaaa
adesso mi tocca provare e riprovare...scrivere la documentazione (qualcuno ha idea di cosa metterci, a proposito?) |
| aghito |
complimenti!
ci fai un riassunto delle strutture dati utilizzate e come hai fatto la funzione blocchi...ci searesti molto d'aiuto..grazie |
| ghily |
Originally posted by contezer0
veramente dice di consegnare una copia cartacea lunedi' 4...
dice anche di non usare variabili globali per informazioni di carattere locale...
io in un UNA SOLA occasione uso UNA SOLA variabile globale...quando inserisco una 1cella manualmente (la funzione di inserimento che uso pasticcia comunque la struttura anche se la cella e' gia' presente). Tutte le altre volte non mi serve...e il valore di ritorno della funzione mi serve sia un indirizzo...avranno pieta' di questa piccola imperfezione?
di certo non mi metto a passare un indirizzo a un int ogni volta...gia' cosi' passo tanti parametri!
Il progetto del turno uno e due sono gli stessi ma le specifiche di consegna sono diverse. Le note di aguzzoli soo di meno (per esempio non dice nulla sulle variabili globali).
Andre, il progetto di aguzzoli dice questo:
Una copia cartacea della relazione e del codice deve inoltre essere consegnata al dr. Aguzzoli sempre
entro il 3 Ottobre 2004 (lasciandola eventualmente nella sua casella postale presso il dipartimento in via
Comelico).
Ma penso che anche se la consegno il 4 mattina alle 8.30 non cambi nulla visto che comunque la mail gliela devo mandare entro la mezzanotte del 3.
Chao
Roby |
| contezer0 |
Originally posted by aghito
complimenti!
ci fai un riassunto delle strutture dati utilizzate e come hai fatto la funzione blocchi...ci searesti molto d'aiuto..grazie
allora...in breve...ho usato 3 alberi, adesso sto decidendo se ottimizzare implementandoli effettivamente tutti diversi (in pratica uno per le 1 celle, uno per le k celle anche se non hanno abbastanza "peso" , e uno per le k celle effettive.
su ognuno di questi in effetti ho bisogno di cose diverse, ma dover riscrivere il cancella(), l'inserisci(), l'inserisci_pesato() e il sistema_adiacenze() per ognuno mi triplicherebbe la lunghezza del codice...
se qualcuno ha seguito il corso mi puo' dire se fiorentini preferisce un codice corto e leggibile a scapito di alcune variabili non utilizzate, oppure una maggiore ottimizzazione a scapito di leggibilita' e dimensione del sorgente?
comunque...sull'albero delle k celle effettive ovviamente eseguo le varie funzioni di numero blocchi, area e peso.
la funza blocchi e' una semplice visita in profondita' ripetuta, in realta' la ricorsione va fatta con due funzioni e non con una sola per poter tener conto delle celle non ancora colorate nelle visite successive. |
| eskimo |
Ciao, non credo di essere l'unico ad aver usato liste semplici per ordinare 1celle e kcelle... qualche idea su come scoprire un cammino?? non avendo liste di adiacenza come fare?? posso controllare tutte le kcelle che toccano in un punto la kcella che sto verificando, ma non basta! una volta che ho scoperto la mia kcella vicina, devo passare a controllare i suoi vicini, ma ogni volta devo tener conto di quelle già visitate... cosa consigliate??
thx!!!! |
| skorpius |
raga, gestite in qualche modo il massimo dei numeri rappresentabili? Cioè se l'utente inserisce un bel
i 2^34 2^48 che cosa deve succedere?
Io credo che nelle supposizioni di correttezza dei comandi si intenda anche che non viene inserito alcun numero non rappresentabile, quindi non ho fatto nulla in proposito, ma secondo voi è una interpretazione corretta? |
| Eruyomë |
ciao eskimo forse potresti fare un'altra lista dove ci metti quelle già controllate e chiami ricorsivamente una funzione (per esempio una specie di area) sulle cordinate di tutti i punti possibili adiacenti.
A me funziona, constatando o meno il fatto di avere già visitato o meno una cella attraverso la lista supplementare non va in loop. |
| contezer0 |
Originally posted by eskimo
Ciao, non credo di essere l'unico ad aver usato liste semplici per ordinare 1celle e kcelle... qualche idea su come scoprire un cammino?? non avendo liste di adiacenza come fare?? posso controllare
chi ti impedisce di usare liste di adiacenza?
non e' impossibile usare due strutture distinte (una per memorizzare le celle inserite e una per lavorarci su...) per i blocchi, l'area e il peso, una lista di adiacenza e' l'ideale, visto che il tempo e' lineare (in questo caso si puo' dire che e' lineare perche' il massimo grado del grafo delle celle e' 8) |
| mitnik |
Io , eskimo ho fatto cosi: Verifico che la k-cella sia occupata, se si la metto in una lista semplice di supporto;: poi controllo una ad una le 8 celle che la circondano, ognuna di esse che è occupata la metto nella lista (in coda). Una volta controllate le 8 celle della prima k-cella della lista di supporo passo alla seconda k-cella di tale lista e così per tutte quelle inserite. Alla fine conto quante k-celle ho nella lista di supporto e mi danno l'area. Fino ad ora ha funzionato.
Ora devo implementare la funzione blocchi. Consigli? |
| contezer0 |
| ue' allora ma fiorentini preferisce un programma corto con strutture un po' ridondanti, o delle strutture perfette ma con un casino di funzioni vagamente simili? |
| contezer0 |
Originally posted by mitnik
Io , eskimo ho fatto cosi: Verifico che la k-cella sia occupata, se si la metto in una lista semplice di supporto;: poi controllo una ad una le 8 celle che la circondano, ognuna di esse che è occupata la metto nella lista (in coda). Una volta controllate le 8 celle della prima k-cella della lista di supporo passo alla seconda k-cella di tale lista e così per tutte quelle inserite. Alla fine conto quante k-celle ho nella lista di supporto e mi danno l'area. Fino ad ora ha funzionato.
Ora devo implementare la funzione blocchi. Consigli?
ma devi usare un flag che ti indica se sei gia' passato ...altrimenti non ti va in loop?
la funzione blocchi e' praticamente uguale! prendi una cella, fai la visita e colori quelle connesse, poi scorri nella struttura principale finche' non ne trovi una non visitata, incrementi il contatore e fai la visita, e cosi' via fino in fondo |
| eskimo |
grazie per i consigli... alla fine stamattina mi sono scervellato e ho tirato fuori una funzione schifezza (tanto lo sono tutte, devo avere un progetto con complessità infinita! :) ) praticamente ho aggiunto una flag nella lista di kcelle che viene usata dalle mie funzioni area e peso... è una specie di attraversamento in ampiezza senza liste di adiacenza:
flag 0 = cella mai visitata flag = 1 cella scoperta ma non visitata flag = 2 cella visitata.
a partire dalla cella che inserisco come argomenti nella funzione controllo i suoi vicini e li metto a 1 oltre ad inserirli in una lista tipo stack, poi metto a 2 la suddetta cella, poi a uno ad uno dallo stack faccio la stessa cosa...
alla fine dovrebbe funzicare
speriamo!
grazie mille per i consigli!!! :) :) |
| contezer0 |
Originally posted by eskimo
grazie per i consigli... alla fine stamattina mi sono scervellato e ho tirato fuori una funzione schifezza (tanto lo sono tutte, devo avere un progetto con complessità infinita! :) ) praticamente ho aggiunto una flag nella lista di kcelle che viene usata dalle mie funzioni area e peso... è una specie di attraversamento in ampiezza senza liste di adiacenza:
flag 0 = cella mai visitata flag = 1 cella scoperta ma non visitata flag = 2 cella visitata.
a partire dalla cella che inserisco come argomenti nella funzione controllo i suoi vicini e li metto a 1 oltre ad inserirli in una lista tipo stack, poi metto a 2 la suddetta cella, poi a uno ad uno dallo stack faccio la stessa cosa...
alla fine dovrebbe funzicare
speriamo!
grazie mille per i consigli!!! :) :)
mah...e se usi solo 1 e 0? non funziona lo stesso?
tanto ti serve solo per non "tornare indietro" ...cioe' prendi la cella che metti come argomento...la poni a 1, metti tutti i suoi vicini a 1 e li poni nello stack, fai la pop(), ti da una cella...metti anche tutti i vicini di questa (che non siano gia' a 1) nello stack, altra pop(), eccetera ovviamente incrementando un contatore ogni volta che colori una cella.
non e' piu' una visita in ampiezza...ma del resto la visita in ampiezza serve per il cammino minimo...a noi non interessa!
anzi direi che si tratta di una visita in profondita'! |
| contezer0 |
correggetemi se ho appena detto una cavolata pero'!
mi rendo conto che devo ripassare parecchio la teoria!
qualcuno ha gia' fatto dei test? ad esempio...se faccio x inserimenti e ci metto un tempo t, e con 10x inserimenti il mio programma ci mette 10t, vuol dire che la complessita' in tempo della funzione inserimento e' logaritmica, giusto?
questo perche' se invece fosse un inserimento in una lista ordinata, e ogni volta beccassi il caso peggiore, all'n-esimo inserimento dovrei fare n-1 confronti...che sommati agli n-2 dell'inserimento appena precedente e cosi' via...sarebbe la sommatoria di n...e quindi O(n^2).
invece se il tempo cresce linearmente vuol dire che faccio un quadrato di un logaritmo in base 2...mi sa che non c'e' scampo e non si riesce a fare meglio di cosi'...almeno a me non vengono in mente altri metodi...qualche consiglio?
il caso medio dell'inserimento in una lista ordinata e' sempre n quadro? |
| sirio |
Originally posted by contezer0
allora...in breve...ho usato 3 alberi, adesso sto decidendo se ottimizzare implementandoli effettivamente tutti diversi (in pratica uno per le 1 celle, uno per le k celle anche se non hanno abbastanza "peso" , e uno per le k celle effettive.
su ognuno di questi in effetti ho bisogno di cose diverse, ma dover riscrivere il cancella(), l'inserisci(), l'inserisci_pesato() e il sistema_adiacenze() per ognuno mi triplicherebbe la lunghezza del codice...
se qualcuno ha seguito il corso mi puo' dire se fiorentini preferisce un codice corto e leggibile a scapito di alcune variabili non utilizzate, oppure una maggiore ottimizzazione a scapito di leggibilita' e dimensione del sorgente?
comunque...sull'albero delle k celle effettive ovviamente eseguo le varie funzioni di numero blocchi, area e peso.
la funza blocchi e' una semplice visita in profondita' ripetuta, in realta' la ricorsione va fatta con due funzioni e non con una sola per poter tener conto delle celle non ancora colorate nelle visite successive.
Ciao, visto che hai finito e che come me hai usato degli alberi mi spieghi come faccio a visitare tutti i nodi di un albero?
In pratica devo valutare il peso del nodo quando cambiano p e q.
Ho scritto questo codice ma non va:
void valutaPeso(nodo *n)
{
if (n->peso >= parR)
// operazioni per inserire nel blocco
}
void cambiaBlocco(nodo *n, valutaPeso(nodo *))
{
cambiaBlocco(n->left, valutaPeso);
cambiaBlocco(n->root, valutaPeso);
cambiaBlocco(n->right, valutaPeso);
}
Grazie |
| maynard80 |
| sono un coglione...ho fatto la matrice come lista di liste.....e mi hanno spiegato solo ora che e' una cazzata...bene...... :( |
| aghito |
ho analizzato un po' la situazione per blocchi()..
dunque l'idea di eskimo mi sembra corretta anche se serve solo 0 e 1 come detto da contezer0.
senza usare lo stack invece si può settare una variabile visita nella kcella dove 0 non visitata,1 visitata 2 visitata e analizzata..
poi si procede nello stesso modo di prima..cioè
prendi la kcella e metti var kblocco della kcella a 1 e variabile visita a 2.prendi i vicini e metti kblocco 1 e visita a 1.poi procedi prendendo elemento con kblocco 1 e visita !=2 e ripeti..
quale sarà la migliore? |
| contezer0 |
Originally posted by sirio
Ciao, visto che hai finito e che come me hai usato degli alberi mi spieghi come faccio a visitare tutti i nodi di un albero?
In pratica devo valutare il peso del nodo quando cambiano p e q.
Ho scritto questo codice ma non va:
void valutaPeso(nodo *n)
{
if (n->peso >= parR)
// operazioni per inserire nel blocco
}
void cambiaBlocco(nodo *n, valutaPeso(nodo *))
{
cambiaBlocco(n->left, valutaPeso);
cambiaBlocco(n->root, valutaPeso);
cambiaBlocco(n->right, valutaPeso);
}
Grazie
la funzione cambiaBlocco mi pare sia definita in modo un po' sbagliato....se devi passare un puntatore a funzione non devi mettere (in questo caso):
void cambiaBlocco(nodo *n, void*(funzione)(nodo *))
ma non sono sicurissimo pero'! okkio quando si lavora coi puntatori a funzione!! |
| pincopallino |
bah, con oggi io dovrei aver finito....quantomeno l'input che c'è nelle specifiche mi ritorna esattamente lo stesso output.....salvo sorprese dovrei aver fatto tutto come si deve =D
ora mi rimane solo da alcolare i tempi.....credo che la complessità del mio progetto sia altissima dato che ho usato solo una lista di adiacenza non ordinata
:D
l'importante è che non dia problemi....
speriam bene |
| aghito |
| chi ha degli input da provare? |
| pincopallino |
Originally posted by aghito
chi ha degli input da provare?
volevo chiedere la stessa cosa |
| skorpius |
Originally posted by pincopallino
volevo chiedere la stessa cosa
io.
Ho fatto una prova di una ventina di comandi assortiti, verificando a mano che l'output fosse corretto.
Se volete li metto entrambi online, ma non so come allegare i due piccoli files. Al limite, li listo all'interno di un messaggio?
Cmq raga, mi dite qualcosa sulla mia domanda circa gli input sprospositati (1 o 2 pagine indietro) ??
Ciao |
| aghito |
| se li posti ci fai un favore,magari anche con gli output prodotti in modo che possiamo confrontarli..va bene anche un copia incolla |
| ghily |
beati voi che siete già arrivati a i test finali :( . Io ho un problema con la funzione crea. Questa funzione deve adnare a cancellare il piano già creato, ovvero le strutture dati che contengono le informazioni,giusto?
Ora io ho una lista che memorizza le celle ed ho creato una funzione che distrugge la lista. Perchè quando chiamo questa funzione nel main funziona e se invece la chiamo nella funzione crea no?
i prototipi sono:
nodo *destroy(nodo *head);
void crea (nodo *head, knodo *h_head[],int p, int q, int newk);
speriamo sia chiaro
chao
Roby |
| aghito |
ho un problema/dubbio
sto usando una coda implementata come lista per gestire delle cose della funzione blocchi()
il codice originale prevede un campo dato.io ho messo 2 campi dato,x e y. come faccio a cambiare il codice seguente?
/*Restituisce il primo elemento della coda.*/
int q_first(q_descriptor *q){
return q->first->dato; }
avevo pensato a:
int q_first(q_descriptor *q){
return q->first->x && q->first->y ; }
però devo assegnarli a due variabili diverse.come si fa? |
| skorpius |
Originally posted by aghito
se li posti ci fai un favore,magari anche con gli output prodotti in modo che possiamo confrontarli..va bene anche un copia incolla
Ecco qua.
Con questi input
c 25 3 5
i 2 2
i 3 1
i 3 3
i 4 1
i 5 1
i 8 4
i 9 3
i 9 4
i 10 2
i 11 2
i 13 8
i 14 4
i 14 5
i 14 7
i 15 4
i 15 5
i 15 7
i 19 2
i 19 3
i 19 4
i 20 2
i 21 1
i 22 0
i 25 1
a 1 0
p 2 1
b
r 25 4
a 1 0
p 2 1
a 3 0
p 3 0
b
e 0 0
e 1 0
e 2 0
i 9 0
i 12 3
i 23 1
i 24 0
R 3
b
a 4 2
p 4 2
r 13 39
b
a 3 0
p 4 1
a 7 0
p 7 0
a 5 1
R 1
b
a 23 1
p 19 3
a 9 1
p 15 7
a 9 0
f
dovreste ricevere questo output:
3
2
4
4
2
6
13
2
0
3
2
4
5
2
0
0
0
8
0
14
1
6
3
3
6
5
Spero di non aver sbagliato il controllo a mano, ma non credo.
Sappiatemi dire se vi torna eh?
Ciao |
| fasa |
| hai inserito l'input che c'è sulla traccia e se con quell'input hai quei risultati mi sa che il tuo codice nn funziona.... |
| fasa |
Qualcuno ha altri test da provare?
Io ho finito e mi dovrebbe andare....forse ha le funzioni con costi alti ma credo di di aver finito.
ho implementato tutto con liste semplici e in pratica ne uso 2generali(una per le 1celle e una per le kcelle)mentre poi ne uso un'altra quasi solo di appoggio per metterci le kcelle di un blocco... |
| skorpius |
Originally posted by fasa
hai inserito l'input che c'è sulla traccia e se con quell'input hai quei risultati mi sa che il tuo codice nn funziona....
beh, mi diresti che output hai tu e dove il mio output risulta diverso dal tuo? |
| fasa |
il mio output con il tuo input è:
6
21
1
2
0
1
4
2
1
8
19
2
2
6
1
3
0
5
9
9
0
3
1
come da traccia
però controlla il tuo post...secondo me hai sbagliato a scrivere gli input...hai copiato quelli sbagliati. |
| eskimo |
fasa, tu con liste semplici lle hai fatte ricorsive? tutte, nessuna o qualcuna??? grazie.... perchè le mie sono tutte iterative, fanno cagare anche se non so neanche ancora se funge, devo ancora scrivere il main.... e riordinare un attimo!
ciao ;) |
| fasa |
| no nn uso liste ricorsive.i tempi di esecuzione con semplici liste nn credo che si possano migliorare...e anche come idee risolutive una volta che scegli di usare delle liste semplici più o meno sono sempre uguali. |
| skorpius |
però controlla il tuo post...secondo me hai sbagliato a scrivere gli input...hai copiato quelli sbagliati.
HAI RAGIONE!!!!!! ho postato l'input della traccia !!!!!!:oops:
Scusate tutti, ecco quello corretto, fatemi sapere.
c 1 2 2
i 0 0
i 1 3
i 2 6
i 3 4
i 3 5
i 4 3
i 4 8
i 5 2
i 5 8
i 6 3
i 6 5
i 6 7
i 10 0
i 8 7
i 9 6
i 9 7
b
a 1 2
p 1 2
i 11 0
i 11 1
b
i 6 6
i 6 4
b
a 2 4
p 4 3
r 4 3
b
a 2 4
p 4 3
r 1 7
b
e 2 1
e 2 4
e 3 2
a 0 0
p 0 1
R 3
b
a 0 0
p 2 0
p 0 2
r 9 1
a 0 0
p 2 0
p 0 2
b
e 2 1
e 0 2
R 1
b
p 9 7
a 9 7
i 7 7
a 6 6
b
f |
| eskimo |
ok fasa... mi hai tranquillizzato... :)
l'ultima cosa: ma l'input si digita tramite tastiera, vero? sul testo c'è scritto che leggo da stdin.... quindi dovrebbe essere da tastiera, il dubbio mi sorge perchè nei primi post del thread tanti parlavano di leggere da un file....
p. |
| fasa |
| ho passato il tuo test skorpius tutto ok!!! |
| fasa |
| ma skorpius tu usi liste semplici o cosa? |
| skorpius |
Originally posted by fasa
ma skorpius tu usi liste semplici o cosa?
Ottimo ! Funzia...
Si, in definitiva l'impostazione è la medesima: lista x le 1-celle inserite, lista x le k-celle con campo occupate ON/OFF e basta così.
Se l'utente chiede qualcosa dei blocchi, ecco che compare la lista dei blocchi, ma solo come appoggio temporaneo.
Ma io non ho finito: sto vedendo se in qualche modo si può aumentare la performance... |
| fasa |
| lo so anch'io dovrei continuare a vedere se riesco a migliorare i tempi di esecuzione ma dopo 2 giorni a pensare come fare mi sono quasi convinto che sia impossibile migliorare il codice che ho fatto mantenendo le strutture pensate.io nn uso il campo on/off per le kcelle in definitiva faccio una solo struct.ma cosa ti serve quel campo?ti aiuta a fare meno ricerce o cosa? |
| skorpius |
| beh, la mia lista delle k-celle include anche quelle libere.....quindi in caso di costruzione blocchi grazie a quel campo le salto subito senza fare ulteriori test..... |
| fasa |
| ah beh...io nn mi preoccupo di inserire anche le kcelle nn occupate tanto nn servono a niente. |
| aghito |
devo solo finire l'elimina...
ho provato il test fino a dove ho potuto,cioè prima del primo e..
risultati come i vostri!!!
bella! |
| skorpius |
Originally posted by fasa
ah beh...io nn mi preoccupo di inserire anche le kcelle nn occupate tanto nn servono a niente.
ci sono pro e contro...metti che l'utente usi il comando r.
Io devo solo verificare se, in base al nuovo rapporto, ogni k-cella esistente è o meno libera...non devo creare nulla in questo caso, solo riaggiornare quel flag. |
| eskimo |
Ciao ho bisogno di aiutoooooo!
il compilatore mi torna sta roba:
<command line>:4:4: missing '(' after predicate
credo che sia un messaggio dell'opzione -ANSI solo che non so proprio che cazzo fare....
qualcuno l'ha già trovata?? la conosce??
thx! thx! :) :) |
| fasa |
| per eskimo:si l'input è da tastiera anche se per tuoi controlli puoi leggere da un file gli input e nn star li a immettere tutti i comandi tu....xò quando lo consegni deve essere da tastiera l'input! |
| fasa |
| per l'errore che dici nn so proprio di cosa si tratta!menomale che a me nn me lo da! :) |
| fasa |
| skorpius hai ragione ti aiuta in quella funzione xò se fai come ho fatto io una funzione che mi crea la lista delle kcelle e la richiami ogni volta che devi ricrearti la lista(cioè in riempimento,risoluzione e inserisci)quel flag nn ti serve....xò così mi si incrementano i tempi di esecuzione delle funzioni...boh....bisogna vedere se ne vale la pena complicarsi la vita con il flag solo per diminuire il tempo di esecuzione di una funzione.... |
| fasa |
| qualcuno sa più o meno com'è un orale con l'aguzzoli? |
| skorpius |
Originally posted by fasa
...boh....bisogna vedere se ne vale la pena complicarsi la vita con il flag solo per diminuire il tempo di esecuzione di una funzione....
in effetti, penso che entrambe le scelte siano pienamente condivisibili....dopotutto, non si sa a priori quante volte un utente possa o meno chiamare un comando..... |
| eskimo |
bene, sono arrivato alla fine e non funge... forse ho anche capito gli errori ma: le funzioni da implementare che ci chiede lui, ad esempio crea(p, q, k) o inserisci(x, y) devono avere proprio quei parametri o possono essere modificate? cioè va bene fare una funzione inserisci(k, x, y) ad esempio se mi dovesse servire passare un altro valore oltre ad x e y???
grazie.... p. |
| ghily |
Originally posted by eskimo
bene, sono arrivato alla fine e non funge... forse ho anche capito gli errori ma: le funzioni da implementare che ci chiede lui, ad esempio crea(p, q, k) o inserisci(x, y) devono avere proprio quei parametri o possono essere modificate? cioè va bene fare una funzione inserisci(k, x, y) ad esempio se mi dovesse servire passare un altro valore oltre ad x e y???
grazie.... p.
anche io ho lo stesso problema. Praticamente le funzioni crea e inserisci non vanno come dovrebbereo. In più mi mancano da implementare le funzioni sui k-blocchi. Per cui mi sa che mi arrendo e che lo ridarò a gennaio.Speriamo in bene. Vedo già Goldwrun dietro l'angolo.......
Chao
Roby |
| eskimo |
| Non so io me ne fotto altamente: le funzioni le adatto come mi pare, mancano due giorni e lo voglio funzionante... |
| fasa |
LE funzioni che il problema dice di fare devono essere come sono sulla traccia.anch'io avevo quei problemi....ho risolto usando 3 variabili globali....che l'aguzzoli nn dice di nn usare!
ci sono disponibili altri test?io consegno gia stanotte a mezzanotte xchè nn ne voglio più sapere di questo progetto nel week end!!!come va và!!!!Piu o meno quanti riusciranno a consegnare? |
| pincopallino |
Originally posted by fasa
...Piu o meno quanti riusciranno a consegnare?
a me manca da scrivere solo la relazione e poi dovrei consegnare....l'unico è che non ho fatto molti test sul progetto a parte quello delle specifiche e pochi altri.... |
| fasa |
beh quello anch'io...è per questo che sto cercando se qualcuno ha qualche test da postare.... :)
pincopallino ma tu che struttura dati hai usato? |
| ghily |
Originally posted by fasa
LE funzioni che il problema dice di fare devono essere come sono sulla traccia.anch'io avevo quei problemi....ho risolto usando 3 variabili globali....che l'aguzzoli nn dice di nn usare!
ci sono disponibili altri test?io consegno gia stanotte a mezzanotte xchè nn ne voglio più sapere di questo progetto nel week end!!!come va và!!!!Piu o meno quanti riusciranno a consegnare?
praticamente hai creato come variabili globali le lsite?? Se faccio così funziona anche a me. Mi apri uno spiraglio di luce. Ma finire il prgoetto in due giornate la vedo scura. In effetti aguzzoli non vieta le variabili globali. Consigliate di provarci? Non è che abbia tutta sta voglia....
chao
Roby |
| fasa |
esatto e oltre alle liste dichiaro 3 variabili globali anche per k, p e q.
secondo ti conviene provare...saRà difficile trovare altri progetti così "facili"... :) |
| Eruyomë |
| Anch'io ho usato variabili statiche esterne, come lo mantieni memorizzato se no il piano, con tutte le operazioni che ci devi fare? |
| ghily |
Originally posted by fasa
esatto e oltre alle liste dichiaro 3 variabili globali anche per k, p e q.
secondo ti conviene provare...saRà difficile trovare altri progetti così "facili"... :)
verissimo. Però ormai ho praticamente gettato la spugna. Dovevo pensarci prima. Ci proverò ancora, però visto che ho un 27 nella teroia non voglio fare un brutto progetto.
Chao
Roby |
| aghito |
ma io non penso che sia così restrittivo il progetto
io invece di crea(p,q,k) ho messo
crea(&root,&rootk,ap,aq,ak,parametro,indice,ris_k);
non penso sia così grave o sbaglio? |
| fasa |
| IO HO APPENA CONSEGNATO cmq credo che su poche cose il progetto è restrittivo e una di queste sono le 8funzioni che ti dice di creare!o almeno credo di aver capito dal testo così!!! |
| fasa |
| x ghily:nn so a che punto sei ma mi pare di aver capito che se dichiari le variabili in generale dovresti aver finito e allora cosa ti fa nn consegnare?considerando anche che mancano 2 giorni pieni ancora prima del termine della consegna! |
| ghily |
Originally posted by fasa
x ghily:nn so a che punto sei ma mi pare di aver capito che se dichiari le variabili in generale dovresti aver finito e allora cosa ti fa nn consegnare?considerando anche che mancano 2 giorni pieni ancora prima del termine della consegna!
Preso da nuovo stimolo mi sono messo a rilavorare sul progetto. Ora però ho messo ben 5 variabili globali..... Il progetto funziona bene.Ho praticamente già implementato crea,inserisci, modifica.
Ora faccio elimina poi vado a riposarmi. Domani devo fare assolutamente le funzioni sui blocchi.Però non so come fare per sapere quando ho finito la visita su quel blocco.. :? Ci penserò....
Non mollare mai
Chao
Roby
P.S: :lode: fasa |
| Dante |
| Avevo fatto la funzione area e peso che mi dava i risultati giusti... ma poi mi sono accorto che erano sbagliate... uso una lista ke contiene le kcelle. con una funzione che scorre tutta la lista cerco, a partire dalla kcella data (a, x, y) le sue confinanti mettendo il loro flag a 1, poi scorro ancora la lista cercando quelle con flag nn a 1 e cerco le confinanti e le pongo a 1... così fino a fine lista... il problema è che se ci sono 2 kcelle confinanti, anche staccate dal kblocco a cui appartiene (a x y ), me le conta pure quelle, mi sbaglia il peso e nn so distinguerle per contare i blocchi... cazzo di budda... devo ripensare ancora la funzione area... come caspita si fa? |
| fasa |
per finire la visita di un blocco basta vedere quando l'ultima kcella del blocco nn ha più nuove kcelle adiacenti.
mi sa che mi sono spiegato da cane
scusa... |
| fasa |
| dante nn ti conviene usare una lista blocco(come appoggio)dove inserisci con una funzione a parte tutte le tue kcelle del blocco?io ho fatto così e va alla grande!!!poi dopo mi basta scorrere quella lista e contare quanti elementi ha per trovare l'area! |
| Polo |
Quando Consegnate voi la copia cartacea
Dato che domenica il dipartimento è chiuso? |
| ghily |
Originally posted by Polo
Quando Consegnate voi la copia cartacea
Dato che domenica il dipartimento è chiuso?
Se lo fai con Aguzzoli: l'importante è mandarli il progetto via mail. Provvederai successivamente alla consenga della copi acartacea (io se riesco a finirla consegno il 4);
Se lo fai con Torelli: da quello che ho capito la devi consegnare il 4.
In sostanza cambia ben poco.....
IO voglio farcela a conseganre.....Anche alle 23.59 di domani senza aver fatto alcun test. Non fa nulla.
Chao
Roby |
| aghito |
be fiorentini dice di consegnare codice e relazione entro domenica e di lasciare cartaceo nella sua casella in comelico lunedì.
ho ufficialmente finito!!!
devo solo vedere se è il caso di rifare tutto con variabili globali
per avere crea(p,q,k)..invece di
crea(&root,&rootk,ap,aq,ak,parametro,indice,ris_k);
intanto funziona e ciò è importantissimo |
| Polo |
Quindi Conta come consegna quella E-mail ,te lo ha assicurato il prof?
Io ho finito ma dovrei fare oggi pomeriggio 60 km solo per consegnare una decina di fogli mi scazzerebbe un po.
|
| aghito |
| nell'email metti anche la relazione in pdf..quindi poi devi solo stamparla e consegnarla dopo |
|
|
|
|
