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

no, no la struttura non deve avere una grandezza di partenza, anche un arrey può aumentare dinamicamente, lui vuole una struttura malleabile che sia ottimizzata al problema.

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

nella tabella di hash memorizzereste solo le 1-celle, giusto?
Quindi data una k-cella, per capire se è occupata, bisognerebbe applicare la funzione di hash a ogni 1-cella contenuta nella k-cella. Al limite ci si potrebbe fermare quando il numero di 1-celle occupate in un certo momento della scansione è già >= pk^2/q.

Originally posted by maynard80
ma non si puòridurre il piano alle celle occupate? nel senso che semplicemente le celle libere non ci sono, quindi il mio pisno "infinito" in realtà non è altro che una lista delle celle occupate ordinate secondo le loro x,y.
In questo modo una cella è occupata se esiste nella lista, libera altrimenti, le celle sono adiacenti se le loro x o y sono consecutive ecc..
Forse sto rasentando l'idiozia, ma magari semplicemente potrebbe funzionare, no?

__________________
"Why, Sir, you find no man at all intellectual who is willing to leave London.
No, Sir, when a man is tired of London, he is tired of life; for there is in London all that life can afford."
(DR SAMUEL JOHNSON 1777)

MSN andrea.poretti(at)hotmail.it

Appena letto il progetto...

Buongiorno a tutti,

per motivi di tempo & lavoro, ho cominciato a pensare al progetto solo poco fa.

Vedo dalla discussione che la struttura dati di base dovrebbe essere una hash table per le 1-celle. Ciò effettivamente garantirebbe tempi ottimali per la ricerca, l'inserimento la cancellazione di una 1-cella (entro buoni limiti, anche con risoluzione dei conflitti con liste concatenate). Per trattare le k-celle, la mia idea sarebbe di scorrere tutti gli elementi della hash table e controllando in quale k-cella cadono, ovviamente appena trovo un elemento di una k-cella non esistente creo tale k-cella.
Il problema di verificare i k-blocchi compare sia per k generico che in particolare per k=1. A questo punto sono bloccato - o la cosa è troppo semplice da non vederla o troppo complicata - sulla relazione di adiacenza. Per ciò che è scritto nel prog. mi è sembrato di capire che le k-celle (per le 1-celle è verificabile) siano adiacenti se hanno almeno un punto (suppongo di confine) in comune. Quindi, data una k-cella, questa può avere al massimo 8 k-celle adiacenti (1 lato in comune, o al più uno spigolo).
S'ha da verificare dunque per ogni k-cella le 8 posizioni adiacenti, o esiste una strategia (nn avendo potuto seguire il corso di Torelli...) più raffinata?

Grazie per eventuali risposte, e buon lavoro

G. "VdM"

secondo me non conviene memorizzare infomazione riguardo alle k-celle, perchè in qualsiasi momento l'utente può modificare risoluzione, parametro di riepimento nonchè celle occupate.
L'informazione riguardo le k-celle mi sembra quindi poco riutillizabile.

La soluzione proposta da torak sembra poter funzionare però non mi convince in quanto quello scritto nel 18.4 si può applicare a qualsiasi struttura statica tipo pile code e matrici di array che sono esplicitamente vietate. Io userei una lista in cui segnare le sole 1-celle occupate..usare un albero non mi sembra utile.infatti se l’input fosse quello dell’esempio si avrebbe un albero alto n dati n input in quanto ogni elemento è sempre maggiore del precedente..

Partendo da questa lista quando ho la risoluzione k creo una nuova struttura dati tramite una funzione che facendo una scansione della lista associa ogni 1cella occupata alla rispettiva k-cella..alla fine conto le 1-celle di ogni k-cella e vedo se è occupata..per blocchi ci sto pensando…

__________________
alessandro colombini

Per definizione....una K-cella esiste solo se è okkupata..giusto??

__________________
"Why, Sir, you find no man at all intellectual who is willing to leave London.
No, Sir, when a man is tired of London, he is tired of life; for there is in London all that life can afford."
(DR SAMUEL JOHNSON 1777)

MSN andrea.poretti(at)hotmail.it

esatto. Secondo me le k-celle ci stanno "sviando" nel senso che la cosa importante sono le 1-celle che vanno memorizzate in una struttura dati, (io penso di usare una lsta) quando poi si fanno le varie operazioni tipo quella di blocchi, peso... entreranno in gioco le k-celle che in realtà sono sempre nel piano in numero infinito e dipendono dalla risoluzione.
Ok, a questo punto io creerei una struttura dati di supporto che puo essere un'altra lista. Questa avrà un puntatore a dx e uno giu, a dx si mette l'informazione della k-cella OCCUPATA e giu si mettono le 1-celle che la occupano.
Puo andare? che ne dite?

Ciao

Originally posted by aghito
La soluzione proposta da torak sembra poter funzionare però non mi convince in quanto quello scritto nel 18.4 si può applicare a qualsiasi struttura statica tipo pile code e matrici di array che sono esplicitamente vietate. Io userei una lista in cui segnare le sole 1-celle occupate..usare un albero non mi sembra utile.infatti se l’input fosse quello dell’esempio si avrebbe un albero alto n dati n input in quanto ogni elemento è sempre maggiore del precedente..

Partendo da questa lista quando ho la risoluzione k creo una nuova struttura dati tramite una funzione che facendo una scansione della lista associa ogni 1cella occupata alla rispettiva k-cella..alla fine conto le 1-celle di ogni k-cella e vedo se è occupata..per blocchi ci sto pensando…

Anche secondo me ci vogliono più strutture dati o almeno bisogna tenere le info sulle attuali k-celle. L'utente può ogni volta cambiare risoluzione o fattore riempim. e in questo caso si rifà la struttura che memorizza le k-celle.... così si fanno calcoli sulla struttura delle 1-celle ogni volta che bisogna cambiare risoluzione o fattore riemp, mentre si lavora sulle k-celle se bisogna fare calcoli tipo area, peso o blocchi.
credo che il costo di due strutture dati sia minore del costo di fare molte operazioni sempre su ste 1-celle....

il problema di come dici tu mitnik è che bisogna tenere info di una k-cella anche se ha solo una 1-cella ed è considerata libera e visto che non sai a che risoluzione stai lavorando, come distribuisci le 1-celle? lo puoi fare secondo la risoluzione corrente ma ad ogni cambio di risoluzione devi rifare proprio tutto! se sai come affrontare il prob fammi sapere che è una sol che mi piace...

per favore, alcune persone cerchino di scrivere più chiaro altrimenti non si capisce un c..zo e perdiamo tutti un casino di tempo.

Re: Appena letto il progetto...

Originally posted by VdM
Quindi, data una k-cella, questa può avere al massimo 8 k-celle adiacenti (1 lato in comune, o al più uno spigolo).
S'ha da verificare dunque per ogni k-cella le 8 posizioni adiacenti, o esiste una strategia (nn avendo potuto seguire il corso di Torelli...) più raffinata?

cavolo è un casino verificare se una 1-cella è contenuta in una k-cella. Avete idee a proposito?

Originally posted by mitnik
cavolo è un casino verificare se una 1-cella è contenuta in una k-cella. Avete idee a proposito?

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

Originally posted by pincopallino
bhe della k-cella presa in considerazione sai la coordinata in basso a sx, quindi ti calcoli le coordinate in alto a dx, e per sapere se una 1-cella è contenuta in quella k-cella basta che confronti le coordinate della 1-cella con quelle della k-cella. tipo la k-cella ha coordinate (0,0) la risoluzione è 3, per verificare se una 1-cella(x,y) è contenuta in quella k-cella basta controllare: 0<= x < 3, 0<= y < 3.....

io farei così......sonostata spiegata?

__________________
"Why, Sir, you find no man at all intellectual who is willing to leave London.
No, Sir, when a man is tired of London, he is tired of life; for there is in London all that life can afford."
(DR SAMUEL JOHNSON 1777)

MSN andrea.poretti(at)hotmail.it