cracknut
Reputation: 61
Implementation of Tower Of Hanoi - iterative procedure
I have been working last night on implementing Tower of Hanoi without using recursion. I have found an algorithm on Wikipedia about the same topic on the wiki page wiki for TOH. I have implemented it, it's working fine (for odd numbers :for now). But I am not happy with the code, its kinda bulky, and hence I want to modify it in a way so that actual Lines of code will reduce with the same functionality and the algorithm in mind.
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
display(int *A, int *B, int *C, int atop , int btop ,int ctop)
{
int i;
if(A[0]==0)
printf("\nEmpty A");
else
{
printf("\nA Stack :\n");
for (i=atop; i>=1; i--)
{
printf(" %d\n",A[i]);
}
}
if(B[0]==0)
printf("\nEmpty B\n");
else
{
printf("\nB Stack: \n");
for (i=btop; i>=1; i--)
{
printf(" %d\n",B[i]);
}
}
if(C[0]==0)
printf("\nEmpty C\n");
else
{
printf("\nC Stack: \n");
for (i=ctop; i>=1; i--)
{
printf(" %d\n",C[i]);
}
}
}
int main()
{
int step=0;
int n,i,*A,*B,*C,atop,btop,ctop,count=0;
int max=1;
printf("\nInput # disks");
scanf("%d",&n);
for(i=0; i<n; i++)
{
max*=2;
}
max=max-1;
printf("\n Max is :%d",max);
A= (int *)malloc(sizeof(int)*(n+1));
B= (int *)malloc(sizeof(int)*(n+1));
C= (int *)malloc(sizeof(int)*(n+1));
A[0]=B[0]=C[0]=0;
atop=btop=ctop=0;
for(i=n; i>0; i--)
{
atop++;
A[0]++;
A[atop]=i;
B[atop]=0;
C[atop]=0;
}
display(A,B,C,atop,btop,ctop);
do
{
count+=1;
step=(step%3)+1;
switch(step)
{
case 1://move between pegs A and C
printf("\n%d count:",count);
if(count%2 ==1)//move of disk 1
{
if(A[atop]==1)
{
ctop++;
C[ctop]=A[atop];
A[atop]=0;
atop--;
C[0]++;
A[0]--;
printf("\nDisk %d: A->C",C[ctop]);
} //i is on A
else if(C[ctop]==1)//1 is on b
{
atop++;
A[atop]=C[ctop];
C[ctop]=0;
ctop--;
A[0]++;
C[0]--;
printf("\nDisk %d: C->A",A[atop]);
}
}//Movement of disk #1
else if(count %2 ==0)
{
if(ctop !=0 && A[atop]>C[ctop])
{
//C[0]--;
atop++;
A[atop]=C[ctop];
C[ctop]=0;
ctop--;
C[0]--;
A[0]++;
printf("\nDisk %d: C->A",A[atop]);
}
else if (ctop ==0)
{
ctop++;
C[ctop]=A[atop];
A[atop]=0;
atop--;
C[0]++;
A[0]--;
printf("\n disk %d:A->C",C[ctop]);
}
else if(atop !=0 && C[ctop]>A[atop])
{
ctop++;
C[ctop]=A[atop];
A[atop]=0;
atop--;
C[0]++;
A[0]--;
printf("\nDisk %d: A->C",C[ctop]);
}
else if(atop==0)
{
atop++;
A[atop]=C[ctop];
C[ctop]=0;
ctop--;
C[0]--;
A[0]++;
printf("\nDisk %d: C->A",A[atop]);
}
}//Movement of Disk non1
break;
case 2://move between pegs A and B
printf("\n%d count:",count);
if(count%2 ==1)//move of disk 1
{
if(A[atop]==1)
{
btop++;
B[btop]=A[atop];
A[atop]=0;
atop--;
B[0]++;
A[0]--;
printf("\nDisk %d: A->B",B[btop]);
} //i is on A
else if(B[btop]==1)//1 is on b
{
atop++;
A[atop]=B[btop];
B[btop]=0;
btop--;
A[0]++;
B[0]--;
printf("\nDisk %d: B->A",A[atop]);
}
}//Movement of disk #1
else if(count %2 ==0)
{
if(btop !=0 && A[atop]>B[btop])
{
//B[0]--;
atop++;
A[atop]=B[btop];
B[btop]=0;
btop--;
B[0]--;
A[0]++;
printf("\nDisk %d: B->A",A[atop]);
}
else if (btop ==0)
{
btop++;
B[btop]=A[atop];
A[atop]=0;
atop--;
B[0]++;
A[0]--;
printf("\n disk %d:A->B",B[btop]);
}
else if(atop !=0 && B[btop]>A[atop])
{
btop++;
B[btop]=A[atop];
A[atop]=0;
atop--;
B[0]++;
A[0]--;
printf("\nDisk %d: A->B",B[btop]);
}
else if(atop==0)
{
atop++;
A[atop]=B[btop];
B[btop]=0;
btop--;
B[0]--;
A[0]++;
printf("\nDisk %d: B->A",A[atop]);
}
}//Movement of Disk non1
break;
case 3://move between pegs C and B
printf("\n%d count:",count);
if(count%2 ==1)//move of disk 1
{
if(C[ctop]==1)
{
btop++;
B[btop]=C[ctop];
C[ctop]=0;
ctop--;
B[0]++;
C[0]--;
printf("\nDisk %d: C->B",B[btop]);
} //i is on C
else if(B[btop]==1)//1 is on b
{
ctop++;
C[ctop]=B[btop];
B[btop]=0;
btop--;
C[0]++;
B[0]--;
printf("\nDisk %d: B->C",C[ctop]);
}
}//Movement of disk #1
else if(count %2 ==0)
{
if(btop !=0 && C[ctop]>B[btop])
{
//B[0]--;
ctop++;
C[ctop]=B[btop];
B[btop]=0;
btop--;
B[0]--;
C[0]++;
printf("\nDisk %d: B->C",C[ctop]);
}
else if (btop ==0)
{
btop++;
B[btop]=C[ctop];
C[ctop]=0;
ctop--;
B[0]++;
C[0]--;
printf("\n disk %d:C->B",B[btop]);
}
else if(ctop !=0 && B[btop]>C[ctop])
{
btop++;
B[btop]=C[ctop];
C[ctop]=0;
ctop--;
B[0]++;
C[0]--;
printf("\nDisk %d: C->B",B[btop]);
}
else if(ctop==0)
{
ctop++;
C[ctop]=B[btop];
B[btop]=0;
btop--;
B[0]--;
C[0]++;
printf("\nDisk %d: B->C",C[ctop]);
}
}//Movement of Disk non1
break;
default:
printf("Some Error!");
}//switch end
// display(A,B,C,atop,btop,ctop);
}
while((count <=max) && (C[0]!=n) );
printf("\n");
//display(A,B,C,atop,btop,ctop);
display(A,B,C,atop,btop,ctop);
return 0;
}
Kindly help me out.
Upvotes: 2
Views: 5851
Answers (1)
Armali
Reputation: 19375
#include<math.h>isn't needed in your program.- Block braces around a single statement aren't needed.
- A sane aggregation of code in one line yields less lines of code without harming readability (sometimes even improving it).
- By extracting repeated similar code sections into a new, parameterized function we can also reduce LOC, probability of errors as well as facilitate understandability. Cf. e. g.
display_stack(),move(),movement()below. - Your program contains variables with essentially identical values: A[0] = atop, B[0] = btop, C[0] = ctop. By dropping atop, btop and ctop we can simplify function calls and reduce LOC etc.
- If we want allocated memory (mostly) filled with zeroes, we can use
calloc().
Here's a modified version of your program.
#include<stdio.h>
#include<stdlib.h>
display_stack(int *stack, char name)
{
int i;
if (!*stack)
printf("\nEmpty %c\n", name);
else
{
printf("\n%c Stack:\n", name);
for (i = *stack; i; --i) printf(" %d\n", stack[i]);
}
}
display(int *A, int *B, int *C)
{
display_stack(A, 'A');
display_stack(B, 'B');
display_stack(C, 'C');
}
void move(int *fromstack, char fromname, int *tostack, char toname)
{
tostack[++*tostack] = fromstack[*fromstack];
fromstack[*fromstack] = 0; // actually unneeded; makes debugging easier
--*fromstack;
printf("\n disk %d:%c->%c", tostack[*tostack], fromname, toname);
}
void movement(int *X, char Xnm, int *Y, char Ynm, int countm2)
{
if (countm2 == 1)//move of disk 1
{
if (X[*X] == 1) move(X, Xnm, Y, Ynm); //i is on X
else
if (Y[*Y] == 1) move(Y, Ynm, X, Xnm); //1 is on Y
}//Movement of disk #1
else
if (countm2 == 0)
{
if (*Y != 0 && X[*X] > Y[*Y]) move(Y, Ynm, X, Xnm);
else
if (*Y == 0) move(X, Xnm, Y, Ynm);
else
if (*X != 0 && Y[*Y] > X[*X]) move(X, Xnm, Y, Ynm);
else
if (*X == 0) move(Y, Ynm, X, Xnm);
}//Movement of Disk non1
}
int main()
{
int step=0;
int n,i,*A,*B,*C,count=0;
int max=1;
printf("\nInput # disks");
scanf("%d",&n);
for (i=0; i<n; i++) max*=2;
max=max-1;
printf("\n Max is :%d",max);
A = calloc(1+n, sizeof *A);
B = calloc(1+n, sizeof *B);
C = calloc(1+n, sizeof *C);
for (i=n; i>0; i--) A[++*A]=i;
display(A, B, C);
do
{
count+=1;
step=(step%3)+1;
switch (step)
{
case 1://move between pegs A and C
printf("\n%d count:",count);
movement(A, 'A', C, 'C', count%2);
break;
case 2://move between pegs A and B
printf("\n%d count:",count);
movement(A, 'A', B, 'B', count%2);
break;
case 3://move between pegs C and B
printf("\n%d count:",count);
movement(C, 'C', B, 'B', count%2);
break;
default:
printf("Some Error!");
}//switch end
} while (count<=max && C[0]!=n);
printf("\n");
display(A, B, C);
return 0;
}
Upvotes: 1
Related Questions
- How Solve Iterative Method For Hanoi Problem
- Tower of Hanoi Recursion Algorithm
- Need an explanation of the recursive calls in "Towers of Hanoi"
- Why does my tower of hanoi algorithm not work?
- Towers of Hanoi solution issue
- unclear with this tower of hanoi recursive call
- recursive solution for tower of hanoi
- I don't understand Hanoi algorithm
- Cannot make sense of my lecturers recursive algorithm for the Towers of Hanoi
- linear towers of hanoi