v16i100: hanoi - Towers of Hanoi, Part01/01

[Sameer Parekh]

Submitted-by: Sameer Parekh <zane at ddsw1.mcs.com>
Posting-number: Volume 16, Issue 100
Archive-name: hanoi/part01

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#		"End of shell archive."
# Contents:  README hanoi.c hanoimod.c
# Wrapped by zane at ddsw1 on Mon Feb 11 16:46:19 1991
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'README' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'README'\"
else
echo shar: Extracting \"'README'\" \(970 characters\)
sed "s/^X//" >'README' <<'END_OF_FILE'
The Towers of Hanoi
X
X	These two programs are based upon the one in the book
X_The_Age_of_Intelligent_Machines by Raymond Kurzweil.  (ISBN 0-262-11121-7)
X
X	They solve the famous towers of hanoi problem recursively.
The hanoi program gives instructions on how to solve the problem, and
the hanoimod program shows the answer.
X
XFor example:
X$ hanoi 3
X
Move disk 1 from tower 1 to tower 2
Move disk 2 from tower 1 to tower 3
Move disk 1 from tower 2 to tower 3
Move disk 3 from tower 1 to tower 2
Move disk 1 from tower 3 to tower 1
Move disk 2 from tower 3 to tower 2
Move disk 1 from tower 1 to tower 2
X
X$ hanoimod 3
X
X1	3 2
X2	1
X3
X
X1	3
X2	1
X3	2
X
X1	3
X2
X3	2 1
X
X1
X2	3
X3	2 1
X
X1	1
X2	3
X3	2
X
X1	1
X2	3 2
X3
X
X1
X2	3 2 1
X3
X
X	Beware, this program grows exponentially.  hanoi n creates
X  n
X(2  - 1) lines.  (E. g. hanoi 20 creates 1,048,575 lines.)
X
X(I compiled this on a System V/386 Release 3.2 UNIX.  I see no reason
why it shouldn't work on other systems, but I haven't tested it.)
X
X 
X 
END_OF_FILE
if test 970 -ne `wc -c <'README'`; then
    echo shar: \"'README'\" unpacked with wrong size!
fi
# end of 'README'
fi
if test -f 'hanoi.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'hanoi.c'\"
else
echo shar: Extracting \"'hanoi.c'\" \(969 characters\)
sed "s/^X//" >'hanoi.c' <<'END_OF_FILE'
X/*****************************************
X * hanoi.c --
X *  Towers of Hanoi program as in _The Age of Intelligent Machines_
X *  by Raymond Kurzweil with main routine written by Sameer Parekh
X *  (zane at ddsw1.MCS.COM)
X *****************************************/
X
void hanoi(original, destination, free, number_of_disks)
int original, destination, free, number_of_disks;
X
X{
if (number_of_disks == 1) {
X	printf("Move disk 1 from tower %d to tower %d\n", original, destination);
X	return;
X	}
X
hanoi(original, free, destination, number_of_disks - 1);
X
printf("Move disk %d from tower %d to tower %d\n", number_of_disks, original, destination);
X
hanoi(free, destination, original, number_of_disks - 1);
X
return;
X}
X
int main(argc, argv)
int argc;
char **argv;
X
X{
int number;
if (argc != 2) {
X	printf("Usage: %s <number of disks>\n", argv[0]);
X	exit(1);
X	}
number = atoi(argv[1]);
X
if (number < 1) {
X	puts("Argument not appropriate!");
X	exit(1);
X	}
X
hanoi(1, 2, 3, number);
X}
X
X
END_OF_FILE
if test 969 -ne `wc -c <'hanoi.c'`; then
    echo shar: \"'hanoi.c'\" unpacked with wrong size!
fi
# end of 'hanoi.c'
fi
if test -f 'hanoimod.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'hanoimod.c'\"
else
echo shar: Extracting \"'hanoimod.c'\" \(1532 characters\)
sed "s/^X//" >'hanoimod.c' <<'END_OF_FILE'
X/*****************************************
X * hanoi.c --
X *  Towers of Hanoi program as in _The Age of Intelligent Machines_
X *  by Raymond Kurzweil with main routine written by Sameer Parekh
X *  (zane at ddsw1.MCS.COM)
X *  and with display routine by Sameer Parekh
X *****************************************/
X
X
mvdisk(number, destination, position, max)
int number, destination, max;
int *position;
X{
int i, j;
position[number] = destination;
X/* Display set */
X
printf("\n");
for(i = 1; i < 4; i++) {
X	printf("%d\t", i);
X	for(j = max; j > 0; j--) {
X		if (position[j] == i) {
X			printf("%d ", j);
X			}
X		}
X	printf("\n");
X	}
X}
X
void hanoi(original, destination, free, number_of_disks, position, max)
int original, destination, free, number_of_disks, max;
int *position;
X{
if (number_of_disks == 1) {
X	mvdisk(1, destination, position, max);
X	return;
X	}
X
hanoi(original, free, destination, number_of_disks - 1, position, max);
X
mvdisk(number_of_disks, destination, position, max);
X
hanoi(free, destination, original, number_of_disks - 1, position, max);
X
return;
X}
X
init(position, max)
int *position;
int max;
X{
int i;
for(i = 1; i < (max + 1); i++) {
X	position[i] = 1;
X	}
X}
X
int main(argc, argv)
int argc;
char **argv;
X
X{
int *position;
int max;
int number;
if (argc != 2) {
X	printf("Usage: %s <number of disks>\n", argv[0]);
X	exit(1);
X	}
number = atoi(argv[1]);
X
if (number < 1) {
X	puts("Argument not appropriate!");
X	exit(1);
X	}
position = malloc(number);
max = number;
init(position, max);
X
hanoi(1, 2, 3, number, position, max);
X}
X
X
END_OF_FILE
if test 1532 -ne `wc -c <'hanoimod.c'`; then
    echo shar: \"'hanoimod.c'\" unpacked with wrong size!
fi
# end of 'hanoimod.c'
fi
echo shar: End of shell archive.
exit 0

-- 
zane at ddsw1.MCS.COM


exit 0 # Just in case...
-- 
Kent Landfield                   INTERNET: kent at sparky.IMD.Sterling.COM
Sterling Software, IMD           UUCP:     uunet!sparky!kent
Phone:    (402) 291-8300         FAX:      (402) 291-4362
Please send comp.sources.misc-related mail to kent at uunet.uu.net.