.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)

qualcuno mi spiega gentilmente la funzione area e come mai nel primo sempio del prof l'output prodotto da a 1 0 0 è 6?

Grazie

ho capito perchè l'area da 6 ma non sono sicuro sul modo di calcolo del blocco. Aiutino?

altro problema: sempre negli esmpi del testo, si arriva ad un certo punto all'input R 3. Ciò vuol dire che imposto la risoluzione a 3 tenendo sempre come riempimento quello precedente che nel nostro caso è 4/25 giusto?

Ora per avere una occupata devo avere al suo interno almeno pk^2/q 1-celle, nel nostro esempio abbiamo 4*9/25=36/25=1.44
Che si fa si considerano 1 o 2 celle?
A questo punto però arriva l'istruzione b che da come out 1, perchè? dove sbaglio?

area 1 0

Anche a me viene 6, e secondo me xchè ci sono 6 5-celle nel blocco della 5-cella(1,0):
la 1,0 la 0,0 la 2,0 la 2,1 la 3,1 e la 4,1.

Piuttosto c'è secondo me un altro problemino:
supponiamo venga dato il comando c 1 3 5.
Il rapporto è 1/3, ma 1/3*5^2 = 8,33 periodico.
Allora quante 1-celle devono essere presenti perchè la 5-cella sia considerata occupata? 8 o 9 secondo voi?

ehi!

ehi Mitnik, abbiamo individuato lo stesso problema insieme eh?

Si tratta di numeri interi, il primo intero maggiore di 8,33 è 9 quindi servono 9 1-celle

ok

L'ho pensata alla fine anch'io così, tra l'altro questa considerazione coincide (ed è l'unico modo) con l'esempio del prof che diceva mitnik

ma state facendo simulazioni "carta e matita" del progetto?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

L'implementazione migliore del piano è sicuramente una tabella di hash dinamica con una funzione biunivoca che assoccia una coppia (x,y) ad un valore k, che viene passato alla funzione di hash.
Sul libro di algoritmi c'è spiegato come funziona una tabella dinamica(una tabella che si allarga e si restringe dinamicamente a seconda del fattore di carico), ma va implementata.
In ogni caso ha performance molto buone, dato che la ricerca è in tempo O(1).
Sulle dispense di Torelli mi han detto che c'è la funzione biunivoca per ottenere k dalla coppia (x,y).

Pero la tabella di Hash ha una dimensione fissa,non puo implementare un piano infinito.. :-(

Originally posted by rach
Pero la tabella di Hash ha una dimensione fissa,non puo implementare un piano infinito.. :-(

ok allora si utilizza il numero intero piu vicino e maggiore di quello trovato.

scusate ma la funzione crea secondo me deve solo memorizzare i parametri k e p/q o q/p e poi "cancella" o meglio svuota la struttura dati che state usando per memorizzare le 1-celle. Questo perchè il piano deve essere infinito quindi servirebbe una struttura per memorizzare infinite k-celle al suo interno.

Lo so mi sono spiegato da schifo però scrivere in poche righe quello che si pensa per il progetto è difficile.

Ciao

Ciao, visto che la soluzione con la tabella di hash dovrebbe essere la soluzione da guru vediamo se si può fare: nella tabella ci metto tutte le celle? e la funzione biunivoca (x, y -> k e viceversa) mi porta alla cella giusta a seconda della risoluzione k?? se non è così credo di non averci capito na mazza ma non voglio già mettermi nell'idea di fare tutto con le liste!!
altrimenti liste di adiacenza con tutte le 1-celle dentro e poi calcoli a manetta ogni volta che devo sapere se a una certa risoluzione quella k-cella è piena o no, calcolo di blocchi, ecc ecc ecc
....sigh....
P.

Originally posted by mitnik
scusate ma la funzione crea secondo me deve solo memorizzare i parametri k e p/q o q/p e poi "cancella" o meglio svuota la struttura dati che state usando per memorizzare le 1-celle. Ciao