zane@ddsw1.mcs.com (Sameer Parekh) (02/16/91)
Submitted-by: Sameer Parekh <zane@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@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@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@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@ddsw1.MCS.COM
exit 0 # Just in case...
--
Kent Landfield INTERNET: kent@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@uunet.uu.net.