![]() ![]() This recurrence equation can compute for any value of n. Hence, transferring n disks requires 2T n-1 + 1 moves: Move T n-1 disks to another peg, transfer the largest disk, then transfer T n-1 disks back onto the large one. ![]() This process can be quite easily generalized. First get the smallest two disks off the largest disk (requiring T 2 moves), then transfer the largest disk to the other peg (requiring one move) and lastly transfer the two smaller disks back onto the larger one (requiring another T 2 moves). Looking more closely at how to solve for three disks, gives some clues on how to solve on a larger scale. Thus, for the small values of n we can state: T 0=0, T 1=1 and T 2=3. The first step to solving this problem is to establish appropriate notation: T n will be the minimum number of moves required to transfer n disks, following Lucas’s rules. This is part of the reason I find this problem so interesting it is a great example of generalizing to spot patterns and recurrences consequently, it serves as a useful introduction to the mathematics of computer science and algorithms. ![]() Instead of focusing on how many moves it will specifically take for the Tower of Hanoi’s 8 disks or the tower of Brahma’s 64 disks – generalization helps, as it allows you to scale down the problem. One might be confused at first, it’s not immediately obvious that the puzzle has a solution, just move the tower from one peg to another in accordance to the rules, what’s the challenge? Well after a small go at the puzzle or with a little thought, the question arises: what is the best way to do this? What’s the smallest number of moves required to solve the puzzle for n disks? Luckily for people trying to solve the puzzle, the tower of Hanoi is a little smaller than the Tower of Brahma, involving only 8 disks instead of 64. ![]() This is how you solve the Tower of Hanoi using recursion.This grand story in fact accompanies a toy puzzle, the Tower of Hanoi, invented by Edouard Lucas, a French mathematician in 1883. The formula to calculate the number of steps for n disks is : (2^n)-1 The output for n=5 is : Take disk 1 from rod A to rod C You can run the code for any number of disks. We can understand the process using the following illustration. The output for the code is: Take disk 1 from rod A to rod C The base case in our code is when we only have one disk. Let’s begin with understanding the two main parts of the code to solve the Tower of Hanoi problem. Implementing the Solution to Tower of Hanoi in Java In the function we write, we will print the movement of the disks. However, we can use this to create a function that does it recursively. Of course, you can’t do it like this because of the constraints. Take the disk number 1 and 2 to tower B.To get the three disks over to the final tower you need to : We solve this question using simple recursion. Let’s name the towers as A,B,C and the disks as 1,2,3. Theoretical Solution to the Tower of Hanoi Problem Since you can only move one disk at a time, the disk you move will have to be at the top of its tower. To do this you have an extra tower, it is known as helper/auxiliary tower. You can only move one disk at a time and never place a smaller disk over a larger disk. So you need to move all the disks from the first tower over to the last. A larger disk can not be placed on a smaller disk. While moving the disks, certain rules must be followed. Problem Statement Move all the disks stacked on the first tower over to the last tower using a helper tower in the middle. It is associated with a legend of a Hindu temple where the puzzle was supposedly used to increase the mental discipline of young priests. Tower of Hanoi Default Setupįun fact : This game was invented by a French mathematician Édouard Lucas in the 19th century. The disks are stacked in such a way that a disk is always over a disk bigger than itself. Initially all the disks are stacked on the first tower. The disks can be moved from one peg to another. The problem setup consists of three rods/pegs and n disks. The Tower of Hanoi is a classic problem in the world of programming. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |