Algorithms and Data Structures in C part 7

The Tower of Hanoi problem is illustrated in Figure 2.1. The problem is to move n discs (in this case, three) from the first peg, A, to the third peg, C. The middle peg, B, may be used to store discs during the transfer.
Nội dung trích xuất từ tài liệu:
Algorithms and Data Structures in C part 7 Previous TableofContents Next Copyright © CRC Press LLC Algorithms and Data Structures in C++ by Alan Parker CRC Press, CRC Press LLC ISBN: 0849371716 Pub Date: 08/01/93 Previous TableofContents Next 2.3.4TowerofHanoiThe Tower of Hanoi problem is illustrated in Figure 2.1. The problem is to move n discs (in thiscase, three) from the first peg, A, to the third peg, C. The middle peg, B, may be used to storediscs during the transfer. The discs have to be moved under the following condition: at no timemay a disc on a peg have a wider disc above it on the same peg. As long as the condition is metall three pegs may be used to complete the transfer. For example the problem may be solved forthe case of three by the following move sequence:where the ordered pair, (x, y), indicates to take a disk from peg x and place it on peg y.Figure 2.1 Tower of Hanoi ProblemThe problem admits a nice recursive solution. The problem is solved in terms of n by noting thatto move n discs from A to C one can move n - 1 discs from A to B move the remaining disc fromA to C and then move the n - 1 discs from B to C. This results in the relation for the number ofsteps, S (n), required for size n aswith the boundary conditionsEq. 2.25 admits a solution of the formand matching the boundary conditions in Eq. 2.26 one obtainsA growing field of interest is the visualization of algorithms. For instance, one might want toanimate the solution to the Tower of Hanoi problem. Each disc move results in a new picture inthe animation. If one is to incorporate the pictures into a document then a suitable language forits representation is PostScript.1 This format is supported by almost all word processors and as aresult is encountered frequently. A program to create the PostScript® description of the Tower ofHanoi is shown in Code List 2.6 The program creates an encapsulated postscript file shown inCode List 2.7. The word processor used to generate this book took the output of the program inCode List 2.7 and imported it to yield Figure 2.1! This program illustrates many features of C++. 1 PostScript®isatrademarkofAdobeSystemsInc. The program utilizes only a small set of the PostScript® language. This primitive subset isdescribed in Table 2.3.Table2.3PostScript®—PrimitiveSubsetCommand Description xsetgray setthegrayleveltox.x=1iswhiteandx=0isblack.Thiswillaffectthe filloperation. xyscale scaletheXdimensionbyxandscaletheYdimensionbyy. xsetlinewidth setthelinewidthtox. xymoveto startasubpathandmovetolocationxyonthepage. xyrlineto drawalinefromcurrentlocation(x1,y1)to(x1+x,y1+y).Makethe endpointthecurrentlocation.Appendsthelinetothesubpath. fill closethesubpathandfilltheareaenclosed. newpath createanewpathwithnocurrentpoint. showpage displaysthepagetotheoutputdevice.The program uses a number of classes in C++ which are derived from one another. This is one ofthe most powerful concepts in object-oriented programming. The class structure is illustrated inFigure 2.2.In the figure there exists a high-level base class called the graphic context. In a typicalapplication a number of subclasses might be derived from it. In this case the graphics contextspecifies the line width, gray scale, and scale for its subsidiary objects. A derived class from thegraphics context is the object class. This class contains information about the position of theobject. This attribute is common to objects whether they are rectangles, circles, etc. A derivedclass from the object class is the rectangle class. For this class, specific information about theobject is kept which identifies it with a recta ...