 | |
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 |
| Skilotto83 |
Apro il thread per il progetto...visto ke mi cimentero' nel farlo...
Se nn sbaglio è piuttosto semplice rispetto a quelli passati...e sikuramente piu' semplice di Banchetto di Luglio...
Voi avete idee??
Consigli??
Insomma...rimbokkiamoci le manike... |
| ghily |
Lo provo anche io in questo appello. In effetto quello di luglio era parecchio difficile.Ora lo stampo e mi metto a ragionarci un po'.
In bocca al lupo a tutti
Chao
Roby |
| karlost |
Potremo aiutarci mutamente sulle cose più importanti, strutture dati da utilizzare e valutazione e costi delle prestazioni che seconde me è la parte più difficile.
Buon lavoro a tutti! |
| aghito |
si sicuramente aiutarsi va benissimo...
la cosa positiva è che il testo è molto chiaro su cosa si deve fare...
la parte difficile è l'implementazione..direi che sarebbe utile che ciascuno dica che stutture dati usare e perchè...ora me lo studio un po'...forza raga un po' d'impegno e lo passiamo sicuro!! |
| maynard80 |
| dunque sicuramente la matrice va fatta con una lista di adiacenze (come in tutti i passati progetti) io non so ancora bene implementare una lista....... chi mi illumina? |
| Skilotto83 |
Ma quando dice che nn è efficente implementare ilò piano kome una matrice intende dire kome un array bidimensionale??
A me sembrerebbe la kosa piu' logika..ma in effetti poi perderebbe senso il progetto... |
| maynard80 |
| beh probabilmete scorrere un array bidimensionale NxN sarebbe "costoso" in termini di efficenza |
| aghito |
si penso che come matrice si riferisca ad array bidimensionali perchè in quel caso bisogna porre un indice finito e lui non vuole vincoli di questo tipo.
ho un dubbio: dice che il parametro di riempimento è p/q con 0<p<=q poi però la funzione crea(p,q,k) imposta il parametro al valore minimo tra p/q e q/p..non è una contraddizione con quello detto prima?
infatti nell'esempio c'è c(25,3,5) e quindi p > q.
quindi una cella è occupata se ha almeno (3/25)*5*5=3 1-celle occupate ,giusto? |
| pincopallino |
Originally posted by aghito
ho un dubbio: dice che il parametro di riempimento è p/q con 0<p<=q poi però la funzione crea(p,q,k) imposta il parametro al valore minimo tra p/q e q/p..non è una contraddizione con quello detto prima?
infatti nell'esempio c'è c(25,3,5) e quindi p > q.
su questo hai ragione, effettivamente è una contraddizione, cavolino...
quindi una cella è occupata se ha almeno (3/25)*5*5=3 1-celle occupate ,giusto?
Questo mi sembra giusto, sempre che io non abbia sbagliato a capire il tutto |
| sirio |
Originally posted by aghito
si penso che come matrice si riferisca ad array bidimensionali perchè in quel caso bisogna porre un indice finito e lui non vuole vincoli di questo tipo.
ho un dubbio: dice che il parametro di riempimento è p/q con 0<p<=q poi però la funzione crea(p,q,k) imposta il parametro al valore minimo tra p/q e q/p..non è una contraddizione con quello detto prima?
infatti nell'esempio c'è c(25,3,5) e quindi p > q.
quindi una cella è occupata se ha almeno (3/25)*5*5=3 1-celle occupate ,giusto?
Anch'io concordo con la tua osservazione, come ci comportiamo? |
| Skilotto83 |
Diciamo ke il progetto l'ho kapito..mi manka di kapire da dove iniziare...
:-D |
| aghito |
| allora siamo in 2! :-D |
| Polo |
La matrice di adiacenza la usereste per vedere quali blocchi sono connessi fra loro??
Perchè io implementerei tutto con un albero di ricerca. |
| aghito |
ho chiesto al prof riguardo il mio dubbio ecco la risposta:
> ho un dubbio: nel testo si dice che il parametro di riempimento è p/q
> con 0<p<=q poi però la funzione crea(p,q,k) imposta il parametro al
> valore minimo tra p/q e q/p..non è una contraddizione con quello detto
> prima?
> infatti nell'esempio c'è c(25,3,5) e quindi p > q.
>
p e q, k in crea(p,q,k) sono nomi arbitrari di parametri
(se le crea confusione, sostituisca crea(p,q,k) con crea(a,b,c) e
modifichi in modo coerente la specifica).
Poiche' qui non si richiede p<q, perche' l'operazione abbia senso
occorre prendere il minimo tra p/q e q/p.
Quindi in
c(25,3,5)
il parametro di riempimento e' 3/25 (non 25/3)
> in ogni caso il numero di 1 celle occupate per far si che la cella
> 3-cella sia occupata è (3/25)*5*5=3 ,giusto?
>
Si
questione risolta! |
| fraile |
| Ke ne dite di una tabella hash!!?? |
| aghito |
domanda apparentemente stupida
l'input può essere rediretto tipo a < in.txt?
in tale file devo scrivere
c 25 3 5
i 2 2
i 3 1
a 1 0
p 2 1
b
e 5 0
r 25 8
R 4
f
oppure
c 25 3 5 \n
i 2 2 \n
i 3 1 \n
a 1 0 \n
p 2 1 \n
b \n
e 5 0 \n
r 25 8 \n
R 4 \n
f \n
cioè l'andare a capo viene riconosciuto automaticamente o devo dire quando trovi \n fermati e fai operazioni della linea? |
| Polo |
se scrivi
qualcosa \n
qualcosaltro.
è come se mettessi 2 a capo ,sono due modi diversi per scriverlo.
quindi nel file di input scrivi normale nel codice per dividere un comando dall'altro dovrai riconoscere \n.
(era questo che chiedevi?) |
| aghito |
si era questo.
ma per riconoscere \n come si fa?
se uso isspace non fa distinzioni tra spazio o a capo. |
| Polo |
| negli abbozzi degli altri progetti dove ,comunque, si presentava un problema simile prendevo un carattere alla volta e con un costrutto switch sceglievo cosa fare.Inoltre \n è un carattere qulasiasi quindi lo puoi trattare come un integer non c'è bisogno di usare funzioni strane. |
| aghito |
\n ha un valore ascii?
se si si potrebbe fare leggi caratteri e inseriscili in un array finche non incontri valore ascii associato a \n
il problema si pone perchè si deve capire quando finisce una riga.
a meno che si fa leggi il primo carattere che è un carattere e poi prendi tutte le cifre che ci sono prima del carattere successivo
c 25 3 5
i 4 5
leggi c e poi tutti fino a i |
| Skilotto83 |
Originally posted by aghito
\n ha un valore ascii?
se si si potrebbe fare leggi caratteri e inseriscili in un array finche non incontri valore ascii associato a \n
il problema si pone perchè si deve capire quando finisce una riga.
a meno che si fa leggi il primo carattere che è un carattere e poi prendi tutte le cifre che ci sono prima del carattere successivo
c 25 3 5
i 4 5
leggi c e poi tutti fino a i
se fai kosi' legge anke /n...ke nn deve essere un argomento della funzione crea..quindi mi sa ke qlks nn va... |
| aghito |
avevo pensato
int main(void){
......
printf("inserire linea:\n");
do{scanf("%c",&i);
switch(i){
case 'c': /* crea piano */
scanf("%d",&p);
scanf("%d",&q);
scanf("%d",&k);
/*crea(p,q,k); */
printf("carattere:%c \n p:%d \n q:%d \n k:%d \n e poi crea()\n\n",i,p,q,k);
break;
case 'i': /* aggiunta di un elemento */
scanf("%d",&a);
scanf("%d",&b);
printf("carattere:%c \n a:%d \n b:%d \n e poi inserisci()\n\n",i,a,b);
break;
}
}
while (i!='f'); /*
cioè fino a che non trovi f fai swicth..se c'è c leggi le successivie 3 cifre,se i 2 se R 1 e fai operazione associata....
l'output è:
inserire linea:
carattere:c
p:25
q:3
k:5
e poi crea()
carattere:i
a:2
b:2
e poi inserisci()
carattere:i
a:3
b:1
e poi inserisci()
mi sembra funzionante.cosa ne pensate? |
| maynard80 |
si, dovrebbe funzionare.
allora abbiamo capito come implementare il piano? amici continuano a dirmi "lista di adiacenze"..... ma non so da dove partire! |
| aghito |
finora le idee sono state:
liste di adiacenza
matrici di adiacenza
heap
albero di ricerca
NO matrici con array
sarebbe utile che chi le ha proposte spieghi perchè le vuole usare |
| mitnik |
Ma se una 1-cella è occupata lo devo decidere io?
Quindi se lo decido io le k-celle saranno occupate solo se ho unserito al loro interno un numero sufficiente di 1-celle occupate. Giusto o sbagliato? |
| pincopallino |
Originally posted by mitnik
Ma se una 1-cella è occupata lo devo decidere io?
Quindi se lo decido io le k-celle saranno occupate solo se ho unserito al loro interno un numero sufficiente di 1-celle occupate. Giusto o sbagliato?
giusto, una 1-cella è occupata quando fai un inserimento.
le k-celle sranno occupate solo se al loro interno avranno (pk^2/q) 1-celle occupate, altrimenti la k-cella è libera |
| Flyzone |
Ragazzi...non sono mica riuscito a capire una cosa sulla creaazione del piano: nell'esempio mette un
c 25 3 5
quindi dovrebbe creare un piano da 25x3 di 5-celle (risoluzione 5), di conseguenza 125x15 da 1-celle...giusto? :pensa: |
| pincopallino |
Originally posted by Flyzone
Ragazzi...non sono mica riuscito a capire una cosa sulla creaazione del piano: nell'esempio mette un
c 25 3 5
quindi dovrebbe creare un piano da 25x3 di 5-celle (risoluzione 5), di conseguenza 125x15 da 1-celle...giusto? :pensa:
o ti sei spiegato male, o non hai capito niente, o non ho capito niente io.....
se non ho capito male, c 25 3 5 crea un piano vuoto con un numero di 1-celle infinite e con un numero di k-celle infinite, e pone la risoluzione a 5. Ovvero, tutte le k-celle hanno lato lungo 5 (quindi ogni k-cella è formata da 5x5 1-celle), mentre i numeri 25 e 3 se non erro ti servono per calcolare il parametro di riempimento facendo il min(25/3, 3/25)........
Se qualcuno la pensa diversamente da e pensa che io abbia capito male me lo può dire per cortesia? così se ne può discutere altrimenti io vado avanti col mio pensiero..... |
| h3mpt0n |
| bravo pincopallino, anch'io concordo con te |
| mitnik |
penso che sia giusto come dice pincopallino
In sostanza tu crei un piano di dimensioni infinite e di una certa risoluzione. Il piano infinito viene messo in ogn i progetto, se fosse altrimenti non sarebbe sconsigliato l'uso di matrici
Ciao |
| mitnik |
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 |
| mitnik |
| ho capito perchè l'area da 6 ma non sono sicuro sul modo di calcolo del blocco. Aiutino? |
| mitnik |
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? |
| skorpius |
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? |
| skorpius |
| ehi Mitnik, abbiamo individuato lo stesso problema insieme eh? :) |
| attila79 |
| Si tratta di numeri interi, il primo intero maggiore di 8,33 è 9 quindi servono 9 1-celle |
| skorpius |
| 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 |
| maynard80 |
| ma state facendo simulazioni "carta e matita" del progetto? |
| torak |
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). |
| rach |
| Pero la tabella di Hash ha una dimensione fissa,non puo implementare un piano infinito.. :-( |
| sirio |
Originally posted by rach
Pero la tabella di Hash ha una dimensione fissa,non puo implementare un piano infinito.. :-(
Vero. Ma le celle che cadono in una stessa posizione possono essere infinite, anche se l'efficenza però si va a benedire |
| mitnik |
| ok allora si utilizza il numero intero piu vicino e maggiore di quello trovato. |
| 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. 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 |
| eskimo |
Ciao, visto che la soluzione con la tabella di hash dovrebbe essere la soluzione da guru :cool: 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. |
| skorpius |
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
Si, anche secondo me.
Tra l'altro, confermatemi che il c deve essere x forza il 1° comando dato al programma.......non si possono avere inserimenti i prima di aver definito i 3 parametri vero? |
| mitnik |
secondo me la soluzione più semplice consiste in una lista che contiene le 1-celle, questo però complica un po il resto delle operazioni nel senso che si devono fare milti calcoli e scorrere la lista parecchie volte per funzioni tipo area. Si può usare però una struttura di supporto che memorizza le 1-celle contenute in un blocco. Bho che dite?
Si skorpius penso che la prima opeazione sia la crea. |
| aghito |
si prima cera poi inserisci un po' di cose e alla fine f
io direi che si memorizzano solo le celle occupate cioè inserite.
mi dicevano di usare un albero di ricerca binario per memorizzare tali celle e poi delle liste per mantenere di ogni cella le celle occupate adiacenti |
| aghito |
la tabella di hash sarà anche la soluzione da guru ma io non lo sono e guardando sul libro a me sembra molto difficile da fare. dato che il 18 va più che bene mi sa che non la userò...
ma degli alberi cosa ne dite..potrebbe essere una alternativa? |
| ghily |
Originally posted by mitnik
secondo me la soluzione più semplice consiste in una lista che contiene le 1-celle, questo però complica un po il resto delle operazioni nel senso che si devono fare milti calcoli e scorrere la lista parecchie volte per funzioni tipo area. Si può usare però una struttura di supporto che memorizza le 1-celle contenute in un blocco. Bho che dite?
Si skorpius penso che la prima opeazione sia la crea.
anche io avevo pensato di usare le liste. Logicamente i tempi di ricerca non sono ottimali perchè bisogna fare più visite sulla lista per ottenere un risulato. Ma davvero a noi ci importa?? oppure è meglio scrivere un programma che funzioni?? Capendo però dove è il lato migliorabile del progetto.Almeno teoricamente.
Chao
Roby |
| Paolo74GRS |
Mi ci metto anch'io..
Pensare il piano delle 1-celle inserite come liste di adiacenza e servirsi poi di un albero di supporto per la parte di ricerca??
Potrebbe andare no? |
| Eruyomë |
| ma per lista di adiacenza intendete una lista di liste? Cioé, una lista per le ascisse che contiene liste con le ordinate? |
| Tosh |
| Chi ha proposto la tabella di hash potrebbe illustrare un po' come applicherebbe la soluzione al problema? |
| LazerPhEa |
Originally posted by Tosh
Chi ha proposto la tabella di hash potrebbe illustrare un po' come applicherebbe la soluzione al problema?
Se vai qui trovi tutto quello che ti serve, compresi esempi di codice C!
IMO comunque non serve un hash ad indirizzamento aperto; gestisciti le collisioni con le liste concatenate e sei a posto! :approved:
Io nel mio progetto ho fatto così ed è andato tutto liscio... |
| Paolo74GRS |
Partiamo dall'idea di inserimento dei vari punti (X, Y)..
La prima ipotesi, secondo me, e' di utilizzare delle liste di adiacenza.. Ma a quel punto mi sorge un dubbio: e' possibile utilizzare una rappresentazione con liste di adiacenza se il mio grafo puo' essere non connesso??
Potrei avere alcune 1-celle inserite che rappresentano una struttura non connessa all'intero grafo..
Vero? In pratica una foresta..
Ditemi se ci sono oppure sto andando fuori strada!!! |
| marchinkus |
Ragazzi, aiutatemi, la formulina per sapere quando una k-cella è piena, è chiara.
Il problema è:supponendo di avere inserito 5 1-cella in posizioni disparate sul piano, come pensate di fare per controllare se esiste qualche k-cella piena????? |
| attila79 |
Una tabella hash ha le dimensioni fissate, cosa succede se tutta la tabella è occupata da elementi? Come si fa ad aumentare le dimensioni se e possibile? Mi spiego meglio, nel caso voglia utilizzare la tabella hash per contenere le 1-celle se arrivo ad un punto in cui la tabella e piena, la posso allargare ? se si come?
grasias per l'eventuale risposta |
| Skilotto83 |
Originally posted by marchinkus
Ragazzi, aiutatemi, la formulina per sapere quando una k-cella è piena, è chiara.
Il problema è:supponendo di avere inserito 5 1-cella in posizioni disparate sul piano, come pensate di fare per controllare se esiste qualche k-cella piena?????
teorikamente kontrolli dalla posizione in cui sei se aggiungendo uno alla cordinata x e uno alla y vai in una posizione occupata...e kontinui kosi' fino a quando hai aggiunto K a x e y....
quindi kn K=3 da (3,4) aggiungi fino a (6,7)...e vedi se il numero di celle trovate okkupate è maggiore al fattore di riempimento...
se si' hai una K-Cella!
Piuttosto...kome pensate di risolvere il problema della funzione ke restituisce il numero di blokki sul piano???
La vedo dura... Anke perkè bisogna skndie tutto il piano...ke potenzilmente è infinito....potrei avere una K-cella e quindi un blokko anke a 2000 celle di distanza...sparsa in mezzo al piano...no?? |
| 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? |
| marchinkus |
| se non ho capito male, guardando la figura 1, creando un piano K , creo automaticamente una infinità di celle predefinite, ogni 2 posizioni, ogni 3 posizioni, ogni k posizioni cominciando dal p.to 0,0; quando si chiede di eliminare una k-cella in teoria le coordinate passate alla funzione dovrebbero corrispondere ad una posizione predefinita:esempio se ci sono k-celle di lato 3, le coordinate passate alla funzione elimina dovrebbero essere 0,0 oppure 3,0 oppure 3,3 .....3,6 che dite stò impazzendo????? |
| torak |
Quello che avevo proposto io è l'uso di una tabella hash con concatenazione(la normale tabella di hash) non una tabella ad indirizzamento aperto. Sul libro di algoritmi è al capitolo 12.2.
Chiaramente dovete usare una prefunzione, che si trova negli appunti di torelli, che trasforma (x,y) in k.
Questo k lo date in pasto ad una funzione di hash ben fatta(sempre sul libro spiega dei metodi molto buoni per costruirla) in modo da minimizzare le collisioni che bisogna prevedere di gestire con liste.
A questo punto, una volta costruita l'algoritmo per la tabella di hash, bisogna andare a vedere il capitolo 18.4 del libro, che parla di come gestire dinamicamente la dimensione delle strutture dati in modo da adattare le dimensioni all'effettivo utilizzo. E' una parte che viene spiegata poco, ma è il modo migliore per gestire la cosa. Alternativamente si può sempre decidere di fare una dimensione molto grande della tabella di hash, così da permettere di inserire molti elementi, però questo è un errore, perchè benchè funzioni per gli esempi di prova fa delle assunzioni sulle dimensioni dell'input. In più avere 10 mega di memoria occupata quando in realtà memorizzate 3 cagate non mi sembra il massimo, quindi se riuscite a realizzare una tabella di hash e avete tempo, guardatevi pure quella cosa... secondo me lo ammazzate fiorentini. |
| maynard80 |
| 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. |
| Tosh |
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. |
| Skilotto83 |
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?
Infatti metti solo le celle okkupate.....
Teoikmente il piano è visto kome la memoria del calcolatore....nn è infinita in pratika...ma lo è potenzialmente....poi quelle okkupate le puoi mettere dove vuoi...anke in un albero binario di ricerka... |
| VdM |
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" |
| Tosh |
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. |
| 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… |
| Skilotto83 |
| Per definizione....una K-cella esiste solo se è okkupata..giusto?? |
| mitnik |
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 |
| torak |
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…
Il 18.4 specifica che le tabelle dinamiche si possono usare con qualsiasi struttura, semplicemente per dire che il concetto è separato dal tipo di struttura dati che use. Liste e vettori non sono vietati, semplicemente hanno tempi di inserimento, ricerca e cancellazioni peggiori, quindi visto che è un esame di algoritmi si suppone utilizzi buone strutture dati.
Una tabella di hash è una buona struttura dati per rappresentare un piano, e con l'allargamento dinamico è ottima, non capisco le tue perplessità...
In più risolvere le collisioni con liste concatenate prevede la possibilità intrinseca delle tabelle di hash di fare collisioni(anche se con bassa probabilità) ma il numero di collisioni rimane basso perchè tieni sotto controllo il fattore di carico. ATTENZIONE: quella che propongo io NON è un hash a indirizzamento aperto. L'indirizzamento aperto è complesso nel caso della cancellazione, e non mi sembra il caso di complicarmi la vita così.
Considerando la bassa probabilità di collisione la tabella di hash con risoluzione delle collisioni con liste semplici è QUASI una struttura statica, quindi il tempo di ricerca inserimento e cancellazione è sempre buono. C'è una probabilità in realtà che tutti gli elementi facciano collisione, ma con una buona funzione di hash questa probabilità e talmente piccola che tutto il dsy potrebbe vincere il superenalotto più facilmente probabilmente. |
| eskimo |
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...
:) |
| Tosh |
| per favore, alcune persone cerchino di scrivere più chiaro altrimenti non si capisce un c..zo e perdiamo tutti un casino di tempo. |
| Tosh |
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?
non vedo una strategia radicalmente diversa.
cmq per ogni k-cella potresti esplorare meno di 8 "vicini", perchè alcuni li hai già verificati in quanto "vicini" di una k-cella già verificata precedentemente. |
| mitnik |
| cavolo è un casino verificare se una 1-cella è contenuta in una k-cella. Avete idee a proposito? |
| pincopallino |
Originally posted by mitnik
cavolo è un casino verificare se una 1-cella è contenuta in una k-cella. Avete idee a proposito?
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?
:D |
| Skilotto83 |
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?
:D
Infatti...nulla di pu' semplice...anke io ho implementato il tutto kosi'...
:D |
| marchinkus |
Scusate, quale sarebbe la k-cella "in considerazione"?
Il problema, secondo me è che le k-celle non SONO CREATE in riferimento alle coordinate delle 1_cella presenti nel piano: le k-celle già ESISTONO ed hanno delle precise coordinate: le inizializziamo noi quandro creiamo il piano con risoluzione k.
Potremo avere un piano suddiviso in k-celle quadrate di lunghezza 2, oppure di 3, di 4 di ........n
cOSA DITE? |
| mitnik |
Appunto. Se le k-celle non le hai memorizzate in nessuna struttura (perchè sono infinite) allora appena hai una 1-cella devi verificare se è contenuta nella k-cella appropriata. Il mio problema è trovare la k-cella appropriata.
Es. Supponi di avere risoluzione 3.
Nel piano hai la 1-cella (3,3)
A questo punto devi valutare in quale k-cella è contenuta.
Come fai a capire che deve essere la (3,3),(6,6)? |
| ghily |
realizzare invece le k-celle come stack di 1-celle?? non potrebbe essere una idea?? Quando si occupa una 1-cella viene creato lo stack per k-cella e viene inserita la 1-cella occupata.Resta sempre il problema di come scopire se una cella che non è occupata appartiene ad una certa k-cella. :?
Chao Roby |
| pincopallino |
Originally posted by marchinkus
Scusate, quale sarebbe la k-cella "in considerazione"?
Il problema, secondo me è che le k-celle non SONO CREATE in riferimento alle coordinate delle 1_cella presenti nel piano: le k-celle già ESISTONO ed hanno delle precise coordinate: le inizializziamo noi quandro creiamo il piano con risoluzione k.
Potremo avere un piano suddiviso in k-celle quadrate di lunghezza 2, oppure di 3, di 4 di ........n
cOSA DITE?
partendo dal presupposto che tu voglia sapere se una 1-cella è contenuta in una k-cella nel momento in cui ti viene richiesta l'area od il peso, per sapere qual'è la cella presa in considerazione ti bastano i numeri x,y che vengono passati alla funzione area(x,y) o peso(x,y). Infatti, partendo per esempio dalla funzione area(x,y), la k-cella che per prima viene presa in considerazione è k-Cella(kx,ky).........di qui poi dovrai calcolare l'area dell'intero blocco cui appartiene quella k-cella
secondo me =D |
| mitnik |
Avete qualche idea per implementare la funzione blocchi?
Io pensavo di richiamare la funzione area finchè non ho più elementi nella lista delle k-celle incrementando un contatore ogni volta che una cella non è connessa ad un'altra. Mi sembra un po complicato, voi che fate? |
| Skilotto83 |
Si'...anke sekondo me è kosi'...in effetti è la parte piu' inkasinata...
Kmq l'idea è quella...una volta ke sai quali sono tutte le k-celle sul piano calcoli tutti i blokki...continuano fino a quando nn ci sono piu' k-celle...
Oppure anke prendendo la coordinata x,y di valore maggiore...ke quindi risulterà la piu' esterna..
:D |
| contezer0 |
Salve a tutti!
scusate se torno ancora sul discorso della struttura dati ottimale per memorizzare le 1-celle...
nel caso di tabella hash, in base a cosa la si dovrebbe dimensionare?
mi spiego...se non ricordo male l'uso di una tabella hash e' comodo e veloce nel caso in cui si conosca a priori il numero massimo degli elementi da inserire.
in questo caso, non conoscendolo, si puo' ovviare con una tabella dinamica, ma in questo caso non va usata una nuova funzione hash, e quindi non bisogna anche ricalcolare il codice hash di tutti gli elementi inseriti prima del ridimensionamento? |
| Paolo74G |
Ciao a Tutti..
Sentite un po' questa: le K-celle vanno memorizzate comunque, siano esse libere oppure occupate (decisione presa tramite il calcolo del fattore di riempimento) perche' se una sola 1-cella è presente, asiste anche la sua K. Infatti se alla medesima risoluzione K vengono fatti dei nuovi (I)nsert potrebbe essere che alcune K-celle diventino da libere.. oKKupate...
Non è così secondo voi?
Adesso porgo una domanda...
Nel caso K=1 come ci si puo' comportare? |
| mitnik |
| Certo che vanno memorizzate, ma solo quelle dipendenti dalle 1-celle presenti sul piano. E' inutile (anche impossibile perchè sono infinite) memorizzare in una struttura un k-cella che al suo interno non ha nemmeno una 1-cella. |
| Skilotto83 |
Originally posted by mitnik
Certo che vanno memorizzate, ma solo quelle dipendenti dalle 1-celle presenti sul piano. E' inutile (anche impossibile perchè sono infinite) memorizzare in una struttura un k-cella che al suo interno non ha nemmeno una 1-cella.
E' vero..ma il suo ragionamento è ke dopo aver calcolato per dire l'area di un blocco...potrei voler inserire una cella e quindi devo per foza ripetere tutta la scansione del piano se voglio riavere l'area dello tesso blocco..perkè kn l'aggiunta di una 1-cella potrebbe essere diventato un blokko piu' grande......kapito? |
| mitnik |
ok.
Come calcolate l'area di una k-cella? come fate a trovare tutte le k-celle che hanno un punto in comune e che sono connesse alla cella data alla funzione?
Sto diventando matto su quella funzione e magari la soluzione è semplice |
| joe.satriani |
| qualcuno saprebbe dirmi come implementare la funzione hash che parte da una lista di 1-celle e le divide in base al blocco di appartenenza? |
| sirio |
Originally posted by contezer0
Salve a tutti!
scusate se torno ancora sul discorso della struttura dati ottimale per memorizzare le 1-celle...
nel caso di tabella hash, in base a cosa la si dovrebbe dimensionare?
mi spiego...se non ricordo male l'uso di una tabella hash e' comodo e veloce nel caso in cui si conosca a priori il numero massimo degli elementi da inserire.
in questo caso, non conoscendolo, si puo' ovviare con una tabella dinamica, ma in questo caso non va usata una nuova funzione hash, e quindi non bisogna anche ricalcolare il codice hash di tutti gli elementi inseriti prima del ridimensionamento?
In effetti hai ragione se usi una tab. hash a indirizzamento aperto, ciò non vale se usi la tab. con liste concatenate. |
| Paolo74GRS |
Ciao a tutti, ho un dubbio/domanda da sottoporVi.
Premetto che ho scelto di implementare la struttura 1-celle tramite un albero; il mio dubbio riguarda la creazione dell'albero binario di ricerca contenente le 1-celle!
Magari sto facendomi venire il mal di testa per nulla..
Comunque, il mio problema e': quale criterio devo utilizzare per l'ordine dei nodi dell'albero??
Ordino per X, ordino per Y.. oppure per XY (..anche se non saprei come )???
Qualcuno può darmi una dritta?
ciao |
| Paolo74GRS |
Ciao a tutti, ho un dubbio/domanda da sottoporVi.
Premetto che ho scelto di implementare la struttura 1-celle tramite un albero; il mio dubbio riguarda la creazione dell'albero binario di ricerca contenente le 1-celle!
Magari sto facendomi venire il mal di testa per nulla..
Comunque, il mio problema e': quale criterio devo utilizzare per l'ordine dei nodi dell'albero??
Ordino per X, ordino per Y.. oppure per XY (..anche se non saprei come )???
Qualcuno può darmi una dritta?
ciao |
| Paolo74GRS |
Ciao a tutti, ho un dubbio/domanda da sottoporVi.
Premetto che ho scelto di implementare la struttura 1-celle tramite un albero; il mio dubbio riguarda la creazione dell'albero binario di ricerca contenente le 1-celle!
Magari sto facendomi venire il mal di testa per nulla..
Comunque, il mio problema e': quale criterio devo utilizzare per l'ordine dei nodi dell'albero??
Ordino per X, ordino per Y.. oppure per XY (..anche se non saprei come )???
Qualcuno può darmi una dritta?
ciao |
| Paolo74GRS |
Ciao a tutti, ho un dubbio/domanda da sottoporVi.
Premetto che ho scelto di implementare la struttura 1-celle tramite un albero; il mio dubbio riguarda la creazione dell'albero binario di ricerca contenente le 1-celle!
Magari sto facendomi venire il mal di testa per nulla..
Comunque, il mio problema e': quale criterio devo utilizzare per l'ordine dei nodi dell'albero??
Ordino per X, ordino per Y.. oppure per XY (..anche se non saprei come )???
Qualcuno può darmi una dritta?
ciao |
| Paolo74GRS |
Ciao a tutti, ho un dubbio/domanda da sottoporVi.
Premetto che ho utilizzato una struttura ad albero per le 1- celle;
il mio dubbio riguarda la creazione dell'albero binario di ricerca
contenente le 1-celle!
Magari sto facendomi venire il mal di testa per nulla..
Comunque, il mio problema e': quale criterio devo utilizzare per l'ordine dei nodi dell'albero??
Ordino per X, ordino per Y.. oppure per XY (..anche se non saprei come )???
Potete darmi qualche dritta?
Ciao |
| Paolo74GRS |
Ciao a tutti, ho un dubbio/domanda da sottoporVi.
Premetto che ho utilizzato una struttura ad albero per le 1- celle;
il mio dubbio riguarda la creazione dell'albero binario di ricerca
contenente le 1-celle!
Magari sto facendomi venire il mal di testa per nulla..
Comunque, il mio problema e': quale criterio devo utilizzare per l'ordine dei nodi dell'albero??
Ordino per X, ordino per Y.. oppure per XY (..anche se non saprei come )???
Potete darmi qualche dritta?
Ciao |
| Paolo74GRS |
Ciao a tutti, ho un dubbio/domanda da sottoporVi.
Premetto che ho utilizzato una struttura ad albero per le 1- celle;
il mio dubbio riguarda la creazione dell'albero binario di ricerca
contenente le 1-celle!
Magari sto facendomi venire il mal di testa per nulla..
Comunque, il mio problema e': quale criterio devo utilizzare per l'ordine dei nodi dell'albero??
Ordino per X, ordino per Y.. oppure per XY (..anche se non saprei come )???
Potete darmi qualche dritta?
Ciao |
| eskimo |
Ciao, io uso una struttura per mantenere la 1-celle, poi per calcolare le k-celle mi baso su di essa e mantengo una struttura con le info sulle kcelle. Il dubbio è sulla struttura che mantiene le k-celle.
Secondo voi è meglio farla come albero binario, quindi cercare le varie 1-celle componenti la kcella con una ricerca binaria su un albero (per ogni 1-cella che devo cercare per verificare se c'è ed appartiene una determinata kcella spendo log N) 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!!!! :) :) |
| Dante |
Io ho pensato così:
1) le 1celle inserite sono memorizz. in una lista in ordine di inserimento.
2) Ad ogni inserimento di 1cella verifico a quale kcella appartiene, e aggiungo ad un'altra lista di kcelle.
3) Ad ogni inserimento di kcella verifico aggiungo ad una'altra lista di kcelle-blocchi se appartiene a quel blocco, se no aggiungo ad un'altra lista di kcelle-blocco
in totale ho almeno 3 liste: 1 che memorizza semplicemente le 1celle inserite, 1 che memorizza le kcelle risultanti e almeno 1 che memorizza le kcelle di un kblocco...
area(x y): verifico che la kcella(kx ky) ci sia nella lista delle kcelle, se sì vado a cercarla nella\e lista\e dei kblocchi e faccio i conti...
secondo voi è fattibile sta cosa? la sto pensando ora... |
| Skilotto83 |
Originally posted by Dante
Io ho pensato così:
1) le 1celle inserite sono memorizz. in una lista in ordine di inserimento.
2) Ad ogni inserimento di 1cella verifico a quale kcella appartiene, e aggiungo ad un'altra lista di kcelle.
3) Ad ogni inserimento di kcella verifico aggiungo ad una'altra lista di kcelle-blocchi se appartiene a quel blocco, se no aggiungo ad un'altra lista di kcelle-blocco
in totale ho almeno 3 liste: 1 che memorizza semplicemente le 1celle inserite, 1 che memorizza le kcelle risultanti e almeno 1 che memorizza le kcelle di un kblocco...
area(x y): verifico che la kcella(kx ky) ci sia nella lista delle kcelle, se sì vado a cercarla nella\e lista\e dei kblocchi e faccio i conti...
secondo voi è fattibile sta cosa? la sto pensando ora...
Ma skusa ma nn è sufficente inserire prima tutte le 1-celle e poi calcolare le varie K celle??
Perkè una 1-cella nn per forza appartiene ad una k-cella....visto ke la K-cella esiste se è superiore il livello di riempimento....
No?
Poi ogni volta ke inserisci una 1-cella rifai la ricerka e kontrolli se è gia' in una K-cella esistente....se si' amen...altrimenti potrebbe doventare k-cella proprio kn la 1-cella inserita...e quindi prosegui...
no? |
| contezer0 |
Originally posted by sirio
In effetti hai ragione se usi una tab. hash a indirizzamento aperto, ciò non vale se usi la tab. con liste concatenate.
perche', se uso le liste concatenate, al momento di incrementare la dimensione della tabella, non devo usare comunque una funzione hash diversa da quella di prima?
o forse vuoi dire che non c'e' bisogno di aumentare la dimensione?
comunque...facendo due conti, e considerando che l'unica limitazione sul piano e' data dal tipo di dato intero, se ci capita un piano interamente ricoperto di celle, abbiamo un fattore di carico (2^32)/numero di posizioni nella tabella.
quindi sara' si un O(1) ma la costante nascosta da questo O mi pare abbastanza gigantesca!
oltretutto solo se la funzione hash e' molto buona. |
| Dante |
Originally posted by Skilotto83
Ma skusa ma nn è sufficente inserire prima tutte le 1-celle e poi calcolare le varie K celle??
Forse sì, quando chiede per la prima volta area, peso o blocchi, è allora che creo la lista di kcelle e kblocchi...
[i]Perkè una 1-cella nn per forza appartiene ad una k-cella....visto ke la K-cella esiste se è superiore il livello di riempimento....
No? [/B]
Sì, ma c'è da tenere conto che cmq il livello di riempimento può cambiare in qualsiasi momento... dentro ogni nodo della lista delle kcelle io terrei anche l'infomazione di quante 1celle ha la kcella... così la lista è riutilizzabile sempre, anche se cambi il livello di riempimento... forse l'unica che devi cambiare è la lista delle kcelle-blocchi...
[i]Poi ogni volta ke inserisci una 1-cella rifai la ricerka e kontrolli se è gia' in una K-cella esistente....se si' amen...altrimenti potrebbe doventare k-cella proprio kn la 1-cella inserita...e quindi prosegui...
no? [/B]
boh... |
|
|
|
|
