gogleditor.blogg.se

Note that it will be most efficient to move the kth disk directly from pole A to pole C. Since our algorithm needs the least number of moves to solve for k -1 disks, we will assume that moving the top k -1 disks takes T k-1 moves. To solve the game with k disks, the k th disk must be moved at some point, and moving it requires the top k -1 disks to be on the pole that is not the starting or ending pole. Assume that our algorithm takes the least number of moves to solve for k -1 disks for k > 1, so T k-1 is minimal. The base case ( T 1 = 1) is satisfied because there is no way to solve the game without moving any disks. We will now show by induction that our algorithm uses the least number of moves. Image 2: After taking 1 step to move the k th disk onto Pole C, all that is left to do is move the k -1 disks onto Pole C. You can play the game Towers of Hanoi right here! This applet will help you understand how the game works. Given that this is about 58.5 times the life span of the Sun, the legend probably overestimates the amount of time we have until the world ends (unless we can survive without the Sun and the Earth). If they were to move one disk per second, then they would need 18,446,744,073,709,551,615 seconds, or 584.54 billion years, to complete the game. We can see the effects of this exponential relationship in the legend about the priests, who had to move 64 disks from one pole to the other. As it turns out, this relationship is exponential (see A More Mathematical Section for details). To fully understand the game's legend, one must understand the relationship between the number of disks and the number of moves. The game is solvable and has a shortest solution (fewest moves) for any number of disks.

Each disk must be placed on a larger disk.Each move consists of moving the top disk of one pole onto the top of another pole.Only one disk may be moved at one time.Goal: Move all k disks from the starting pole (typically the leftmost) to the specified end pole (typically the rightmost), following these rules: The standard game begins with 3 poles, one of which (the starting pole) has some natural number, k, disks placed around it in increasing size from top to bottom, while the other poles start out empty.