Yoruno: Riportata alla revisione precedente da Yoruno

2006-03-08T13:03:40Z

Riportata alla revisione precedente da Yoruno

Mostra modifiche

219.117.58.251: test

2006-03-08T12:31:01Z

test

Mostra modifiche

Yoruno il 08:52, 3 feb 2006

2006-02-03T08:52:32Z

Yoruno il 08:48, 3 feb 2006

2006-02-03T08:48:16Z

Yoruno il 08:47, 3 feb 2006

2006-02-03T08:47:47Z

Nuova pagina

/* Attention please! ;)
* Questo software e l'annessa documentazione
* sono distribuiti sotto la GNU policy.
* [se non sai cos'è, vergognati, e poi acculturati un po':
* [http://www.gnu.org/philosophy/free-sw.it.html]
*
* Il fine della distribuzione gratuita è per combattere il
* fiorente "mercato" dei progettini. Sei libero di prenderne
* spunto, se hai dubbi o non capisci qualcosa, let me know!
* bye! min:o)
* mail: mino@ngi.it
* ICQ: 57553717
*
* Il progetto è stato valutato 4 (cioè il massimo)
* durante l'appello di Febbraio-Aprile 2002.
*/

#include <stdlib.h>
#include <stdio.h>
#define HASHTABLE_SIZE 11 // Grandezza del lato della tabella hash"

struct cella {
int x, y; // Coordinate della cella"
int tempo; // Tempo in cui e' nata la cella"
struct cella *next; // Prossimo elem. nella hash"
struct cella *prossimo_sul_piano; // Per la lista ordinata"
struct cella *prossimo_nel_blocco; // Per i gruppi di blocchi"
struct blocco *padre; // Blocco rappresentativo"
};

struct blocco {
int num; // Numero di celle nel blocco"
struct cella *prima_cella; // Prima cella del blocco"
struct blocco *prossimo_blocco; // Puntatore al prossimo blocco"
};

typedef struct cella cella;
typedef struct blocco blocco;

int tempo = 2; // Tempo iniziale. Lo poniamo uguale"
// a due per una piccola ottimizzazione"
// (vedere relazione)."
int dimensione_piano = 0; // Dimensione del piano"

cella *primo_sul_piano = NULL; // Primo elemento sul piano"
blocco *primo_blocco = NULL; // Primo blocco"
int n_blocchi = 0; // Numero di blocchi sul piano"
cella *hashtable[HASHTABLE_SIZE][HASHTABLE_SIZE]; // Tabella Hash

void crea(int n) {
/* Crea un piano di dimensioni n * n."
Dobbiamo solo verificare se un piano esiste gia', e se si', eliminarlo. */"
if (primo_sul_piano != NULL) {"
int i,j;"
cella *q, *p;"
blocco *r, *s;"

/* Passo 1) Svuota le liste della hashtable. */"
for (i = 0; i < HASHTABLE_SIZE; i++) {"
for (j = 0; j < HASHTABLE_SIZE; j++) {"
hashtable[i][j] = NULL;"
}"
}"

/* Passo 2) Svuota la lista prossimo_sul_piano. */"
q = primo_sul_piano;"
while(q) {"
p = q;"
q = q->prossimo_sul_piano;"
free(p);"
} "
primo_sul_piano=NULL;"

/* Passo 3) Svuota la lista dei blocchi. */"
r = primo_blocco;"
while(r) {"
s = r;"
r = r->prossimo_blocco;"
free(s);"
} "
primo_blocco=NULL;"

} "
/* Infine, inizializza (o resetta) dimensione_piano, tempo"
e numero di blocchi. */"
dimensione_piano = n;"
tempo = 2;"
n_blocchi = 0;"
}
int hash(int key) {
/* Calcola l'hash di x (usando il metodo del resto). */"
return (key % HASHTABLE_SIZE);"
}

cella *cerca(int x, int y, int t) {
/* Restituisce un puntatore alla cella di coordinate (x, y) viva al tempo t."
Se il parametro t e' -1, il tempo non viene considerato nella ricerca. */"
cella *p = hashtable[hash(x)][hash(y)], *q = NULL;"
while (p && (p->x < x || (p->x == x && p->y < y))) {"
q = p;"
p = p->next;"
} "
"
if (p && p->x==x && p->y == y && ((t!=-1 && p->tempo <= t) || t==-1))"
return p; // trovata!"
else"
return NULL; // non esiste!"
}

void crea_blocco(cella *origine) {
/* Crea un nuovo blocco con la cella puntata da origine. */"
blocco *r;"
/* Passo 1) Alloca la memoria. */"
r = calloc(1,sizeof(blocco));"
if(!r) {"
fprintf(stderr,""Errore nella creazione del blocco.\n"");"
exit(-1); "
}"
"
/* Passo 2) Inizializza le variabili. */"
origine->prossimo_nel_blocco=NULL;"
origine->padre = r;"
r->num = 1;"
r->prima_cella = origine;"
r->prossimo_blocco = NULL;"
"
/* Passo 3) Inserisce nella lista dei blocchi. */"
if (!primo_blocco)"
primo_blocco = r;"
else {"
r->prossimo_blocco = primo_blocco;"
primo_blocco = r;"
}"

/* Il tempo e' negativo se la cella era parte di un blocco"
cancellato in precedenza. In tal caso lo ""resettiamo"". */"
if (origine->tempo < 0)"
origine->tempo = origine->tempo * (-1);"

/* Passo 4) Aggiorniamo il numero di blocchi sul piano */"
n_blocchi++;"
}

void cancella_blocco(blocco *eliminare) {
/* Cancella il blocco specificato dalla lista dei blocchi. */"
blocco *t = primo_blocco;"
blocco *s = NULL;"
"
/* Passo 1) Cancella dalla lista dei blocchi. */"
if (t == eliminare) {"
primo_blocco = eliminare->prossimo_blocco;"
} else {"
while (t != eliminare) {"
s = t;"
t = t->prossimo_blocco;"
}"
s->prossimo_blocco = t->prossimo_blocco;"
}"
"
/* Passo 2) Liberiamo la memoria. */"
free(eliminare);"
"
/* Passo 3) Aggiorniamo il numero di blocchi sul piano. */"
n_blocchi--;"
}
void unisci_blocchi(cella *uno, cella *due) {
/* Unisce i blocchi a cui appartengono le celle uno e due."
Come ottimizzazione, uniamo sempre il blocco piu' piccolo a"
quello piu' grande. */"
cella *p;"
blocco *eliminare;"
if (uno->padre->num > due->padre->num) {"
/* Passo 1) Aggiorniamo il numero di celle nel blocco. */"
(uno->padre->num) += (due->padre->num);"
eliminare = due->padre; "
p = uno->padre->prima_cella;"
"
/* Passo 2) Aggiungiamo le nuove celle in coda. */"
while (p->prossimo_nel_blocco) {"
p=p->prossimo_nel_blocco;"
}"
p->prossimo_nel_blocco = due->padre->prima_cella;"
p = due->padre->prima_cella;"
"
/* Passo 3) Aggiorniamo il puntatore ""padre"". */"
while (p) {"
p->padre = uno->padre;"
p=p->prossimo_nel_blocco;"
}"

/* Passo 4) Eliminiamo il blocco. */"
cancella_blocco(eliminare);"
} else {"
/* Passo 1) Aggiorniamo il numero di celle nel blocco. */"
(due->padre->num) += (uno->padre->num);"
eliminare = uno->padre; "
p = due->padre->prima_cella;"
"
/* Passo 2) Aggiungiamo le nuove celle in coda. */"
while (p->prossimo_nel_blocco) {"
p=p->prossimo_nel_blocco;"
}"
p->prossimo_nel_blocco = uno->padre->prima_cella;"
p = uno->padre->prima_cella;"
"
/* Passo 3) Aggiorniamo il puntatore ""padre"". */"
while (p) {"
p->padre = due->padre;"
p=p->prossimo_nel_blocco;"
}"
"
/* Passo 4) Eliminiamo il blocco. */"
cancella_blocco(eliminare);"
}"
}

void rimuovi_cella_dal_blocco(cella *eliminare) {
/* Cancella la cella dal blocco. */"
cella *p, *q;"
blocco *b;"
int dx, dy;"
"
/* Caso 1) Se e' l'unica cella del blocco allora dobbiamo "
eliminare anche il blocco stesso. */"
if (eliminare->padre->num <= 1)"
cancella_blocco(eliminare->padre);"
"
/* Caso 2) Se nel blocco ci sono due celle (ovvero se la cella"
ha solo un vicino) possiamo semplicemente rimuoverla dal blocco. */"
if (eliminare->padre->num == 2) {"
if(eliminare->padre->prima_cella == eliminare) // e' la prima."
eliminare->padre->prima_cella = eliminare->prossimo_nel_blocco;"
else // e' la seconda."
eliminare->padre->prima_cella->prossimo_nel_blocco = NULL;"
eliminare->padre->num=1;"
}"

/* Caso 3) Altrimenti cancello il blocco e lo ricreo partendo da"
ogni vicino della cella da eliminare ed effettuando una visita "
in profondita' in cui unisco i blocchi adiacenti. */"
if (eliminare->padre->num > 2) {"
b = eliminare->padre;"
q = NULL;"

/* Passo 1) Per marcare le celle del blocco da ricalcolare, rendo"
// il tempo negativo e azzero il puntatore ""padre"". */"
for(p = b->prima_cella; p; p = p->prossimo_nel_blocco) {"
p->tempo = p->tempo * (-1);"
p->padre = NULL; "
}"
"
/* Passo 2) Cancello il blocco originale. */"
cancella_blocco(b);"

/* Passo 3) Per ogni p appartenente alla lista delle celle nel blocco... */"
for(p = primo_sul_piano; p; p = p->prossimo_sul_piano) {"
if(p->tempo > 0) continue;"
if(p->x==eliminare->x && p->y==eliminare->y) continue;"
crea_blocco(p);"

/* ...per ogni q vicino di p... */"
for (dx=p->x-1 ; dx<=p->x+1 ; dx++) {"
if (dx<0 || dx>dimensione_piano) continue;"
for (dy=p->y-1 ; dy<=p->y+1 ; dy++) {"
if (dx==p->x && dy==p->y) continue;"
if (dy<0 || dy>dimensione_piano) continue;"
q=cerca(dx, dy, -1);"
if (q && q->padre!=p->padre) {"
if (q->tempo < 0) crea_blocco(q);"
/* ...unisci i blocchi di p e q. */"
unisci_blocchi(p,q);"
}"
}"
}"
}"
}"
}

void inserisci(int x, int y, int t) {
/* Inserisce una cella di coordinate (x, y). */"
cella *p = hashtable[hash(x)][hash(y)];"
cella *q = NULL, *r;"
int dx, dy;"

/* Passo 1) Calcola il valore della hash e scorre la lista ordinata"
fino a trovare un elemento maggiore della cella. */"
while (p && (p->x < x || (p->x == x && p->y < y))) {"
q = p;"
p = p->next;"
}"

/* Passo 2) Se la cella esiste gia', esce. */"
if (p && p->x==x && p->y==y) {"
return;"
}"

/* Passo 3) Alloca la cella. */"
r = calloc(1,sizeof(cella));"
if(!r) {"
fprintf(stderr,""Errore nell'inserimento della cella.\n"");"
exit(-1); "
}"

/* Passo 4) Inizializza alcune variabili. */"
r->x = x;"
r->y = y;"
r->tempo = t;"
r->prossimo_nel_blocco=NULL;"
r->padre=NULL;"
r->prossimo_sul_piano=NULL;"
r->next = p;"

/* Passo 5) La inserisce nella lista, spostando i puntatori. */"
if (q == NULL) {"
hashtable[hash(x)][hash(y)] = r;"
}"
else {"
q->next = r;"
}"
"
/* Passo 6) La inserisce nella lista prossimo_sul_piano. */"
p = primo_sul_piano;"
q = NULL;"

while (p && (p->x < x || (p->x == x && p->y < y))) {"
q = p;"
p = p->prossimo_sul_piano;"
}"

if (q == NULL) {"
r->prossimo_sul_piano = primo_sul_piano;"
primo_sul_piano = r;"
}"
else {"
q->prossimo_sul_piano = r;"
r->prossimo_sul_piano = p;"
}"

/* Passo 7) Controlla se ha vicini e, se si', si aggiunge ai loro blocchi. */"
q = NULL;"
crea_blocco(r);"
for (dx=x-1 ; dx<=x+1 ; dx++) {"
if (dx<0 || dx>dimensione_piano) continue;"
for (dy=y-1 ; dy<=y+1 ; dy++) {"
if (dy<0 || dy>dimensione_piano) continue;"
if (dx==x && dy==y) continue;"
q = cerca(dx, dy, -1);"
if (q && q->padre != r->padre) {"
unisci_blocchi(r,q);"
}"
}"
}"
}

void cancella(int x, int y) {
/* Cancella la cella di coordinate (x,y). */"
cella *p, *q;"

/* Passo 1) Cancella dalla lista nell'hashtable. */"
p = hashtable[hash(x)][hash(y)];"
q = NULL;"
while (p && (p->x < x || (p->x == x && p->y < y))) {"
q = p;"
p = p->next;"
}"

if (!(p && p->x==x && p->y == y)) {"
return; // se la cella non esiste, esce."
}"

if (q==NULL) "
hashtable[hash(x)][hash(y)] = p->next;"
else"
q->next = p->next;"

/* Passo 2) Cancella dalla lista prossimo_sul_piano. */"
p = primo_sul_piano;"
q = NULL;"

while (p && (p->x < x || (p->x == x && p->y < y))) {"
q = p;"
p = p->prossimo_sul_piano;"
}"
"
if (!(p && p->x==x && p->y == y)) {"
return; // se la cella non esiste, esce."
}"

if (primo_sul_piano == p) "
primo_sul_piano = p->prossimo_sul_piano;"
else"
q->prossimo_sul_piano = p->prossimo_sul_piano;"

/* Passo 3) La rimuove dal suo blocco. */"
rimuovi_cella_dal_blocco(p);"

/* Passo 4) Dealloca la memoria. */"
free(p);"
}

void listacelle() {
/* Stampa la lista delle celle in un ordine non decrescente,"
prima secondo le x poi le y. In questa implementazione e' "
sufficiente scorrere la lista prossimo_sul_piano. */"
cella *q = primo_sul_piano;"

while(q) {"
printf(""%d %d\n"", q->x, q->y); "
q = q->prossimo_sul_piano;"
}"
}

void maxdimblocco() {
/* Stampa la dimesione del massimo blocco, scorrendo la "
lista dei blocchi, cercando il valore massimo del campo num. */"
int max = 0;"
blocco *p;"

for (p=primo_blocco; p; p=p->prossimo_blocco) {"
if (p->num > max)"
max = p->num;"
}"
printf(""m %d\n"",max);"
}

void evolvi(int steps) {
/* Calcola la situazione del piano dopo ""steps"" generazioni. */"
cella *p = primo_sul_piano;"
int x, y, dx, dy, ddx, ddy, i, j;"
"
while(steps > 0) {"
/* Per ogni cella p (usando la lista prossimo_sul_piano): */"
while(p) {"
if (p->tempo > tempo) { // E' una cella appena nata, e non va"
p = p->prossimo_sul_piano; // quindi considerata."
continue;"
}"
y = p->y;"
x = p->x;"
j = 0;"
"
/* Per cella (viva o morta) vicina. */"
for (dx=x-1 ; dx<=x+1 ; dx++) {"
if (dx<0 || dx>dimensione_piano) continue;"
for (dy=y-1 ; dy<=y+1 ; dy++) {"
i = 0;"
if (dx==x && dy==y) continue;"
if (dy<0 || dy>dimensione_piano) continue;"

/* Per ogni vicino (vivo o morto) dei suoi vicini. */"
for (ddx=dx-1 ; ddx<=dx+1 ; ddx++) {"
if (ddx<0 || ddx>dimensione_piano) continue;"
for (ddy=dy-1 ; ddy<=dy+1 ; ddy++) {"
if (ddx==dx && ddy==dy) continue;"
if (ddy<0 || ddy>dimensione_piano) continue;"
"
/* Conta quanti ""vicini-dei-vicini"" son vivi */"
if (cerca(ddx, ddy, tempo)) i++;"
}"
}"
/* La cella (dx, dy) nasce */"
if (i==3) inserisci(dx, dy, tempo+1);"
"
/* Conta quanti ""vicini"" son vivi */"
if (cerca(dx, dy, tempo)) j++;"
}"
}"
"
/* Se una cella va eliminata, la segno come ""morta"","
ponendo il tempo uguale a uno. */"
if (j <= 1 || j >= 4) cerca(x,y,-1)->tempo=1;"
p = p->prossimo_sul_piano; "
}"
"
/* Elimino le celle segnate come ""morte"". */"
p = primo_sul_piano;"
while(p) {"
x = p->x;"
y = p->y;"
i = p->tempo;"
p=p->prossimo_sul_piano;"
if (i==1) cancella(x,y);"
}"
steps--; "
tempo++;"
p = primo_sul_piano;"
}"
}

int main(void) {
char input;"
int x,y;"

while (scanf(""%c"",&input) != -1) {"
switch(input) {"
case 'c':"
/* Crea il piano */"
scanf(""%d"",&x);"
crea(x);"
break;"

case 'i': "
/* Inserisce nel piano una cella di coord (x,y) */"
scanf(""%d %d"",&x,&y);"
if (dimensione_piano > 0 && x >= 0 && y >= 0 && x <= dimensione_piano && y <= dimensione_piano)"
inserisci(x,y,tempo);"
break;"

case 'e':"
/* Evolve lo stato del piano di x passi. */"
scanf(""%d"",&x);"
if (dimensione_piano > 0 && x > 0) {"
evolvi(x);"
printf(""e %d\n"",x);"
}"
break;"

case 'l':"
/* Lista le celle del piano. */"
printf(""l\n"");"
listacelle(); "
printf(""-1\n"");"
break;"

case 'b':"
/* Stampa il numero di blocchi. */"
printf(""b %d\n"",n_blocchi);"
break;"
"
case 'm':"
/* Stampa la dimensione del massimo blocco. */"
maxdimblocco(); "
break;"
"
case 'f':"
/* Fine del programma. */"
printf(""f\n"");"
return 0; "
break;"
}"
}"
return 0;"
}

/* è tutto, semplice no? */

[[Categoria:Progetti]]

← Versione meno recente		Versione delle 08:52, 3 feb 2006
Riga 546:		Riga 546:

	/* è tutto, semplice no? */		/* è tutto, semplice no? */
		+
		+	Per quanto riguarda la discussione del progetto fai riferimento a [http://www.dsy.it/forum/attachment.php?s=&postid=21225 questo file], che contiene anche il file C del progetto.

	[[Categoria:Progetti]]		[[Categoria:Progetti]]

@@ Riga 2: / Riga 2: @@
     * Questo software e l'annessa documentazione
     * sono distribuiti sotto la GNU policy.
-    * [se non sai cos'è, vergognati, e poi acculturati un po':
+    * [se non sai cos'è, vergognati, e poi acculturati un po': [http://www.gnu.org/philosophy/free-sw.it.html]
+    *
     * Il fine della distribuzione gratuita è per combattere il

Algoritmi e strutture dati/Progetti/Life/Stesura I - Cronologia

Yoruno: Riportata alla revisione precedente da Yoruno

219.117.58.251: test

Yoruno il 08:52, 3 feb 2006

Yoruno il 08:48, 3 feb 2006

Yoruno il 08:47, 3 feb 2006