Per chi fosse interessato alla programmazione in C ecco un esempio di utilizzo di tecniche quali la ricorsività e la memorizzazione di matrici a due indici mediante vettori.
Il programma che viene presentato di seguito è stato realizzato dal professor
Zironi dell’Università di Modena per il corso di Teoria e Applicazioni alle
Macchine Calcolatrici. In questa sede si vuole fornire un’analisi del listato per permettore al lettore di apprezzare metodi che possono risultare molto utili in determinate situazioni.
Supponendo di avere una scacchiera di 8×8 caselle, vi si vogliono disporre 8 regine in modo tale che, alla prima mossa, non si trovino in presa reciproca.
Si ricorda che nel gioco degli scacchi la regina si può muovere in orizzontale, verticale e lungo linee parallele alle diagonali principale e secondaria.
1. Si posiziona la prima regina (preferibilmente nella casella in alto a sinistra);
2. si posiziona la seconda regina in modo tale che non sia in presa reciproca con la prima;
3. si procede in questo modo finchè:
regine senza avere sistemato l’ultima.
Nel caso a. si stampa la soluzione, nel caso b. si riposiziona l’ultima regina e si riprende dal punto 3.
Ogni volta che si sistema una regina sulla scacchiera, occorre sapere in quali caselle sarebbe presa dalle regine precedentemente posizionate. Per tenere memoria di queste caselle vengono utilizzati tre vettori: lr (righe libere), ldp (diagonali parallele alla principale libere), lds (diagonali parallele alla secondaria libere). In essi il valore 1 indica che nella casella
è possibile mettere una regina, il valore 0 indica il caso contrario. Si noti che non vengono considerate le colonne in quanto il loro indice viene
utilizzato come indice di variazione dell’algoritmo.
In questo modo, senza utilizzare una matrice a due indici per rappresentare la scacchiera, siamo in grado memorizzare le posizioni di tutte le regine.
Supponendo di considerare dati di tipo carattere (1 byte), i vantaggi ottenuti sono molteplici:
1. innanzi tutto si può notare che volendo mantenere in memoria una matrice di 8×8 elementi occorrono 64 byte, mentre per memorizzare i vettori lr, ldp ed lds bastano 38 byte, in quanto 8 sono le righe e
15 le diagonali sia parallele alla principale che alla secondaria. In questo modo si ha un discreto risparmio di memoria già per una scacchiera di dimensioni ridotte come quella utilizzata in questo caso.
2. Un altro vantaggio deriva dal minor numero di celle contigue necessarie per memorizzare l’intera struttura. I vettori, infatti, possono essere allocati in tre aree di memoria differernti; la matrice, invece, necessita di 64 celle contigue per essere memorizzata.
3. Abbiamo inoltre un più rapido accesso agli elementi memorizzati grazie al minor numero di indici utilizzati.
Sistema utilizzato per numerare le diagonali parallele alla principale.
Sistema utilizzato per numerare le diagonali parallele alla secondaria.
(Cliccare qui per scaricare il file REGINE.C)
include
void prova(int ic); void stampa_soluzione(); int ns, r[8], lr[8],
void main()
{
int i;
for(i=0;i<8;i++)
lr[i]=1;
for(i=0;i<15;i++)
ldp[i]=lds[i]=1;
prova(0);
}
void prova (int ic)
{
int ir;
for(ir=0;ir<8;ir++)
if(lr[ir])
if(ldp[ir-ic+7])
}
void stampasoluzione(void)
{
int i,j,k,l,diversa,uguali,
for(i=0;i<8;i++)
w[i]=r[i];
diversa=1;
i=0;
while((i
j=0;
while((j<4)&&diversa)
i++;
}
if(diversa)
{
for(i=0;i<8;i++)
clrscr();
printf(“nn Soluzione n.%2d: “,ns);
for(i=0;i<8;i++)
printf(“nn”);
for(j=0;j<8;j++)
printf(” +”);
for(i=0;i<8;i++)
printf(“n”);
ns++;
getch();
}
}
E’ un esempio di ricorsività diretta che qui viene utilizzata per la ricerca della posizione delle regine sulla scacchiera. In questo particolare caso risulta appropriato l’uso di una funzione di questo tipo in quanto l’algoritmo
è tipicamente ricorsivo, pertanto la sua realizzazione mediante un ciclo variato sull’indice di colonna non permetterebbe, alla fine del ciclo, di ritornare alla penultima regina se non mediante indici ausiliari. La struttura ricorsiva, invece, realizza automaticamente il processo di ricerca all’indietro.
Questa funzione realizza la stampa sullo schermo della scacchiera in cui il simbolo
