Analysis The above procedure can be represented via the following recurrence relation, where T(n) represents the number of moves required in order to solve the puzzle for n disks: T(n) = 2 * T(n-1) + 1, The initial condition is T(1) = 1, since one disk can be transferred from peg A to C, according to the rules of the puzzle in 1 move. The recursion continues in this fashion, for the right subtree, until all disks are on peg C. The point in time depicted therefore, is when the 2 smallest disks are on peg B, while the largest disk (disk #3) is on the target peg C. In the tree above, we notice that the edges are solid lines on the left half of the tree, and dotted in the right half of the tree.
#Hanoi towers big oh proof by induction code
In the code above, this point in time occurs during the function call, when the node s movement is recorded to the console.
The transition occurs after, for any node k, k s leftmost children have all been visited, but prior to any of k s rightmost children are visited. move 2 from A to B move 3 from A to C move 2 from B to C move 1 from A to C move 1 from C to B move 1 from B to A move 1 from A to C Each node in the tree represents a transition from for a single disk, from an initial state (peg) to a new state. Graphically, this tree with N=3, is shown in the picture below:ģ McCann 3 (of 9) Recursion Tree for N = 3 Number of Moves : 3 1 move (move disk 3 from A to C) moves moves. Since a node is only processed (printed to console) after it s left child, the tree ends up being traversed in an In-Order, Depth First manner. public class Main hanoi(n-1, from, to, temp) ("Moving disc " + n + " from " + from + " to " + to) hanoi(n-1, temp, from, to) #output: Moving disc 1 from A to C Moving disc 2 from A to B Moving disc 1 from C to B Moving disc 3 from A to C Moving disc 1 from B to A Moving disc 2 from B to C Moving disc 1 from A to C As the procedure above is recursive, the resulting execution of the program results in the traversal of a recursion tree. Note: This program assumes that disks start on peg A, with the target being peg C.
Move N-1 disks from r to d (using f as an intermediary peg) This procedure is shown in Java below, along with output generated when N = 3 disks. Move the top N-1 disks from peg f to r (using d as an intermediary peg) 2.
Recursively, this can be described by a procedure (Note: the starting peg is initially f (from), and the target is d (destination), lastly the auxiliary is r ): 1. Step 2, move another disk legally (there will only be one possibility).Ģ McCann 2 (of 9) Step 3, Repeat both steps until all disks have been moved to their final location. Step 1, move the smallest disk to the peg it has not recently come from (or if it s the very first move, move the smallest disk to the non-target peg if there are an even number of disks, otherwise, move it to the target peg). As we ll describe briefly in the following Analysis section, this algorithm is in fact an optimal solution, in that it solves the problem in the absolute minimal number of moves.
Solution for solving 3 peg Tower Of Hanoi An algorithm that solves the Tower of Hanoi problem is shown below. 2.) A disk can only be moved if it is the upper most disk on a peg, and it can only be placed on a destination peg, if it is smaller than the topmost disk currently on the destination peg. The goal of the puzzle is to move all the disks from a source peg, to a destination peg, with a minimal number of moves, without violating the following rules: 1.) Only one disk can be moved at a time. The puzzle starts with the disks neatly stacked in order of size on one peg, the smallest at the top, thus making a conical shape. The puzzle consists of three pegs, and a number of disks of different sizes which can slide onto any peg. Tower of Hanoi The Tower of Hanoi puzzle was invented in 1883 by a French mathematician named Edouard Lucas. Then I will look at a very similar problem, called the Reeve s Puzzle, and it s algorithm to see if it can be shown to be optimal as well. 1 McCann 1 (of 9) William McCann Professor Langston Discrete Mathematics AugTower Of Hanoi & Reve Puzzles Abstract In this paper I will describe the Tower Of Hanoi puzzle along with an algorithm proven to be an optimal solution.
0 kommentar(er)
