![]() Now we have exactly plate on A and (N-1) plates on B. In the last step, we move the whole remaining tower to C via A. Because we are not really moving anything physically (not even data), let's just add a line for our mental node: (println 'Move 'disk 'from 'the A 'to 'the B 'pole) Now we only need to move one plate from A to B. We express it in PicoLisp by "moving" N-1 plates from A to B via C. Then we model the overall procedure as recursion of small, repetitive tasks:įirst we move the tower on pole A to pole B, except for the lowest, largest plate. In our case, the base case is that the number of plates need to be larger than 0, otherwise we cannot move anything: (de move (N A B C) First of all, a recursive function always needs an exit condition: the base case. The main idea of recursion is that a large problem can be split up into repetition of smaller problems that are easier to solve. Let's define a function move which has four parameters: We will discuss a recursive functional and logical algorithm. No disk may be placed on top of a disk that is smaller than it.įor example, this is how a solution for four disks may look like:.Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod. ![]() These are the "immutable rules of Brahma": According to the legend, when the last move of the puzzle is completed, the world will end. ![]() Acting out the command of an ancient prophecy, Brahmin priests have been moving these disks in accordance with the immutable rules of Brahma since that time. Once there was an Indian temple in Kashi Vishwanath containing a large room with three time-worn posts in it, surrounded by 64 golden disks. This is the story (or one of many versions): The "Towers of Hanoi" riddle was introduced to the West by the French mathematician Edouard Lucas in 1883. We will show two ways to solve this, one using functional programming purely in PicoLisp, and one using logical programming with help of Pilog. And then put all other (n-1) disks onto it.Today we will talk about a very famous recursive algorithm: The Towers of Hanoi riddle. Similarly if we will have n number of disk then our aim is to move bottom which is disk n from source to destination.
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |