![]() To write an algorithm for Tower of Hanoi, first we need to learn how to solve this problem with lesser amount of disks, say → 1 or 2. This presentation shows that a puzzle with 3 disks has taken 2 3 - 1 = 7 steps. Tower of Hanoi puzzle with n disks can be solved in minimum 2 n−1 steps. No large disk can sit over a small disk.įollowing is an animated representation of solving a Tower of Hanoi puzzle with three disks.Only one disk can be moved among the towers at any given time.A few rules to be followed for Tower of Hanoi are − The mission is to move all the disks to some another tower without violating the sequence of arrangement. There are other variations of the puzzle where the number of disks increase, but the tower count remains the same. the smaller one sits over the larger one. These rings are of different sizes and stacked upon in an ascending order, i.e. The space complexity is O(N) since, for each recursion, the disks take up N – 1 recursive stack space.Tower of Hanoi, is a mathematical puzzle which consists of three towers (pegs) and more than one rings is as depicted − What is the space complexity of the Tower of Hanoi? The minimum moves required is 2^N – 1 to move all disks from Source rod A to destination rod B, while following the rules. What are the minimum moves to solve the Tower of Hanoi problem? Space Complexity: O(N), as the disks, take up the recursive stack space. Time Complexity: O(2^N) where N is the number of disks. TowerOfHanoi(n-1, aux_rod, to_rod, from_rod) Print("Move disk",n,"from rod",from_rod,"to rod",to_rod) TowerOfHanoi(n-1, from_rod, aux_rod, to_rod) Print("Move disk 1 from rod",from_rod,"to rod",to_rod) } Python Code for Recursive Approach def TowerOfHanoi(n, from_rod, to_rod, aux_rod): } Java Code for Recursive Approach static void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) TowerOfHanoi(n - 1, aux_rod, to_rod, from_rod) TowerOfHanoi(n - 1, from_rod, aux_rod, to_rod) Ĭout << "Move disk " << n << " from rod " << from_rod << Repeat the above steps until it reaches the base case.Ĭ++ Code for Recursive Approach void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)Ĭout ![]()
0 Comments
Leave a Reply. |