need help in assignment

Hi!Am learning C++. But have an assignment on recursion that I cannot understand. Supposed to be a short program but don't know where to start. Can someone help? Problem is as follows:

64 disks from one peg are being moved to a second peg, one peg at a time. The disks are arranged from top to bottom in increasing diameter(no two disks are the same diameter) Constraints are that one disk is moved at a time and a larger disk can never be placed on top of a smaller disk. There is a third peg for temporary storage.

We can think in terms of 3 disks and then n disks. The solution for 3 disks is the following:

move a disk from peg 1 to peg 2

move a disk from peg 1 to peg 3

move a disk from peg 2 to peg 3

move a disk from peg 1 to peg 2

move a disk from peg 3 to peg 1

move a disk from peg 3 to peg 2

move a disk from peg 1 to peg 2

Now all three disks are on peg 2 in decreasing diameter upward

Next think about the problem recursively and for moving n disks from peg 1 to peg 2(peg 3 is temporary storage:

if n is equal to 1

move a disk from peg 1 to peg 2

else

move(n-1)disks from peg 1 to peg 3(peg 2 is temp storage)

move a disk from peg 1 to peg 2

move(n-1)disks from peg 3 to peg 2(peg 1 is temp storage)

There is a check to see if there is no more recursion and, if the check fails, two recursive function calls.

Any help would be appreciated.














Comments

  • I love this puzzle.


    The classic problem is as you stated: Given n discs of decreasing radius on one of three pegs, transfer the tower to another peg one disc at a time with no larger disc placed atop a smaller one.


    Think about it this way, for a moment:


    If you wanted to transfer from peg 1 to peg 3 a tower of n discs, it'd be really easy if you had a way to transfer a tower of n-1 discs. Let's say you had a magic function (call it magic1) that transfered n-1 discs _for_ you. You could use magic1 to transfer n-1 discs from peg 1 to peg 2, and then transfer the last (nth) disc to peg 3, and then again use magic1 to transfer n-1 discs from peg 2 to peg 3. Since you only transferred the last disc by hand, and it's the largest, you didn't break the rules of the tower.


    Let's think about the above magic1 function for a moment, and how you might write it. If only you had a magic function to transport n-2 discs (let's call it magic2). Then, for the first use of magic1 (going from peg 1 to peg 2), you could use magic2 to transport n-2 discs from peg 1 to peg 3, then transport the (n-1)st disc by hand from peg 1 to peg 2, and then use magic2 to transport n-2 discs from peg 3 to peg 2. The second use of magic1 in the previous paragraph involves an identical procedure with different source and destination pegs.




    Sound familiar? The second magic function is identical to the first except for three things: The source peg, the destination peg, and the number of discs to transfer. Computer languages are just dandy for repetitious behaviour, and many pieces of code that are almost identical can often be collapsed into a more universal function.


    In this case, we'll write a function that is a recursive solution. A recursive solution is one that is defined in terms of itself, but with a different (usually smaller) case. If you can break down a problem into smaller problems that are almost identical to the original, you've probably got a good candidate for a recursive solution.


    Let's call it Hanoi.


    Almost all behaviours of Hanoi are identical except for source and destination pegs and the number of discs.


    So let's have Hanoi take three parameters.


    void Hanoi(int iSourcePeg,int iDestinationPeg,int n);


    That, of course, is just the prototype.


    Just a hint: One of the first things you should do is determine what the 'transfer' peg is (the 'scratch space' to use). It will require a quick little bit of decision making, but having a variable which is the transfer peg number will make the rest of the code easier.


    So, let's say you have no idea what two pegs will be chosen, or how many discs (but you _do_ know that the two peg numbers given to the function will be different, so you can depend on that). Can you solve the problem generally?


    We did, earlier on!


    All you have to do is transfer n-1 discs from the source to the transfer peg, and then transfer 'by hand' (saying "I'm transferring a disc from peg x to peg y now!" or something) the 'last disc' from the source peg to the destination peg, and then transfer n-1 discs from the transfer peg to the destination peg.


    You don't need to worry about transferring the n-1 discs yourself... because you already have Hanoi. This is the trick in writing recursive routines -- assume you already have it written, and use it within itself to solve a simpler problem than the one you're given. If Hanoi is given n discs to move, then Hanoi can give Hanoi n-1 discs to move.


    Well, we're not quite done. What happens when Hanoi is given 1 disc to transfer? Do we allow Hanoi to call Hanoi to transfer 0 discs? Well, if we do, we certainly can't have it transfer -1 discs. That doesn't make sense. Transferring 0 discs doesn't make a lot of sense either. What we're getting at here is that Hanoi can't use itself to solve all problems. There must be a simplest case that it can solve on its own without any help from itself.


    So, if Hanoi is given 1 disc to transfer, perhaps we just don't call Hanoi to solve 0 discs. We still transfer the one disc 'by hand', but we don't have Hanoi bother to ask itself to transfer 0 discs to the transfer peg.


    I'm not going to provide you code, because you should be able to reason it out. Recursive routines have the three following properties:


    1) Problems of all complexities have the same basic format.

    2) One or more 'simplest cases' that don't need recursion to solve. Detecting this 'simplest case' must prevent further recursion from happening, otherwise your recursion will go on forever.

    3) More complex cases, wherein they can be broken down into 'simpler cases' of a nearly identical type that the routine can solve itself.


    Hope this helps. Post if you're still confused (after trying your best).


Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories