C++ (Towers of Hanoi) In this chapter, you studied functions that can be easily
ID: 3665915 • Letter: C
Question
C++
(Towers of Hanoi) In this chapter, you studied functions that can be easily implemented both recursively and iteratively. In this exercise, we present a problem whose recursive solution demonstrates the elegance of recursion, and whose iterative solution may not be as apparent. The Towers of Hanoi is one of the most famous classic problems every budding computer scientist must grapple with. Legend has it that in a temple in the Far East, priests are attempting to move a stack of golden disks from one diamond peg to another (Fig. 34). The initial stack has 64 disks threaded onto one peg and arranged from bottom to top by decreasing size. The priests are attempting to move the stack from one peg to another under the constraints that exactly one disk is moved at a time and at no time may a larger disk be placed above a smaller disk. Three pegs are provided, one being used for temporarily holding disks. Supposedly, the world will end when the priests complete their task, so there is little incentive for us to facilitate their efforts. Let's assume that the priests are attempting to move the disks from peg 1 to peg 3. We wish to develop an algorithm that prints the precise sequence of peg-to-peg disk transfers. If we were to approach this problem with conventional methods, we would rapidly find our selves hopelessly knotted up in managing the disks. Instead, attacking this problem with recursion in mind allows the steps to be simple. Moving n disks can be viewed in terms of moving only n - 1 disks (hence, the recursion), as follows: Move n - 1 disks from peg 1 to peg 2, using peg 3 as a temporary holding area. b) Move the last disk (the largest) from peg 1 to peg3 c) Move the n - 1 disks from peg 2 to peg 3, using peg a) as a temporary holding area.Explanation / Answer
#include <iostream>
using namespace std;
/*
with recursion. The setup of Hanoi is simple. We have three pegs. On each of these pegs is a series of disks decreasing in size from the bottom of the peg to the top of the peg. The goal is to move
all these disks to another peg following these rules:
-Only one disk can be moved at a time.
-Only the top most disk of any given peg can be moved to another peg.
-A larger disk cannot be placed ontop a smaller disk.
The simplest way of doing this is via Divide and Conquer.
The code is simple, but keeping track of what is going on may cause your brain to have a stack-overflow.
Params:
diskSize refers to the maximum number of disks we wish to move. If we have 5 disks and we wish
to move all five disks to another peg then this value should be 5.
5 = largest disk and 0 = smallest disk.
source is the peg where the disks currently exist.
dest is the peg we want the disks to be moved to.
spare is the peg that temporally stores pegs. This is necessary in order for us to shuffle disks
around without violating the rules.
*/
void hanoi(int diskSize, int source, int dest, int spare)
{
//This is our standard termination case. We get to here when we are operating on the
//smallest possible disk.
if(diskSize == 0)
{
std::cout << "Move disk " << diskSize << " from peg " << source << " to peg " << dest << endl;
}
else
{
//Move all disks smaller than this one over to the spare.
//So if diskSize is 5, we move 4 disks to the spare. This leaves us with 1 disk
//on the source peg.
//Note the placement of the params.
//We are now using the dest peg as the spare peg. This causes each recursion to ping-pong
//the spare and dest pegs.
hanoi(diskSize - 1, source, spare, dest);
//Move the remaining disk to the destination peg.
std::cout << "Move disk " << diskSize << " from peg " << source << " to peg " << dest << endl;
//Move the disks we just moved to the spare back over to the dest peg.
hanoi(diskSize - 1, spare, dest, source);
}
}
int main()
{
//Move all 3 disks from peg 0 to peg 1 using peg 2 as a temporary.
hanoi(2, 0, 1, 2);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.