.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [ALGORITMI]Progetto Zoom (http://www.dsy.it/forum/showthread.php?threadid=13146)

numeri naturali

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?

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.

__________________
Io sono la fata verde. Sono la rovina e il rimpianto, la vergogna e il disonore. Io sono la morte, io sono l'assenzio...

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

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?

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?

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?

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!!!

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!!!

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?

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.

sono un coglione...ho fatto la matrice come lista di liste.....e mi hanno spiegato solo ora che e' una cazzata...bene......

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

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?

__________________
alessandro colombini

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

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



l'importante è che non dia problemi....
speriam bene

__________________
"Che ne sai di un ragazzo che ti amava
che parlava e niente sapeva
eppur quel che diceva chissà perchè‚ chissà adesso è verità."

chi ha degli input da provare?

__________________
alessandro colombini