![]() Some applications may have multiple views. ![]() The View outputs the model, either presenting a visual repretation, outputting information from the model, responding to signals from the Control or all of these. The Control is makes changes to the contents of the model and also passes the changing model along with other signals to the view. The Model is a structure for the data being manipulated by the program The MVC discipline strives to find separate responsibilities of a program into code modules that are independent and loosely linked with each other. ![]() And I think the problem is the difficulty in visualizing the nested context of the recursive calls. It is much better than the usual factorial example which does nothing more than use recursion to replace a simple for loop.īut students have a hard time getting it. I have tried a couple of times to teach the Hanoi puzzle as a good example of recursion. Here is a screen shot of the game in progress.Īnd here is a javascript animation. The other 99% of the program involves doing TK graphics to make it come alive. Guido's hanoi.py in the Python Demo area is a nice demonstration of this recursive process. Can't do 4 discs? Well then, move just 3. If you don't know how to move 5 discs from A to C (using B for intermediate storage), then just move 4 discs from A to B, one disk from A to C (this is really easy) and then move 4 discs from B to C. The problem is to move the discs, one at a time from peg to peg in such a way that this is always true and to finally end up with all of the discs on peg 3 in the original order. A disc is never stacked on top of a smaller disc. In the initial configuration all the discs are stacked on the first peg with the largest disc on the bottom and the smallest on top. Each disc can fit on any of 3 pegs and each peg is high enough to hold all the discs in a stack. There are a number of discs each with a hole in the center. My %tower = map1.The Tower of Hanoi is a classic game that is often emulated on computers to demonstrate recursion. Towers of Hanoi problems are good examples in that they are easy to visualize, and their relationship to sorting with stacks is obvious. If T(n) is the number of moves needed to sort n disks, your recursion gives the recurrence T(n) = 2T(n-1). If we aren't allowed to put larger disks on top of smaller disks (as in the classic example above), you need an exponential number of moves. I won't give away how to sort the disks in O(n log n) time, but here's a hint: adapt quicksort. In fact, a question on a recent algorithms Ph.D qualifying exam here at UIUC was to show that disks can be sorted in O(n log n) moves, and to also show that in fact, &Omega(n log n) moves are required in general. In this version, you are allowed to place any disk onto any other disk (no size restrictions). Re: Recursion: the Towers of Hanoi problemĪnother related fun 'n' interesting problem is to start with the disks placed randomly onto the three pegs and then try to sort them all onto one peg. You may only move one disk at a time and this disk must be the top disk on a peg.No disk may be placed on top of a smaller disk.All the disks are initially placed on the first peg (the 'A' peg).The towers are labeled 'A', 'B', and 'C'. There are n disks (1, 2, 3., n) and three towers (pegs). ![]() Fortunately, they are nowhere even close to being done. They are said to believe that when the last move of the puzzle is completed, the world will end in a clap of thunder. Monks, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the rules of the puzzle, once every day since the monastery was founded over a thousand years ago. According to this myth (uttered long before the Vietnam War), there is a Buddhist monastery at Hanoi which contains a large room with three time-worn posts in it surrounded by 21 golden discs. The puzzle is called "Towers of Hanoi" because an early popular presentation wove a fanciful legend around it. To help illustrate the power and elegance (yes, there are drawbacks as well) it provides, a classic problem known as the 'Towers of Hanoi' is often used.įor those unfamiliar with this classic, please allow me explain the history and rules. Many computer science professors eventually discuss the concept of recursion.
0 Comments
Leave a Reply. |