code:
#include<stdio.h>
void toh(int n,int source,int aux,int dest)
{
if(n==1){
//just pick and place
printf("move the disk from tower no: %d to tower no: %d\n",source,dest);
return;
}
//move all n-1 disk to aux
toh(n-1,source,dest,aux);
toh(1,source,aux,dest);
toh(n-1,aux,source,dest);
}
int main(){
toh(3,1,2,3);
return 0;
}
output:
move the disk from tower no: 1 to tower no: 3 move the disk from tower no: 1 to tower no: 2 move the disk from tower no: 3 to tower no: 2 move the disk from tower no: 1 to tower no: 3 move the disk from tower no: 2 to tower no: 1 move the disk from tower no: 2 to tower no: 3 move the disk from tower no: 1 to tower no: 3
Pseudocode:
START
Procedure Hanoi(disk, source, dest, aux)
IF disk == 0, THEN
move disk from source to dest
ELSE
Hanoi(disk - 1, source, aux, dest) // Step 1
move disk from source to dest // Step 2
Hanoi(disk - 1, aux, dest, source) // Step 3
END IF
END Procedure
STOP
Formula: 2^n-1
https://en.wikipedia.org/wiki/Tower_of_Hanoi
