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

[ALGORITMI]Progetto Zoom

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

__________________
"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

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

Help Zoom

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!

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

__________________
alessandro colombini

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?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

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

__________________
"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

beh probabilmete scorrere un array bidimensionale NxN sarebbe "costoso" in termini di efficenza

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

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?

__________________
alessandro colombini

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.

quindi una cella è occupata se ha almeno (3/25)*5*5=3 1-celle occupate ,giusto?

__________________
"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 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?

Diciamo ke il progetto l'ho kapito..mi manka di kapire da dove iniziare...

__________________
"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

allora siamo in 2!

__________________
alessandro colombini

La matrice di adiacenza la usereste per vedere quali blocchi sono connessi fra loro??
Perchè io implementerei tutto con un albero di ricerca.

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!

__________________
alessandro colombini

Ke ne dite di una tabella hash!!??

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?

__________________
alessandro colombini

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

si era questo.
ma per riconoscere \n come si fa?
se uso isspace non fa distinzioni tra spazio o a capo.

__________________
alessandro colombini

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.

\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

__________________
alessandro colombini

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

__________________
"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

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?

__________________
alessandro colombini

si, dovrebbe funzionare.

allora abbiamo capito come implementare il piano? amici continuano a dirmi "lista di adiacenze"..... ma non so da dove partire!

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

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

__________________
alessandro colombini

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?

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?

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

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?

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?

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

bravo pincopallino, anch'io concordo con te

__________________
" Non ti vantare del domani, perchè non sai neppure che cosa genera l'oggi. "
PROVERBI 28,1

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

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

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.

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

__________________
alessandro colombini

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?

__________________
alessandro colombini

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.

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?

ma per lista di adiacenza intendete una lista di liste? Cioé, una lista per le ascisse che contiene liste con le ordinate?

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

Chi ha proposto la tabella di hash potrebbe illustrare un po' come applicherebbe la soluzione al problema?

Originally posted by Tosh
Chi ha proposto la tabella di hash potrebbe illustrare un po' come applicherebbe la soluzione al problema?

__________________
Questo è il giardino
Dove il principe muore
Nessun sentiero
Nessun destriero
Soltanto un nome... Eterno...

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

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

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

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

__________________
"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

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?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

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

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.

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

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?

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

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

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?

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

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?

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

__________________
"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

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?

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?

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.

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.

__________________
"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

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

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?

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?

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

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

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

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

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

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

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

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

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

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

__________________
"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

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.

Originally posted by Skilotto83
Ma skusa ma nn è sufficente inserire prima tutte le 1-celle e poi calcolare le varie K celle??

[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]

[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]

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?

__________________
alessandro colombini

Come faccio UNA LISTA CON

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?

bravo! sto scrivendo questa parte di codice.... una volta funzionante aggiungo le funzioni area, peso e blocchi... sperem....
tu sei già lì?

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.

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!

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

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

__________________
"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

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

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

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"?

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

__________________
"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

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

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.

__________________
o sei parte della soluzione o sei parte del problema.

recensioni libri informatica

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?

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

Occhei, come non detto! Ho risolto manipolando manualmente la parte dopo la virgola del double (un lavoraccio)...

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

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?

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?

__________________
"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

Originally posted by Eruyomë
Occhei, come non detto! Ho risolto manipolando manualmente la parte dopo la virgola del double (un lavoraccio)...

Originally posted by Eruyomë
Occhei, come non detto! Ho risolto manipolando manualmente la parte dopo la virgola del double (un lavoraccio)...

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?

Originally posted by Eruyomë
Occhei, come non detto! Ho risolto manipolando manualmente la parte dopo la virgola del double (un lavoraccio)...

chi ha usato le liste mi darebbe una mano sulla funzione blocchi? come ha ragionato?

Grazie

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

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

consegna

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

perchè la carta può anche non essere cartacea?
cmq è il 3 ottobre e le modalità sono ben spiegate nel pdf..

__________________
alessandro colombini

Originally posted by aghito
perchè la carta può anche non essere cartacea?

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

__________________
"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

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

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

complimenti!
ci fai un riassunto delle strutture dati utilizzate e come hai fatto la funzione blocchi...ci searesti molto d'aiuto..grazie

__________________
alessandro colombini

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!

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

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

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