Program name: Tower of Hanoi Program description: This program calculates the minimum number of moves required to solve a Tower of Hanoi puzzle. It also shows steps of moving to solve the puzzle.

The given program can compile but cannot link until after you defined the above three functions.

#include #include #include // for pow()

using namespace std;

/** The following functions calculate how many steps are needed for a Hanoi Tower puzzle. */ int HanoiExpessN(int n); // expressive version int HanoiRecursiveN(int n); // recursive version

/** This function will print each step of moving disks for a given size of Hanoi Tower puzzle in a recursive way.

@param n: the number of disks to be moved. @param start: the peg holding disks to be moved. @param target: the peg to which disks will be moved to. @param temp: the auxiliary peg. */ void HanoiRecursiveSteps(size_t n, string start, string temp, string target);

int main() { cout << "This program calculates the numbers of moving Tower Hanoi in both "; cout << "explicit way and recursive method. Then the moving steps will be "; cout << "shown. "; cout << "=================================================================== ";

const int upperN = 10; // upper bound int n;

cout << ">>> Calculate the Tower Hanoi expressively ... "; for (n = 0; n <= upperN; n++) cout << "Hanoi(" << n << ") = " << HanoiExpessN(n) << endl;

cout << " >>> Calculate the Tower Hanoi recursively ... "; for (n = 0; n <= upperN; n++) cout << "Hanoi(" << n << ") = " << HanoiRecursiveN(n) << " ";

cout << " >>> Show moving steps for Tower of Hanoi ... "; for (int n = 1; n <= 4; n++) { cout << " ==> Steps for " << n << " disk(s) for Tower of Hanoi: "; HanoiRecursiveSteps(n, "peg1", "peg2", "peg3"); }

cout << endl; }

/* A Sample Output

This program calculates the numbers of moving Tower Hanoi in both explicit way and recursive method. Then the moving steps will be shown. ===================================================================

>>> Calculate the Tower Hanoi expressively ... Hanoi(1) = 1 Hanoi(2) = 3 Hanoi(3) = 7 Hanoi(4) = 15 Hanoi(5) = 31 Hanoi(6) = 63 Hanoi(7) = 127 Hanoi(8) = 255 Hanoi(9) = 511 Hanoi(10) = 1023

>>> Calculate the Tower Hanoi recursively ... Hanoi(1) = 1 Hanoi(2) = 3 Hanoi(3) = 7 Hanoi(4) = 15 Hanoi(5) = 31 Hanoi(6) = 63 Hanoi(7) = 127 Hanoi(8) = 255 Hanoi(9) = 511 Hanoi(10) = 1023

>>> Show moving steps for Tower of Hanoi ...

==> Steps for 1 disk(s) for Tower of Hanoi: Disk_1: peg1 --> peg3

==> Steps for 2 disk(s) for Tower of Hanoi: Disk_1: peg1 --> peg2 Disk_2: peg1 --> peg3 Disk_1: peg2 --> peg3

==> Steps for 3 disk(s) for Tower of Hanoi: Disk_1: peg1 --> peg3 Disk_2: peg1 --> peg2 Disk_1: peg3 --> peg2 Disk_3: peg1 --> peg3 Disk_1: peg2 --> peg1 Disk_2: peg2 --> peg3 Disk_1: peg1 --> peg3

=> Steps for 4 disk(s) for Tower of Hanoi: Disk_1: peg1 --> peg2 Disk_2: peg1 --> peg3 Disk_1: peg2 --> peg3 Disk_3: peg1 --> peg2 Disk_1: peg3 --> peg1 Disk_2: peg3 --> peg2 Disk_1: peg1 --> peg2 Disk_4: peg1 --> peg3 Disk_1: peg2 --> peg3 Disk_2: peg2 --> peg1 Disk_1: peg3 --> peg1 Disk_3: peg2 --> peg3 Disk_1: peg1 --> peg2 Disk_2: peg1 --> peg3 Disk_1: peg2 --> peg3