Newsgroup: it.comp.lang.c
Titolo: Qualche consiglio!!!

Salve a tutti dovrei fare questo progetto per motivi di studio!! Qualcuno di
voi che conosce bene le strutture dati mi potrebbe dare un consiglio!!!!!
Laboratorio di Algoritmi e Strutture Dati
Progetto "MiniLife"
Il problema
Obiettivo del progetto `e studiare l'evoluzione di un semplice automa
cellulare bidimensionale.
L'universo `e rappresentato da un piano di dimensione fissata n £ n (n > 0
intero) suddiviso in quadrati
di lato unitario che chiamiamo celle. L'intorno di una cella s del piano `e
l'insieme delle 8 celle che la
circondano (con le ovvie limitazioni quando la cella in questione tocca
qualche lato del piano). In un dato
istante t, ogni cella pu`o essere viva o morta.
Partendo da una situazione iniziale (al tempo t = 0), in cui viene dato un
insieme V0 di celle vive nel piano,
a ogni istante successivo t = 1; 2; :::, l'insieme Vt delle celle vive al
tempo t `e determinato applicando
all'insieme Vt¡1 la regola di evoluzione specificata nel seguito.
La regola di evoluzione di ogni cella s `e la seguente:
² se s `e viva al tempo t ¡ 1 rimane viva al tempo t;
² se al tempo t ¡ 1 s `e morta e il suo intorno conta esattamente 3 celle
vive, allora s diventa viva al
tempo t (diciamo anche che s nasce);
² in nessun altro caso s pu`o nascere (tranne che per inserzione manuale,
vedi sotto).
Oltre alla regola di evoluzione si prevede di poter modificare lo stato
delle celle mediante inserzione ed
eliminazione manuale di celle vive.
Formalmente, fissato un intero n, chiamiamo piano l'insieme dei punti
Piano(n) = f (x; y) 2 N£N j 0 · x · n; 0 · y · ng:
Una cella `e un quadrato il cui lato ha dimensione unitaria; pi`u
precisamente, data una coppia di naturali
(a; b), una cella in posizione (a; b) `e data dall'insieme dei punti
(vertici del quadrato):
Cella(a; b) = f (x; y) j a · x · a + 1; b · y · b + 1g:
Ad esempio, Cella(3; 5) = f(3; 5); (3; 6); (4; 6); (4; 5)g
Analogamente, definiamo Rettangolo(a; b; c; d) come l'insieme dei punti del
piano individuati dai punti
(a; b) e (c; d) (coordinate dei vertici pi`u in basso a sinistra e pi`u in
alto a destra), ossia
Rettangolo(a; b; c; d) = f (x; y) j a · x · c; b · y · dg:
Chiamiamo (a; b; c; d) le coordinate di Rettangolo(a,b,c,d).
Ad esempio, Rettangolo(1; 3; 2; 5) `e il rettangolo formato dai punti f(1;
3); (2; 3); (1; 4); (2; 4); (1; 5); (2; 5)g.
Diciamo che due celle sono adiacenti se hanno in comune almeno un punto
(quindi, ogni cella `e adiacente
a se stessa); nella figura qui sotto le celle A e B sono adiacenti, B e C
sono adiacenti, e anche A e C sono
adiacenti. Al contrario D non `e adiacente ad alcuna delle altre tre celle.
1
A B
C
D
Un cammino da A1 a Ah `e una sequenza di celle A1; : : : ;Ah tali che Ai `e
adiacente a Ai+1 per 1 · i · h¡1.
Diciamo che un insieme P di celle vive `e connesso se, per ogni A;B 2 P,
esiste un cammino da A a B
contenuto in P. Un blocco `e un insieme di celle vive A tale che A `e
connesso e, per ogni cella viva P 62 A,
A[ fPg non `e connesso. La dimensione di un blocco `e data dal numero di
celle vive che lo compongono.
L'intorno della cella A (viva o morta) `e l'insieme delle celle adiacenti ad
A tranne A stessa.
Nell'esempio sopra fAg, fBg, fCg, fA;Bg, fB;Cg, fA;B;Cg, fA;Cg sono
connessi, mentre fA;Dg,
fB;Dg, fA;B;C;Dg, fB;C;Dg, etc., non sono connessi. I blocchi sono fA;B;Cg e
fDg.
Si consideri l'esempio seguente:
A1
A2
A3 A4
A6
A7 A8 A9
A10
A5
A1
A2
A3 A4
A6
A7 A8 A9
A10
A5
B1
B2 B3
B4
Nella figura a sinistra `e riportata la situazione al tempo t. Le celle
etichettate con la lettera A sono tutte
e sole le celle vive al tempo t. Nella figura a destra la situazione al
tempo t + 1 ottenuta dopo un passo
di evoluzione. Le celle etichettate con la lettera B sono tutte e sole
quelle nate al tempo t + 1. Le celle
vive al tempo t + 1 sono tutte e sole le celle etichettate con la lettera A
o con la lettera B.
Si richiede di implementare una struttura dati e±ciente che permette di
eseguire le operazioni seguenti
(si tenga presente che la dimensione del piano n pu`o essere grande rispetto
al numero di celle vive, quindi
non `e sicuramente e±ciente rappresentare il piano mediante una bit-map di
tipo n £ n).
Nel seguito parleremo di inserimento di Cella(x,y) per riferirci all'
operazione che pone Cella(x,y) nello
stato viva.
Analogamente chiameremo eliminazione di Cella(x,y) l'operazione che pone
Cella(x,y) nello stato morta.
- crea (n)
Crea un piano vuoto di dimensione n (se un piano `e gi`a definito viene
eliminato).
- inserisci (x, y)
Inserisce nel piano la Cella(x, y).
- inserisci-rand (k)
Inserisce casualmente k nuove celle vive nel piano.
- genera ()
Assumendo di essere al tempo t, genera le celle che devono nascere al tempo
t+1. Questo determina
un passo (da t a t + 1) nell'evoluzione dell'intero sistema.
2
- elimina (x, y)
Elimina dal piano la Cella(x, y).
- listacelle ()
Fornisce la lista di tutte le celle vive al tempo corrente, secondo le
specifiche sotto riportate.
- min-rett (x, y)
Calcola le coordinate del pi`u piccolo rettangolo contenente il blocco cui
appartiene Cella(x,y). se
Cella(x,y) non `e viva restituisce il rettangolo degenere
Rettangolo(x,y,x,y).
- num-blocchi ()
Calcola il numero di blocchi presenti nel piano.
- max-dim-blocco ()
Calcola la dimensione del pi`u grande blocco presente nel piano.
Specifiche di implementazione
Il programma deve leggere dallo standard input (stdin) una sequenza di linee
(separate da \n), ciascuna
delle quali corrisponde a una linea della prima colonna della Tabella 1,
dove x; y; z;w sono numeri naturali
e i vari elementi sulla linea sono separati da uno o pi`u spazi. Quando una
linea `e letta, viene eseguita
l'operazione associata; le operazioni di stampa sono e®ettuate sullo
standard output (stdout), e ogni
operazione deve iniziare su una nuova linea.
Linea di input Operazione
c x crea (x)
i x y inserisci (x, y)
d x inserisci-rand (x)
g Calcola la funzione genera()
e x y elimina (x, y)
l Stampa la lista delle celle vive secondo il formato sotto specificato
r x y Stampa le coordinate del minimo rettangolo
calcolato da min-rett(x, y) secondo il formato sotto specificato
b Stampa il valore di num-blocchi ()
m Stampa il valore di max-dim-blocco ()
f Termina l'esecuzione del programma
Tabella 1: Specifiche del programma
Si noti che non devono essere presenti vincoli sulla dimensione del piano e
sul numero di celle (se non
quelli determinati dal tipo di dato intero). Non si richiede - anzi si
sconsiglia - l'uso di grafica, se non
per test personali: in modo particolare, non si usi conio.h e neppure
clrscr().
3
Formato per la visualizzazione della lista delle celle vive
Il formato a cui attenersi `e il seguente: Assumiamo che l'insieme delle
celle vive sia
f(x1; y1); (x2; y2); : : : ; (xn; yn)g
dove, per ogni i 2 f1; : : : ; n ¡ 1g, valga (xi; yi) < (xi+1; yi+1)
rispetto all' ordine stretto < definito da:
(xi; yi) < (xi+1; yi+1) se e solo se xi < xi+1 oppure xi = xi+1 e yi < yi+1:
L'output della funzione listacelle() , innescata dal comando l, deve essere:
x1 y1
x2 y2
..
xn yn
Formato per la visualizzazione delle coordinate del minimo rettangolo
Sia Rettangolo(a,b,c,d) il minimo rettangolo che contiene il blocco a cui
appartiene Cella(x,y).
L'output di min-rett(x,y) deve essere:
a b c d
Esempio. Si supponga che le linee di input siano:
c 100
i 3 2
i 4 2
i 5 2
i 2 5
i 3 5
i 4 5
b
g
l
b
r 4 2
e 5 2
e 3 4
e 4 3
e 3 5
g
l
b
m
f
4
L'output prodotto dal programma deve essere:
2
2 5
3 2
3 4
3 5
3 6
4 1
4 2
4 3
4 5
5 2
1
2 1 6 7
2 5
3 1
3 2
3 5
3 6
4 1
4 2
4 5
2
4

qualche lato del piano). 
Una matrice di adiacenza di NxN? 
[MEGASNIP]
Potevi pure farci un riassunto :P
Da quanto ho capito una matrice si adatta bene al problema, meglio di
altre soluzioni. Se invece sei sicuro di lasciare sempre molto spazio
inutilizzato nella tua matrice ti suggerisco un altro medoto.
Visto che e' un lab di ASD dovrai implementarti tutte le primitive di
gestione della matrice (create, destroy, traverse, etc.).
Intuitivamente ti servira un metodo per accedere alle celle adiacenti
e un medoto per leggere i dati di una data cella (non che' inserire e
cancellare una data posizione).
Per il resto non ci devo grandi complicazioni (nell'ADT matrice).
Mox :)

io faccio il tuo stesso corso e ho il progetto. ovviamente non uso una
matrice, sto usando un grafo con liste di adiacenza.
ho fatto circa metà progetto, oggi vado avanti. 
la cosa più difficile a mio modo di vedere è generare le cellule vive
(è l'ultima cosa che farò), per il resto in tempo lineare si fa tutto,
si tratta di manipolare liste e niente di più. i blocchi li fai con
UNION e FIND che ha spiegato a lezione (io vado al pomeriggio anche se
ho frequentato 2 lezioni in tutto ^_^).
se qualche espertone salta fuori con altre idee ben venga cmq :-)
ciao

 di altre soluzioni.
ti darei ragione ma a detta del docente per cose simili le matrici le
usa un bambino dell'asilo e non ha tutti i torti. con l'uso di matrici
questo progetto (senza immodestia) si fa in un attimo...
insomma che una matrice sia come ordine di grandezza N^2 non è da
trascurare, anzi!!
io userò un grafo con liste di adiacenza, inserimento e cancellazione
avvengono in tempo lineare (almeno spero, non ho ancora fatto i conti
ma di sicuro non sono N^2), per i calcolare blocchi visito il grafo in
ampiezza, per il resto deciderò oggi :-)
ciao

On Sun, 13 Jan 2002 13:25:09 GMT, 
alanw...@freemail.it
 (alan) wrote:
[...]
ripensandoci meglio forse sono stato offensivo. ho riletto il tuo post
e inizialmente avevo capito che tu suggerissi di rappresentare il
piano con una matrice NxN (questa si che sarebbe una cagata) mentre
intendevi la matrice di adiacenza che sarebbe di soli 8 elementi
quindi non č un'idea sbagliata ( anche se mi sembra di ricordare che
la matrice di adiacenza non č tanto gradita al docente).
la matrice di adiacenza renderebbe piů veloci certe operazioni ma
quello che interessa a noi sono i costi asintotici e credo che pescare
un elemento nella matrice con una sola operazione o impiegarne al
massimo 7 nel caso della lista siano la stessa cosa ai fini del costo.
ora me ne torno al mio progetto, speriamo di non essere OT con questa
storia ma del resto un newsgroup di strutture dati non mi risulta
esista :-) (e il progetto si fa in c)
ciao

la matrice di adiacenza non č tanto gradita al docente).
Nel caso di un grafo scarsamente connesso puo' andare e viene usata;
se il grafo inizia a farsi denso hai piu' spreco di spazio che non con
le liste di adiacenza.
La soluzione da adottare dipende solo dal docente, pero' io non
escluderei la matrice solo perche' e' banale (ovviamente se il prof
vuole soluzioni articolate e lente fategliele articolate e lente).
Mox.

 wrote in message
3c418718...@powernews.libero.it...


ci vediamo in uni!
ciao

 alberello ^_^
complimenti! e così l'hai già finito! bravo!
io ho ancora troppe difficolta a risolverlo su carta! e quindi nn ci provo
neanche ad implementarlo in C!
potresti darmi qualche suggerimento?
anche in privato 
rgt...@iol.it
grazie ancora!
Luca
Ps ho sentito che altri stanno provando ad usare le tabelle hash! potrebbe
essere una buona idea!