potenza.c
/*
Algoritmi e Programmazione Avanzata
Tutore: Sergio Porcu
Argomento: ricorsione
Calcolo di una potenza - di sistema, iterativo e ricorsivo.
*/
#include <stdio.h>
#include <math.h>
double potenzaIte (double x, int n);
double potenzaRic (double x, int n);
main (void)
{
float x;
double y;
int n;
fprintf (stdout, "Base x: ");
scanf ("%f", &x);
fprintf (stdout, "Esponente n: ");
scanf ("%d", &n);
fprintf (stdout, "Funzione di sistema (%f^%d) = %f\n", x, n, pow (x, n));
y = potenzaIte (x, n);
fprintf (stdout, "Ite (%f^%d) = %f\n", x, n, y);
y = potenzaRic (x, n);
fprintf (stdout, "Ric (%f^%d) = %f\n", x, n, y);
return;
}
double
potenzaIte (
double x,
int n
)
{
double pot;
int i;
pot = 1.0;
for (i=1; i<=n; i++) {
pot = pot * x;
}
return (pot);
}
double
potenzaRic (
double x,
-1-
potenza.c
int n
)
{
if (n==0) {
return (1.0);
}
if (n==1) {
return (x);
}
return (x * potenzaRic (x, n-1));
}
-2-
heapSort.c
/*
Algoritmi e Programmazione Avanzata
Tutore: Sergio Porcu
Argomento: ricorsione e ordinamento
Realizza l'algoritmo di ordinamento Heap Sort su
un vettore di interi.
Input: nome di 2 file;
file di ingresso:
prima riga = numero di elementi (interi) presenti nel file
di seguito i vari elementi
Output: sul file di output il vettore risultante dopo ogni
iterazione dell'algoritmo.
*/
#include <stdlib.h>
#include <stdio.h>
#define L 50
#define NDIGIT 3
#define PARENT(i) ((i-1) / 2)
#define LEFT(i) ((i*2) + 1)
#define RIGHT(i) ((i*2) + 2)
void HeapSort (int A[], int n, FILE *fpU );
main ()
{
FILE *fpI , *fpU ;
char nomeFileI [L], nomeFileU [L];
int i , j , n, vetvar , *vet ;
/* Lettura nome file */
fprintf (stdout , "Nome File di Ingresso: " );
scanf ("%s" , nomeFileI );
fprintf (stdout , "Nome File di Uscita: " );
scanf ("%s" , nomeFileU );
/* Apertura file */
fpI = fopen (nomeFileI , "r" );
fpU = fopen (nomeFileU , "w" );
if (fpI == NULL || fpU == NULL) {
fprintf (stderr , "Errore di apertura file.\n" );
exit (1);
}
/* Lettura file */
fscanf (fpI , "%d" , &n);
vet = (int *) malloc (n * sizeof (int ));
if (vet == NULL) {
fprintf (stderr , "Errore di allocazione del vettore.\n" );
exit (1);
}
/* Ciclo di lettura file */
-1-
heapSort.c
i = 0;
while (fscanf (fpI , "%3d" , &vet [i ]) != EOF ) {
i ++;
}
/* Ciclo di visualizzazione vettore */
fprintf (fpU , "\n" );
fprintf (fpU , "INIZIALE : " );
for (i =0; i <n; i ++) {
fprintf (fpU , "%3d " , vet [i ]);
}
fprintf (fpU , "\n\n" );
HeapSort (vet , n, fpU );
/* Ciclo di visualizzazione vettore */
fprintf (fpU , "\n" );
fprintf (fpU , "FINALE : " );
for (i =0; i <n; i ++) {
fprintf (fpU , "%3d " , vet [i ]);
}
fprintf (fpU , "\n" );
fclose (fpI );
fclose (fpU );
return;
}
void Swap( int v[], int n1, int n2)
{
int temp;
temp = v[n1];
v[n1] = v[n2];
v[n2] = temp;
}
void Heapify (int v[], int i , int heapsize )
{
int l , r , largest ;
l = LEFT(i );
r = RIGHT(i );
if (l < heapsize && v[l ]>v[i ]) {
largest = l ;
} else {
largest = i ;
}
if (r <heapsize && v[r ]>v[largest ]) {
largest = r ;
}
if (largest != i ) {
Swap(v,i ,largest );
Heapify (v,largest ,heapsize );
}
}
-2-
heapSort.c
void BuildHeap (int v[], int heapsize )
{
int i ;
for (i =(heapsize )/2-1; i >= 0; i --) {
Heapify (v,i ,heapsize );
}
return;
}
void HeapSort ( int v[], int dim , FILE *fpU )
{
int i , k,
heap_size = dim ;
BuildHeap (v, heap_size );
fprintf (fpU , "IN HEAP : " );
for (i =0; i <dim ; i ++) {
fprintf (fpU , "%3d " , v[i ]);
}
fprintf (fpU , "\n\n" );
for (i =dim -1; i > 0; i --) {
fprintf (fpU , "CICLO %3d: " , dim -i );
for (k=0; k<=i ; k++) {
fprintf (fpU , "%3d " , v[k]);
}
fprintf (fpU , " - " );
for (k=i +1; k<dim ; k++) {
fprintf (fpU , "%3d " , v[k]);
}
fprintf (fpU , "\n" );
Swap (v,0,i );
heap_size --;
Heapify (v,0,heap_size );
}
}
-3-
insertionSort.c
/*
Algoritmi e Programmazione Avanzata
Tutore: Sergio Porcu
Argomento: ricorsione e ordinamento
Realizza l'algoritmo di ordinamento per inserzio ne su
un vettore di interi.
Input: nome di 2 file;
file di ingresso:
prima riga = numero di elementi (interi) presenti nel file
di seguito i vari elementi
Output: sul file di output il vettore risultante dopo ogni
iterazione dell'algoritmo.
*/
#include <stdio.h>
#define L 50
main ()
{
FILE *fpI , *fpU ;
char nomeFileI [L], nomeFileU [L];
int i , j , n, vetvar , *vet ;
/* Lettura nome file */
fprintf (stdout , "Nome File di Ingresso: " );
scanf ("%s" , nomeFileI );
fprintf (stdout , "Nome File di Uscita: " );
scanf ("%s" , nomeFileU );
/* Apertura file */
fpI = fopen (nomeFileI , "r" );
fpU = fopen (nomeFileU , "w" );
if (fpI == NULL || fpU == NULL) {
fprintf (stderr , "Errore di apertura file.\n" );
exit (1);
}
/* Lettura file */
fscanf (fpI , "%d" , &n);
vet = (int *) malloc (n * sizeof (int ));
if (vet == NULL) {
fprintf (stderr , "Errore di allocazione del vettore.\n" );
exit (1);
}
/* Ciclo di lettura file */
i = 0;
while (fscanf (fpI , "%3d" , &vet [i ]) != EOF ) {
i ++;
}
/* Ciclo di visualizzazione vettore */
fprintf (fpU , "\n" );
fprintf (fpU , "INIZIALE : " );
-1-
insertionSort.c
for (i =0; i <n; i ++) {
fprintf (fpU , "%3d " , vet [i ]);
}
fprintf (fpU , "\n\n" );
/* Ciclo di ordinamento vettore */
for (i =1; i <n; i ++) {
vetvar = vet [i ];
j = i -1;
while ( j >=0 && vetvar <vet [j ] ) {
vet [j +1] = vet [j ];
j --;
}
vet [j +1] = vetvar ;
/* Ciclo di visualizzazione vettore */
fprintf (fpU , "CICLO %3d: " , i );
for (j =0; j <n; j ++) {
fprintf (fpU , "%3d " , vet [j ]);
if (j ==i ) {
fprintf (fpU , "%3s " , "-" );
}
}
fprintf (fpU , "\n" );
}
/* Ciclo di visualizzazione vettore */
fprintf (fpU , "\n" );
fprintf (fpU , "FINALE : " );
for (i =0; i <n; i ++) {
fprintf (fpU , "%3d " , vet [i ]);
}
fprintf (fpU , "\n" );
fclose (fpI );
fclose (fpU );
return;
}
-2-
mergeSort.c
/*
Algoritmi e Programmazione Avanzata
Tutore: Sergio Porcu
Argomento: ricorsione e ordinamento
Realizza l'algoritmo di ordinamento per fusione su un
vettore di interi.
Input: nome di 2 file;
file di ingresso:
prima riga = numero di elementi (interi) presenti nel file
di seguito i vari elementi
Output: sul file di output il vettore risultante dopo ogni
iterazione dell'algoritmo.
*/
#include <stdlib.h>
#include <stdio.h>
#define L 50
void MergeSort (int A[], int p, int r , int n, FILE *fpU );
void Merge (int A[], int p, int q, int r );
main ()
{
FILE *fpI , *fpU ;
char nomeFileI [L], nomeFileU [L];
int i , j , n, vetvar , *vet ;
/* Lettura nome file */
fprintf (stdout , "Nome File di Ingresso: " );
scanf ("%s" , nomeFileI );
fprintf (stdout , "Nome File di Uscita: " );
scanf ("%s" , nomeFileU );
/* Apertura file */
fpI = fopen (nomeFileI , "r" );
fpU = fopen (nomeFileU , "w" );
if (fpI == NULL || fpU == NULL) {
fprintf (stderr , "Errore di apertura file.\n" );
exit (1);
}
/* Lettura file */
fscanf (fpI , "%d" , &n);
vet = (int *) malloc (n * sizeof (int ));
if (vet == NULL) {
fprintf (stderr , "Errore di allocazione del vettore.\n" );
exit (1);
}
/* Ciclo di lettura file */
i = 0;
while (fscanf (fpI , "%3d" , &vet [i ]) != EOF ) {
i ++;
}
-1-
mergeSort.c
/* Ciclo di visualizzazione vettore */
fprintf (fpU , "\n" );
fprintf (fpU , "INIZIALE : " );
for (i =0; i <n; i ++) {
fprintf (fpU , "%3d " , vet [i ]);
}
fprintf (fpU , "\n\n" );
/* Chiamate di ordinamento vettore */
MergeSort (vet , 0, n-1, n, fpU );
/* Ciclo di visualizzazione vettore */
fprintf (fpU , "\n" );
fprintf (fpU , "FINALE : " );
for (i =0; i <n; i ++) {
fprintf (fpU , "%3d " , vet [i ]);
}
fprintf (fpU , "\n" );
fclose (fpI );
fclose (fpU );
return;
}
void MergeSort (
int A[],
int p,
int r ,
int n,
FILE *fpU
)
{
if (p<r ) {
int q=(p+r )/2;
int i ;
fprintf (fpU , "PARTIZIONE : " );
for (i =0; i <p; i ++) {
fprintf (fpU , " " );
}
for (i =p; i <=r ; i ++) {
fprintf (fpU , "%3d " , A[i ]);
}
fprintf (fpU , "\n" );
MergeSort (A, p, q, n, fpU );
MergeSort (A, q+1, r , n, fpU );
Merge (A, p, q+1, r );
fprintf (fpU , "FUSIONE : " );
for (i =0; i <p; i ++) {
fprintf (fpU , " " );
}
for (i =p; i <=r ; i ++) {
fprintf (fpU , "%3d " , A[i ]);
}
-2-
mergeSort.c
fprintf (fpU , "\n" );
}
return;
}
void Merge (
int A[],
int p,
int q,
int r
)
{
int *tmpvet =(int *)malloc ((r -p+1)*sizeof(int ));
int i =p;
int j =q;
int k=0;
if (tmpvet == NULL) {
fprintf (stderr , "Errore di allocazione del vettore temporaneo.\n" );
exit (1);
}
while ((i <q)&&(j <=r ))
if (A[i ]<A[j ])
tmpvet [k++]=A[i ++];
else
tmpvet [k++]=A[j ++];
while (i <q)
tmpvet [k++]=A[i ++];
while (j <=r )
tmpvet [k++]=A[j ++];
for (k=0;k<r -p+1;k++)
A[p+k]=tmpvet [k];
return;
}
-3-
quickSort.c
/*
Algoritmi e Programmazione Avanzata
Tutore: Sergio Porcu
Argomento: ricorsione e ordinamento
Realizza l'algoritmo di ordinamento QuickSort su un vettore
di interi.
Input: nome di 2 file;
file di ingresso:
prima riga = numero di elementi (interi) presenti nel file
di seguito i vari elementi
Output: sul file di output il vettore risultante dopo ogni
iterazione dell'algoritmo.
*/
#include <stdlib.h>
#include <stdio.h>
#define L 50
void Quicksort (int v[], int left , int right , int n, FILE *fpU );
void swap(int vet [], int i , int j );
main ()
{
FILE *fpI , *fpU ;
char nomeFileI [L], nomeFileU [L];
int i , j , n, vetvar , *vet ;
/* Lettura nome file */
fprintf (stdout , "Nome File di Ingresso: " );
scanf ("%s" , nomeFileI );
fprintf (stdout , "Nome File di Uscita: " );
scanf ("%s" , nomeFileU );
/* Apertura file */
fpI = fopen (nomeFileI , "r" );
fpU = fopen (nomeFileU , "w" );
if (fpI == NULL || fpU == NULL) {
fprintf (stderr , "Errore di apertura file.\n" );
exit (1);
}
/* Lettura file */
fscanf (fpI , "%d" , &n);
vet = (int *) malloc (n * sizeof (int ));
if (vet == NULL) {
fprintf (stderr , "Errore di allocazione del vettore.\n" );
exit (1);
}
/* Ciclo di lettura file */
i = 0;
while (fscanf (fpI , "%3d" , &vet [i ]) != EOF ) {
i ++;
}
-1-
quickSort.c
/* Ciclo di visualizzazione vettore */
fprintf (fpU , "\n" );
fprintf (fpU , "INIZIALE : " );
for (i =0; i <n; i ++) {
fprintf (fpU , "%3d " , vet [i ]);
}
fprintf (fpU , "\n\n" );
/* Ordinamento del vettore */
/* fpU e' passato per avere i passi intermedi */
fprintf (fpU ,
"Legenda: x = Elemento pivot usato per dividere le partizioni\n"
" i = Indice sx\n"
" j = Indice dx (usato anche per dividere l a partizioni)\n\n"
);
Quicksort (vet , 0, n-1, n, fpU );
/* Ciclo di visualizzazione vettore */
fprintf (fpU , "\n" );
fprintf (fpU , "FINALE : " );
for (i =0; i <n; i ++) {
fprintf (fpU , "%3d " , vet [i ]);
}
fprintf (fpU , "\n" );
fclose (fpI );
fclose (fpU );
return;
}
void Quicksort ( /* Funzione di ordinamento */
int v[], /* Vettore da ordinare */
int p, /* Primo elemento del vettore */
int r , /* Ultimo elemento del vettore */
int n, /* Numero di elementi nel vettore (debug) */
FILE *fpU /* File su cui vengono scritti i risultati intermed i */
)
{
int i , j , x, k;
if (p >= r )
return;
x = v[p];
i = p-1; j = r +1;
while (i <j ) {
while (v[--j ] > x);
while (v[++i ] < x);
fprintf (fpU , "p=%3d r=%3d: " , p, r );
for (k=0; k<p; k++)
fprintf (fpU , " " );
-2-
quickSort.c
for (k=p; k<=r ; k++) {
char riemp =3; /* Riempitivo */
fprintf (fpU , "%3d" , v[k]);
if (k==p) {
fprintf (fpU , "x" , v[k]);
riemp --;
}
if (k==i ) {
fprintf (fpU , "i" , v[k]);
riemp --;
}
if (k==j ) {
fprintf (fpU , "j" , v[k]);
riemp --;
}
while (riemp --) fprintf (fpU , " " );
}
fprintf (fpU , "\n" );
if (i <j ) {
swap (v, i , j );
}
}
Quicksort (v, p, j , n, fpU );
Quicksort (v, j +1, r , n, fpU );
}
void swap( /* Scambia l'elemento j-esimo con l'elemento i-esim o di vet */
int vet [],
int i ,
int j
)
{
int tmp=vet [i ];
vet [i ]=vet [j ];
vet [j ]=tmp;
}
-3-
damaCinese.c
/*
Algoritmi e Programmazione Avanzata
Tutore: Sergio Porcu
Argomento: ricorsione
Dama cinese.
Il gioco consiste nel muovere una pedina alla vo lta
lungo le linee orizzontali o verticali, in modo da
"saltare" la pedina vicina, che così viene elimi nata
dal tavolo di gioco. Il salto della pedina può e ssere
eseguito se il posto di destinazione è libero.
La partita termina quando si arriva ad un punto in
cui non è possibile eseguire altre mosse. Se sul la
scacchiera è presente una sola pedina il giocato re
ha vinto. Una ulteriore sfida consiste di termin are
il gioco con l'ultima pedina collocata nella pos izione
centrale della scacchiera.
*/
#include <stdio.h>
/* casella vuota */
#define V 0
/* casella piena */
#define P 1
/* casella fuori scacchiera */
#define I 255
/* Dimensione Scacchiera */
#define SIZE 8
/* Prototipi */
int muovi (int scacc [SIZE +1][SIZE +1], int mosse[31][4], int n);
main ()
{
/* Definizione Scacchiera */
int scacc [SIZE +1][SIZE +1] =
{
{I , I , I , I , I , I , I , I , I },
{I , I , I , P, P, P, I , I , I },
{I , I , I , P, P, P, I , I , I },
{I , P, P, P, P, P, P, P, I },
{I , P, P, P, V, P, P, P, I },
{I , P, P, P, P, P, P, P, I },
{I , I , I , P, P, P, I , I , I },
{I , I , I , P, P, P, I , I , I },
{I , I , I , I , I , I , I , I , I }
};
/* Buffer memorizzazione mosse */
int mosse[31][4];
/* Altre variabili */
FILE *fout ;
int i ;
char nomeFile [80];
if (muovi (scacc , mosse, 0) == 0) {
-1-
damaCinese.c
fprintf (stdout , "Soluzione non esistente.\n" );
return;
}
fprintf (stdout , "Nome file di output: " );
scanf ("%s" , nomeFile );
fout = fopen (nomeFile , "w" );
if (fout == NULL) {
fprintf (stderr , "Errore in apertura file %s\n" , nomeFile );
return;
}
for (i =0; i <31; i ++) {
fprintf (fout , "%d %d %d %d\n" , mosse[i ][0], mosse[i ][1],
mosse[i ][2], mosse[i ][3]);
}
fclose (fout );
return;
}
/*
* Funzione Ricorsiva
*/
int
muovi (
int scacc [SIZE +1][SIZE +1],
int mosse[31][4],
int n
)
{
/* Offset pedina da mangiare */
int xOffPedina [4] = { 0, 1, 0, -1};
int yOffPedina [4] = { -1, 0, 1, 0};
/* Offset casella di arrivo */
int xOffArrivo [4] = { 0, 2, 0, -2};
int yOffArrivo [4] = { -2, 0, 2, 0};
/* Altre variabili */
int x1, y1, x2, y2, x3, y3, k;
#if 0
/* Debug Printing */
printf ("%d\n" , n);
#endif
/* Condizione di terminazione */
if (n == 31) {
return (1);
}
/* Per ogni cella della scacchiera ... */
for (x1=1; x1<SIZE ; x1++) {
for (y1=1; y1<SIZE ; y1++) {
/* ... se c'e' una pedina ... */
if (scacc [x1][y1] == P) {
-2-
damaCinese.c
/* ... guardo se riesco a mangiare ... */
for (k=0; k<4; k++) {
x2 = x1 + xOffPedina [k];
y2 = y1 + yOffPedina [k];
if (scacc [x2][y2] == P) {
x3 = x1 + xOffArrivo [k];
y3 = y1 + yOffArrivo [k];
if (scacc [x3][y3] == V) {
/* ... faccio la mossa ... */
scacc [x3][y3] = P;
scacc [x2][y2] = V;
scacc [x1][y1] = V;
/* ... ricorro ... */
if (muovi (scacc , mosse, n+1) == 1) {
/* ... se ma mossa era OK, la memorizzo ... */
mosse[n][0] = x1;
mosse[n][1] = y1;
mosse[n][2] = x3;
mosse[n][3] = y3;
return (1);
} else {
/* ... altrimenti backtrack */
scacc [x3][y3] = V;
scacc [x2][y2] = P;
scacc [x1][y1] = P;
}
}
}
}
}
}
}
return (0);
}
-3-
ottoRegine.c
/*
Algoritmi e Programmazione Avanzata
Tutore: Sergio Porcu
Argomento: ricorsione
Questo problema e' un classico problema di back- tracking
dalla soluzione ricorsiva.
In una scacchiera sono disposte otto regine. Il compito del
programma e' quello di trovare tutte le disposiz ioni delle
otto regine sulla scacchiera, affinche' nessuna regina possa
mangiare un'altra regina, ovvero affinche' se un a regina
occupa una posizione sulla scacchiera 8X8, non c i devono
essere altre regine ne sulla stessa riga, ne sul la stessa
colonna, e neanche su una delle sue diagonali (s i ricordo che
la regina nel gioco degli scacchi puo' muoversi di un numero
di caselle arbitrario, sia in orizzontale, che i n verticale,
che in obliquo).
*/
#include <stdio.h>
int queen [8];
char row [8],
dia [15],
revdia [15];
int muovi ( int );
void setqueen ( int , int );
void removequeen ( int , int );
main ()
{
int i ;
if( muovi ( 0))
for( i =0; i <8; i ++)
printf ( "%d " , queen [i ]);
}
int muovi ( int n)
{
int i ;
if( n == 8)
return( 1);
for( i =0; i <8; i ++)
if( !row [i ] && !dia [n+i ] && !revdia [n-i +7])
{
setqueen ( n, i );
if( muovi ( n+1))
return( 1);
removequeen ( n, i );
}
return( 0);
}
-1-
ottoRegine.c
void setqueen ( int n, int i )
{
queen [n] = i ;
row [i ] = 255;
dia [n+i ] = 255;
revdia [n-i +7] = 255;
}
void removequeen ( int n, int i )
{
queen [n] = 0;
row [i ] = 0;
dia [n+i ] = 0;
revdia [n-i +7] = 0;
}
-2-
torriHanoi.c
/*
Algoritmi e Programmazione Avanzata
Tutore: Sergio Porcu
Argomento: ricorsione
Torre di Hanoi. Soluzioni Ricorsiva e Iterativa.
Le regole del gioco sono due e molto semplici:
1) si puo' spostare solo il disco situato sulla
sommità di una torre
2) un disco piu' grande non può essere posato
sopra un disco piu' piccolo. Lo scopo e'
quello di spostare tutti i dischi su un'altra
asta in modo che risultino ancora disposti
nello stesso ordine. Ogni disco, una volta
portato su un'asta, e' calamitato e quando
viene rilasciato e' attratto verso la base
se la mossa e' corretta altrimenti torna
automaticamente al posto da dove e' stato
prelevato.
*/
#include <stdio.h>
void hanoiRic (int *, int , int , int );
void hanoiIte (int );
main ()
{
int mossa, n;
fprintf (stdout , "Numero dischi: " );
scanf ( "%d" , &n);
mossa = 1;
fprintf (stdout , "HANOI Ricorsivo:\n" );
hanoiRic (&mossa, n, 0, 2);
fprintf (stdout , "HANOI Iterativo:\n" );
hanoiIte (n);
return;
}
void
hanoiRic (
int *mossa,
int n,
int source ,
int dest
)
{
int aux ;
/*fprintf (stdout, "### %d , %d -> %d\n", n, source , dest);*/
if (n > 0) {
aux = 3 - (source + dest );
-1-
torriHanoi.c
hanoiRic (mossa, n - 1, source , aux );
fprintf (stdout , "(%d) Source %d - Dest. %d \n" , *mossa, source , dest );
*mossa = *mossa + 1;
hanoiRic (mossa, n - 1, aux , dest );
}
return;
}
void
hanoiIte (
int n
)
{
int *pos , numeroMosse ;
int i , disc , mossa, delta , newPos;
/* Vettore Dinamico COntenente la posizione dei dis chi (0, 1, 2) */
pos = (int *) malloc (n * sizeof (int ));
/* Numero di Mosse */
numeroMosse = (1<<n)-1;
/* Inizializzo la posizione dei dischi: tutti sulla torre 0 */
for (i =0;i <n;i ++) {
pos [i ]=0;
}
for (mossa=0; mossa<numeroMosse ; mossa++) {
/* Cerco il disco da muovere (disc): LSB a zero
e dove muoverlo delta */
for (disc =0, delta =n&1; disc <n; disc ++, delta ^=1) {
if (((mossa >> disc )&1)==0) {
break;
}
}
/* Calcolo la nuova posizione del disco */
newPos = (pos [disc ]+1+delta )%3;
/* Visualizzo la mossa */
fprintf (stdout , "(%d) Source %d - Dest. %d \n" , mossa+1,
pos [disc ], newPos);
/* Modifico la posizione del disco */
pos [disc ]=newPos;
}
free (pos );
return;
}
-2-
tourCavaliere.c
/*
Algoritmi e Programmazione Avanzata
Tutore: Sergio Porcu
Argomento: ricorsione
Tour del Cavaliere.
Trova una possibile soluzione al problema di
far percorrere ad un cavallo tutte le caselle
di una scacchiera una sola volta. Soluzione
mediante ricorsione "brutale".
*/
#include <stdio.h>
#define DIM 8
#define KO 0
#define OK 1
int muovi (int, int, int, int [], int [], int [][DIM]);
int
main (
)
{
int offsetX[8], offsetY[8], scacc[DIM][DIM];
int i, j, result;
offsetX[0] = 2; offsetY[0] = 1;
offsetX[1] = 1; offsetY[1] = 2;
offsetX[2] = -1; offsetY[2] = 2;
offsetX[3] = -2; offsetY[3] = 1;
offsetX[4] = -2; offsetY[4] = -1;
offsetX[5] = -1; offsetY[5] = -2;
offsetX[6] = 1; offsetY[6] = -2;
offsetX[7] = 2; offsetY[7] = -1;
for (i=0; i<DIM; i++) {
for (j=0; j<DIM; j++) {
scacc[i][j] = 0;
}
}
scacc[0][0] = 1;
result = muovi(2, 0, 0, offsetX, offsetY, scacc);
if (result == OK) {
for (i=0; i<DIM; i++) {
for (j=0; j<DIM; j++) {
fprintf (stdout, "%2d ", scacc[i][j]);
}
fprintf (stdout, "\n");
}
return (OK);
} else {
fprintf (stdout, "Soluzione non trovata\n");
-1-
tourCavaliere.c
return (KO);
}
}
int
muovi (
int mossa,
int posx,
int posy,
int offsetX[],
int offsetY[],
int scacc[][DIM]
)
{
int i, ret, newposx, newposy;
if (mossa == (DIM*DIM+1)) {
return (OK);
}
for (i=0; i<8; i++) {
newposx = posx + offsetX[i];
newposy = posy + offsetY[i];
if ((newposx<DIM) && (newposx>=0) && (newposy<DIM) && (newposy>=0)) {
if (scacc[newposx][newposy] == 0) {
scacc[newposx][newposy] = mossa;
ret = muovi(mossa+1, newposx, newposy, offsetX, offsetY, scacc);
if (ret == 0) {
scacc[newposx][newposy] = 0;
} else {
return (OK);
}
}
}
}
return (KO);
}
-2-
anagrammi.c
/*
Algoritmi e Programmazione Avanzata
Tutore: Sergio Porcu
Argomento: ricorsione
Generazione di anagrammi (ricorsivo).
Visualizza TUTTI gli anagrammi con duplicazione.
Ad esempio, la parola aab, fornira' anagrammi
ripetuti: aab, aab, aba, aba, baa, baa.
*/
#include <stdio.h>
#define MAX_L 10
void genAna (char *, int *, int , int );
void visAna (char *, int *, int );
main ()
{
char parola [MAX_L];
int usato [MAX_L];
int l , i ;
fprintf (stdout , "Introduci la parola: " );
scanf ("%s" , parola );
l = strlen (parola );
for (i =0; i <l ; i ++) {
usato [i ] = (-1);
}
fprintf (stdout , "Anagrammi:\n" );
genAna (parola , usato , l , 0);
}
void
genAna (
char *parola ,
int *usato ,
int l ,
int level
)
{
int i ;
if (level == l ) {
visAna (parola , usato , l );
return;
}
for (i =0; i <l ; i ++) {
if (usato [i ]==(-1)) {
usato [i ] = level ;
genAna (parola , usato , l , level +1);
-1-
anagrammi.c
usato [i ] = (-1);
}
}
return;
}
void
visAna (
char *parola ,
int *usato ,
int l
)
{
static numeroAnagramma = 1;
int i , j ;
fprintf (stdout , "%d " , numeroAnagramma);
numeroAnagramma++;
for (i =0; i <l ; i ++) {
for (j =0; j <l ; j ++) {
if (usato [j ]==i ) {
fprintf (stdout , "%c" , parola [j ]);
break;
}
}
}
fprintf (stdout , "\n" );
return;
}
-2-
mcd.c
/*
Algoritmi e Programmazione Avanzata
Tutore: Sergio Porcu
Argomento: ricorsione
MCD secondo Euclide - iterativo e ricorsivo.
*/
#include <stdio.h>
int mcdRic (int a, int b);
int mcdIte (int a, int b);
void swap (int *a, int *b);
main ()
{
int n, n1, n2;
fprintf (stdout, "N1: ");
scanf ("%d", &n1);
fprintf (stdout, "N2: ");
scanf ("%d", &n2);
n = mcdIte (n1, n2);
fprintf (stdout, "Ite = %d\n", n);
n = mcdRic (n1, n2);
fprintf (stdout, "Ric = %d\n", n);
return;
}
int
mcdIte (
int a,
int b
)
{
int tmp, r;
while ( b!=0 ) {
if (b>a) {
swap (&a, &b);
}
r = a%b;
a = b;
b = r;
}
return (a);
}
int
mcdRic (
int a,
int b
-1-
mcd.c
)
{
int r;
if (b>a) {
swap (&a, &b);
}
if (b==0) {
return (a);
}
r = a%b;
return (mcdRic (b, r));
}
void
swap (
int *a,
int *b
)
{
int tmp;
tmp = *a; *a = *b; *b = tmp;
return;
}
-2-