![]() Note the explicit recursion in this procedure, because MoveStack () calls itself to move a smaller stack of disks stacked on top of the disk that it is going to move. The complete definition of the procedure is as follows: MoveStack (N, Start, Spare, Goal) So, if we had a stack of three discs at location A, and wanted to move the stack to location C using location B as the “spare”, we would execute MoveStack (3, A, B, C). It will take four arguments: the number of discs in the stack to be moved, the starting location, the “spare” location, and the goal location. The recursive nature of the solution to the Towers of Hanoi is made obvious if we write a pseudocode algorithm for moving the disks. The whole approach is recursive in the sense that to move the big stack, the same procedure must first be used to move the smaller stack on top of the largest disc. “Moving the stack” is the same kind of procedure for the n discs and for the n-1 discs. To move a stack of n discs to location C, we first move the smaller stack of n-1 discs to location B. We solve the bigger problem by first solving a smaller version of the same kind of problem. A solution to the Towers of Hanoi problem points to the recursive nature of divide and conquer. ![]() In other words, divide and conquer is the explicit use of recursion to solve a problem.įor example, consider the Towers of Hanoi problem, in which a stack of different sized discs are moved from one location to another (using a third “spare” location as well) under the restrictions that only one disc is moved at a time, and a larger disc can never be placed on a smaller one. In divide and conquer, one solves a problem by first defining a subgoal that involves solving a smaller version of the same kind of problem. Divide and conquer is an approach to solving a problem that is a special case of means-ends analysis. ![]()
0 Comments
Leave a Reply.AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |