This is a very easy program, I have already provided the header file,
driver program and custom functions, I just need two things done for
me, I would have done them myself, but I'm really pressed for time on
stuff at work. I need this done by 11.00pm ,Wednesday 04/23/2003. Thank
you. And Please stick to the code I already have, it compiles
perfectly.
Things I want done:
1.submit the output results from execution of your program with n
=3, n=5, n=10, n=20, n=30 where n is the user input for the number of
disks. Be sure to desk-check your program results.
2.By benchmarking your program and recording the execution time for
each of the the values of n in #1 above determine the number of moves
and estimate the execution time required to run the program when n=64.
note. Do not try to run the program when n=64 because it would not
finish in a feasible time frame
you can either cut and paste these results and put them at the end of
the program or you can attach them somehow, but I need to see these 2
things.
The towers of Hanoi:
In this program you’ll write a recursive function that identifies all
the moves needed to complete the towers of Hanoi logic problem.
There are three towers T1 T2 T3 on a platform and n>0 disks (D1…….Dn)
of different diameters placed on the first tower T1. The disks are in
the order of decreasing diameter as one scans up the tower T1.Monks
were reputedly supposed to move the disks from tower T1 to tower T3
obeying the following rules
1.only one disk can be moved at a time
2. no disk can be placed on top of another disk with a smaller
diameter
3. to complete the task, the disk should be stacked on tower
T3exactly like they are on tower at1.
Write a C program that calls a recursive function and prints out a
sequence of moves and total number of moves needed to accomplish this
task for a given number of disks. The program should accept from the
user, the number of disks (ranging from 1 -100)and then call the
recursive function to print each move in sequence( if the number of
disks is less than 10), and finally print the total time elapsed,
required to complete the task.
I have already provided the header files, functions and the main
driver program all I need is:
1.submit the output results from execution of your program with n
=3, n=5, n=10, n=20, n=30 where n is the user input for the number of
disks. Be sure to desk-check your program results.
2.By benchmarking your program and recording the execution time for
each of the the values of n in #1 above determine the number of moves
and estimate the execution time required to run the program when n=64.
note. Do not try to run the program when n=64 because it would not
finish in a feasible time frame
/* Header File */
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
void hanoi(int,int,char,char,char);
void move(char,char,char);
void ddraw(void);
int peg[3][50];
int top[3]={0,0,0};
static char disc[13][26];
void InitialDiscGraph (int,int);
int n;
/* Driver program */
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
void InitialDiscGraph (int,int);
int main(void)
{
int i = 0 , j = 0 ;
InitialDiscGraph (i,j);
return 0;
}
/* main program*/
==================== Program description ==================
// This program will solve the hanoi problem and also
// draw the graph for the peg situation. The maximum
// number of discs to process is 50.
//===========================================================
#include"tower2.h"
void InitialDiscGraph (int i,int j) /* Initialize the disc graph */
{
for (i=0; i<=12; i++)
{
for (j=0; j<=11; j++)
{
if (11-j>=i)
{
disc[i][j]=' ';
disc[i][24-j]=' ';
}
else
{
disc[i][j]='*';
disc[i][24-j]='*';
}
}
disc[i][12]='|';
disc[i][25]='\0';
}
printf(" Please input the number of disc(1-12):");
scanf("%d",&n);
printf("Hanoi Tower with %d discs:\n",n);
printf("====================================================\n\n");
for (i=1; i<=n; i++) /* initialize the peg status */
{
top[0]++;
peg[0][top[0]]=n-i+1;
}
ddraw(); /* Draw the initial status */
while (n != 0)
{
hanoi(n,n,'A','B','C'); /* Do n discs */
printf(" Please input the number of disc:");
scanf("%d",&n);
printf("Hanoi Tower with %d discs:\n",n);
printf("====================================================\n\n");
/* initial top */
for (i=0; i<=2; i++)
{
top[i]=0;
}
for (i=0; i<=2; i++) /* Clean up the discs in the pegs */
{
for (j=0; j<=20; j++)
{
peg[i][j]=0;
}
}
for (i=1; i<=n; i++) /* initialize the peg status */
{
top[0]++;
peg[0][top[0]]=n-i+1;
}
if (n!=0)
ddraw(); /* Draw the initial status */
}
return ;
}
//*************************************************************
//Main function of hanoi tower program:
//It will move the disc recursively
//hanoi(n, A, B, C) =
//hanoi(n-1, A, C, B) + hanoi(1, A, B, C)
//+hanoi(n-1, B, A, C)
//*************************************************************
void hanoi(int num,int Disc_num,char beg,char aux,char tem)
{
if (num==1) /* only one disc */
{
printf("move disc %d from peg %c to %c \n",Disc_num,beg,tem);
move(beg,aux,tem); /* update the graph status */
ddraw(); /* disc status draw */
}
else
{
hanoi(num-1,Disc_num-1,beg,tem,aux); /* move n-1 disc from beg to
aux */
hanoi(1,Disc_num,beg,aux,tem);/* move 1 disc from beg to tem
*/
hanoi(num-1,Disc_num-1,aux,beg,tem);/* move n-1 disc from aux
to tem */
}
}
//************************************************************
//Move: move the discs between the pegs by updating
//the top pointer
//************************************************************
void move(char beg,char aux,char tem)
{
if (beg=='A') /* Move disc from A to B */
{
if (tem=='B')
{
top[1]++;
peg[1][top[1]]=peg[0][top[0]];
peg[0][top[0]]=0;
top[0]--;
}
else
{
top[2]++;
peg[2][top[2]]=peg[0][top[0]];
peg[0][top[0]]=0;
top[0]--;
}
}
else
{
if (beg=='B') /* Move disc from B to A */
{
if (tem=='A')
{
top[0]++;
peg[0][top[0]]=peg[1][top[1]];
peg[1][top[1]]=0;
top[1]--;
}
else /* Move disc from B to C */
{
top[2]++;
peg[2][top[2]]=peg[1][top[1]];
peg[1][top[1]]=0;
top[1]--;
}
}
else
{
if (tem=='A') /* Move disc from C to A */
{
top[0]++;
peg[0][top[0]]=peg[2][top[2]];
peg[2][top[2]]=0;
top[2]--;
}
else /* Move disc from C to B */
{
top[1]++;
peg[1][top[1]]=peg[2][top[2]];
peg[2][top[2]]=0;
top[2]--;
}
}
}
return;
}
//******************************************************************
//Draw the disc status
//******************************************************************
void ddraw(void)
{
int i = 0;
int j = 0;
int k = 0;
for (i=n; i>=1; i--)
{
printf(" ");
for (j=0; j<=2; j++)
{
for (k=0; k<=25; k++)
printf("%c",disc[peg[j][i]][k]);
printf(" ");
}
printf("\n");
}
for (i=0; i<81; i++) printf("-");
printf("\n\n\n");
return;
} |