/* The Tower of Hanoi (also called the Tower of Brahma or Lucas's Tower and sometimes pluralized) ís a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: 1.Only one disk can be moved at a time. 2.Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack 3.No disk may be placed on top of a smaller disk */ #include #include #include #include #include #include #include using namespace std; // source rod stack A; // middle rod stack B; // target rod stack C; void printStack(stack s); void showAll(); void move(int n, stack *source, stack *target, stack *bridge); int main() { int discs; char inputDiscs; cout << "The number of discs: "; cin >> discs; // if input is text or 0, it's will set the default value of discs to 3 if(discs == 0) { discs = 3; } cout << discs << endl << "========================================" << endl; for (int i=discs; i > 0; --i) A.push(i); showAll(); move(A.size(), &A, &C, &B); cout << "Number of moves: " << pow(2, discs) - 1; return 0; } // move disc using recursion void move(int n, stack *source, stack *target, stack *bridge) { if(n > 0) { // move n - 1 disks from source to bridge, so they are out of the way move(n - 1, source, bridge, target); // move the nth disk from source to target target->push(source->top()); source->pop(); // Display our progress showAll(); // move the n - 1 disks that we left on bridge onto target move(n - 1, bridge, target, source); } } // display rods void showAll() { printStack(A); printStack(B); printStack(C); cout << "_________________"<< endl; } // extract value from stack void printStack(stack s) { std::ostringstream oss; while (!s.empty()) { oss << ',' << s.top(); s.pop(); } string str = oss.str(); reverse(str.begin(), str.end()); cout << '[' << str.substr(0, str.size() - 1) << ']' << endl; }

Tower of Hanoi algorithm (clear view)