Question

Desbribe tower of Hanoi problem, provide an algorithim for it and analyze the time complexity of your algorithim.

(only attempt if you can solve thank you)

Answer 1

Tower of hanoi is a mathematical puzzle which consists of three rods and disks. Initially all the disks are located at first rod , our task is to move the disks to the last rod with  help of auxiliary rod by following certain rules:-

(i) One disk can be moved at a time.

(ii) Only top disk can be moved.

(iii) Larger disk can't sit on smaller disk.

Suppose we have 2 disks. we first move the smaller top disk to the auxiliarly peg. Move the bigger disk to destination and then finally move smaller peg which was on auxiliary rod to destination rod.

1 − Move m-1 disks from source to aux

2 − Move m^th disk from source to dest

3 − Move m-1 disks from aux to dest

Algorithm:-

START
Function Hanoi(disk, src, dest, auxil)

   IF disk == 1, THEN
      move disk from src to dest             
   ELSE
      Hanoi(disk - 1, src, auxil, dest)     
      move disk from src to dest          
      Hanoi(disk - 1, auxil, dest, src)     
   END IF
   
END Function
STOP

Time complexity for recursive tower of hanoi approach is exponential and it is O(2ⁿ).

DON'T FORGET TO HIT LIKE.

THANKS BY HEART.