/*
Programmazione II - Esempio di codice
<![CDATA[
Example code: recursive implementation of the hanoi tower problem.
(20000721 prelz@mi.infn.it)
*/
#include <stdio.h>
#define MAXTOWERS 3
/* A "tower" is an unsigned long int: if disk number N
is present bit 2^N is turned on */
typedef unsigned long tower_t;
tower_t towers[MAXTOWERS];
/* This is just a move counter */
unsigned long nmoves;
int move_disks(int howmany, int from, int to);
int move_disk(int from, int to);
int fill_tower(int tower, int howmany);
int main(int argc, char *argv[])
{
int i;
char line[80];
int ndisks;
printf("How many disks should I put on the first tower? ");
fgets(line, sizeof(line), stdin);
ndisks = atoi(line);
fill_tower(0,ndisks);
nmoves = 0;
printf("Before (nmoves = %d):\n",nmoves);
for (i=0;i<MAXTOWERS;i++)
{
printf("towers[%d] = [%016X]\n",i,towers[i]);
}
move_disks(ndisks,0,2);
printf("\n\nAfter (nmoves = %d):\n",nmoves);
for (i=0;i<MAXTOWERS;i++)
{
printf("towers[%d] = [%016X]\n",i,towers[i]);
}
exit(0);
}
int
fill_tower(int tower, int howmany)
{
int i;
if (tower < 0 || tower >= MAXTOWERS) return(-1);
if (howmany > (sizeof(tower_t)*8))
howmany = sizeof(tower_t)*8;
for (i=0;i<howmany;i++)
{
towers[tower]<<=1;
towers[tower]|=1;
}
return(0);
}
int
move_disks(int howmany, int from, int to)
{
int storage;
if (howmany > 1)
{
for (storage=0; storage<MAXTOWERS; storage++)
{
if (storage != from && storage != to) break;
}
if (storage >= MAXTOWERS)
{
fprintf(stderr,"Cannot find a storage tower\n");
return(-1);
}
if (move_disks(howmany - 1, from, storage) < 0) return(-1);
if (move_disk(from, to) < 0) return(-1);
if (move_disks(howmany - 1, storage, to) < 0) return(-1);
}
else
{
if (move_disk(from, to) < 0) return(-1);
}
return(0);
}
int
move_disk(int from, int to)
{
tower_t test_mask, which_one;
int i;
static max_bit = (1<<(8*sizeof(tower_t)-1));
nmoves++;
/* Move top disk from "from" to "to" tower */
if (towers[from] == 0)
{
fprintf(stderr,"No disks found on tower %d\n",from);
return(-1);
}
for (test_mask = max_bit,
which_one = max_bit;
which_one > 0;
which_one>>=1,test_mask = ((test_mask>>1)|max_bit))
{
if ((towers[from] & which_one)!=0) break;
}
/* Can we move it ? */
if ((towers[to] & test_mask) != 0)
{
fprintf(stderr,"Cannot move a disk from [%016X] to [%016X].\n",
towers[from], towers[to]);
return(-1);
}
/* Move disk */
towers[to] ^= which_one;
towers[from] ^= which_one;
printf("\nMove #%d:\n",nmoves);
for (i=0;i<MAXTOWERS;i++)
{
printf("towers[%d] = [%016X]\n",i,towers[i]);
}
return(0);
}
]]></plaintext></span>