What a c plus plus program that solve the tower of hanoi problem of n disk?

Answer 1

#include<iostream>

#include<string>

#include<vector>

#include<sstream>

using namespace std; // For std::cout and std::endl

// Each rod in the tower has a variable number of rings.

typedef vector<size_t> Rod;

// Displays the tower.

void display(Rod tower[], size_t move=0)

{

if(!move)

cout<<"Initial Position";

else

cout<<"Move "<<move;

cout<<":\n"<<endl;

static const char label[]="ABC";

for(size_t rod=0; rod<3; ++rod)

{

cout<<label[rod]<<":";

for(size_t ring=0; ring<tower[rod].size(); ++ring)

cout<<" "<<tower[rod][ring];

cout<<endl;

}

cout<<endl;

}

int main()

{

cout<<"Tower of Hannoi\n===============\n"<<endl;

size_t rings=1;

do

{

if( rings<1 rings>9 )

cout<<"You must enter a value in the range 1..9.\n"<<endl;

cout<<"Enter the no. of rings (1..9): ";

string input;

getline(cin, input);

stringstream(input)>>rings;

cout<<endl;

}while(rings<1 rings>9);

// Instantiate the three towers.

Rod tower[3];

// Push all the rings onto the 1st tower (largest to smallest)

// and display the initial position.

for(size_t ring=0; ring<rings; ++ring)

tower[0].push_back(rings-ring);

display(tower);

// Determine the minimum no. of moves required

// (2 raised to the power of rings, minus 1).

size_t moves=(1<<rings)-1;

// Determine if the number of rings is odd or even.

size_t odd=rings&1;

// Begin moving rings...

size_t move=0;

while(move<moves)

{

// Determine which 2 of the 3 rods to compare.

size_t rod_index1=0, rod_index2=odd?1:2;

switch(move%3)

{

case(0): rod_index2=odd?2:1; break;

case(2): rod_index1=odd?2:1; break;

}

// Reference the two rods.

Rod& rod1=tower[rod_index1];

Rod& rod2=tower[rod_index2];

// Obtain the top-most ring sizes (0 if rod is empty).

size_t ring1=rod1.size()?*rod1.rbegin():0;

size_t ring2=rod2.size()?*rod2.rbegin():0;

// Invariant: ring1 + ring2 > 0.

// Move the smallest ring to the other rod.

if(!ring2 (ring1 && ring1<ring2))

{

rod1.pop_back();

rod2.push_back(ring1);

}

else

{

rod2.pop_back();

rod1.push_back(ring2);

}

// Display the result of the move.

display(tower, ++move);

}

// Finished!

cout<<"Complete in "<<moves<<" moves!\n"<<endl;

}