Esercizio 2

Obiettivo dell'esercizio

Realizzare programmi per generare quadrato magico, triangolo di Pascal e il gioco della Vita (descritti sotto).


Scadenza: 31-05-2004


Quadrato Magico

Un quadrato magico è una matrice di numeri in cui la somma degli numeri è la stessa per ogni colonna, ogni riga e i due diagonali. Per esempio:

8
 1
 6
3
 5
 7
4
 9
 2

Uno dei sistemi più semplici per costruire un quadrato magico, di lato dispari, è il seguente:
  1. Si parte sempre dalla casella centrale del lato superiore e si procede nella sequenza numerica aggiungendo il numero successivo nel riquadro in diagonale a destra del livello superiore. Quando la mossa richiederebbe di uscire dal quadrato, come in questo primo caso, si prosegue aggiungendo il numero seguente nella casella sul lato opposto della stessa riga in cui andrebbe collocato, nel posto in cui andrebbe, idealmente, se ci fosse un altro quadrato uguale adiacente (vedi il numero 2 rispetto al numero 1).
  2. La stessa questione si ripropone per la mossa successiva. Il 3 andrebbe collocato a in alto a destra rispetto al 2, e slitta alla prima casella a sinistra della stessa riga superiore.
  3. Quando si ha completato la serie di numeri corrispondente al numero di lati del quadrato creato (in questo caso 3), si prosegue scendendo di una casella (vedi il numero 4 rispetto al numero 3).
  4. Il 5 e il 6 seguono tranquillamente la regola generale e si dispongono in alto a destra rispetto al numero precedente.
  5. Per la stessa ragione spiegata al terzo punto, dopo il 6 il 7 prosegue la serie dalla casella sottostante.
  6. L'8, come quanto avvenuto con il 3, al secondo punto, si ritrova in alto a sinistra.
  7. E sempre per la stessa ragione il 9 va nella prima casella in basso della riga verticale centrale, non potendo andare in alto a destra dell'8. E a questo punto il quadrato magico è completato.
Il programma che costruisce il quadrato magico deve effettuare le seguenti operazioni
  1. chiedere il numero delle righe r dall'utente
  2. controllare se il numero è dispari; se no ritornare al punto 1, altrimenti avanti
  3. allocare memoria usando malloc per una matrice con  r righe e  r collone
  4. riempire la matrice secondo il algoritmo sopra
  5. controllare se il risultato è un quadrato magico
  6. stampare il quadrato magico sul video


Triangolo di Pascal (o di Tartaglia).

Scrivere un programma che genera il triangolo di Pascal

1



1
 1


1
 2
 1

1
 3
 3
 1
1
 4
 6
 4
 1

fino alla riga specificata dall'utente. Il programma deve memorizzare le righe generate in una matrice triangolare-bassa
int **triangolo
le cui righe devono essere allocate dinamicamente senza sprecare celle di memoria.
Le righe del triangolo sono numerate 0,1,2...k,... La riga k-esima contiene k+1 elementi; il primo e l'ultimo sono sempre 1; ogni altro elemento si ricava, per k>=2, 1<=i<=k-1 come
triangolo[k][i]=triangolo[k-1][i-1]+triangolo[k-1][i].

Il programma deve avere un main che richiede il numero di righe da generare, alloca le righe necessarie mediante una funzione

int ** alloca_triangolo(int nr_righe)

richiama una funzione

void genera_triangolo(int **t, int nr_righe)

per riempire le righe necessarie e quindi le stampa. A stampa effettuata la memoria allocata per le righe deve essere rilasciata da una funzione

void cancella_triangolo(int **t, int nr_righe).


Gioco della Vita

Life e` un gioco che simula in modo semplificato l'evoluzione di una colonia di cellule soggetta a semplici regole. Il gioco si svolge su una matrice di caselle NxN, ognuna delle quali puo` ospitare una cellula o essere vuota. La matrice deve essere memorizzata come un array bidimensionale
int **matrice
(matrice[i,j]=1 se la casella contiene una cellula, 0 altrimenti). La configurazione evolve, dal passo k al passo k+1 secondo le seguenti regole

I vicini di una casella [i,j] sono

[i-1,j], [i+1,j], [i,j-1], [i,j+1], [i-1,j-1], [i+1,j+1], [i-1,j+1], [i+1,j-1]

 X 
 X
  X
 X
[i,j]
  X
 X
X
  X

(se una coppia di indici esce dalla matrice, non viene contata).
Il main deve contenere un ciclo (infinito) che offre le seguenti possibilita`
Inserimento e cancellazione: in entrambe queste voci vengono lette una serie di coordinate [riga,colonna], nelle quali viene creata (o cancellata) una cellula; la creazione di una cellula in una cella gia` piena non ha alcun effetto, ma non e` un errore; la cancellazione di una cellula da una casella gia` vuota non ha alcun effetto ma non e` un errore. L'inserimento di una coordinata -1 termina la fase di inserimento o di cancellazione  e riporta al menu di scelta principale.

Modifica delle dimensioni della matrice: viene creata una nuova matrice NxN con il valore di N specificato. Se il nuovo N e` piu` grande del precedente, tutta la vecchia configurazione viene ricopiata nella nuova matrice alle stesse coordinate, mentre le caselle nuove sono inizialmente vuote. Se il nuovo N e` piu` piccolo, tutte le caselle della vecchia configurazione con le coordinate ancora presenti nella nuova permangono, mentre le altre caselle vecchie scompaiono.