Teaching Materials There are currently no teaching materials for this page. The faster the apes solve the game, the more intelligent they are perceived to be. In the 2011 film Rise of the Planet of the Apes, scientists test the intelligence of apes with Towers of Hanoi. Consequently, the game is often used to test intelligence. Towers of Hanoi is also a popular tool in psychological research it can test problem solving capabilities. Assuming the average computer can do 100 million operations per minute, then solving the game with 64 disks would take the computer 5845.42 years to complete. In addition, the game's exponential solution is an example of why computer scientists dislike exponential time it takes far too long to compute. The mathematical nature of the game teaches how to create recursive programs, while the simple user interface of the game (which can be made using only rectangles) introduces the basics of programming graphics. Towers of Hanoi is a popular example in introductory computer science courses because programming it is instructional but relatively simple. If the priests move 1 disk per second, then they will need:Īssuming that the Sun has a life span of 10 billion years, the time predicted by the legend is times longer than the Sun's lifespan. A Towers of Hanoi game with 64 disks will take: Now that we have the equation to determine the number of moves needed for any number of disks, we can verify the time we said was needed to complete the game in the legend. Thus we have shown the minimal algorithm for any Towers of Hanoi game with k disks requires T k = 2 k – 1 steps. We will show by induction that the explicit formula for the number of moves in this minimal algorithm is Thus the minimum number of moves required to solve for k disks assuming T k-1 is minimized is This requires transferring those k-1 disks three times (to pole C, then pole A, then back to C), whereas our method of moving the kth disk directly to pole C only requires two such transfers. The other option would be to move the other k-1 disks to pole C, move the kth disk to pole B, then move the other k-1 disks back to pole A before the kth disk can reach pole C. 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.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |