Iterative vs. Recursive Towers of Hanoi Solution The tower of Hanoi (commonly al
ID: 3562184 • Letter: I
Question
Iterative vs. Recursive Towers of Hanoi Solution The tower of Hanoi (commonly also known as the "towers of Hanoi"), is a puzzle invented by E. Lucas in 1883. Given a stack of n disks arranged from largest on the bottom to smallest on top placed on a rod, together with two empty rods, the towers of Hanoi puzzle asks for the minimum number of moves required to move the stack from one rod to another, where moves are allowed only if they place smaller disks on top of larger disks.
Task 1. Make an algorithm to iteratively solve the problem
Task 2. Convert the algorithm to a C program
Task 3. Make an algorithm to recursively solve the problem
Task 4. Convert the recursive algorithm to a C program
Explanation / Answer
/*Task 1:an algorithm to iteratively solve the problem */
GET NUMBER OF DISKS AS n
WHILE x BETWEEN 1 INCLUSIVE AND 1 LEFT-SHIFTED BY n BITS
SUBTRACT 1 FROM n, DIVIDE BY 3 AND TAKE THE REMAINDER AS A
OR x WITH x-1, ADD 1 TO THAT, DIVIDE BY 3 AND TAKE THE REMAINDER AS B
PRINT "MOVE FROM TOWER " A " TO TOWER " B
ADD 1 TO x
1 LEFT SHIFTED BY n BITS is basically 2 to the power of n, 16 in the case of 4 disks.
/*Task 2:C program */
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n, x;
printf( "How many disks? " );
scanf( "%d", &n );
printf(" ");
for (x=1; x < (1 << n); x++)
printf( "move from tower %i to tower %i. ",
(x&x-1)%3, ((x|x-1)+1)%3 );
return 0;
}
/*Task 3:an algorithm to recursively solve the problem */
1.Move the top n-1 disks from Source to Auxilary tower.
2.Move the nth disk from Source to Desination tower.
3.Move the n-1 disks from Auxilary tower to Desination tower.
4 Transferring the top n-1 disks from Source to Auxilary tower can again be thought as a fress
problem and can be solved in the same manner.once we solve Toweer of hanoi with three disk ,we
can solve it with any number of disks with the above algorithm.
*Task 4: C program */
#include<stdio.h>
void TowerofHanoi(int n,char frompeg,char topeg,char auxpeg)
{
if(n==1)
{
printf("Move disk 1 from peg %c to peg %c",frompeg,topeg);
return;
}
else
{
TowerofHanoi(n-1,frompeg,auxpeg,topeg);
printf("Move disk %d from peg %c to peg %c",n,frompeg,topeg);
TowerofHanoi(n-1,auxpeg,topeg,frompeg);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.