Sunday, August 12, 2012

Hanoi tower in C++

Here I'm sending a recursive solution for solving Hanoi tower problem with 3 columns and n disks.
Columns are in following order :

    ||                ||             ||
    ||                ||             ||
    ||                ||             ||
    ||                ||             ||
====         ====      ====
 c_from         c_other         c_to

The problem is moving n disks from column c_from to column c_to ( we can't put bigger disks over smaller disks in a column )
Solution is :
1- moving n-1 disks from c_from to c_other
2- moving last disk from c_from to c_to
3- moving n-1 disks from c_other to c_to
.
here is simple code in C++ to solve the problem:

class HanoiTower
{
 
private :
 int N;
 stack<int> towers[3];
public:
 enum TOWERS
 {
  A=0,
  B=1,
  C=2
 };
 HanoiTower(int pN)
 {
  N=pN;
  for(int i=N-1;i>=0;i--)
   towers[A].Push(i);
 }
 void MoveRec(int pN,TOWERS tFrom,TOWERS tTo)
 { 
  if(pN==0)
  {
   int disk=towers[tFrom].Top();
   towers[tFrom].Pop();
   towers[tTo].Push(disk);
   cout <<" move "<<disk<<" from "<<tFrom<< " to "<< tTo<<endl;
   //cout <<disk+1<<tFrom+1<<tTo+1<<endl;
   return;
  }
  TOWERS other=(TOWERS)(3-tFrom-tTo);
  MoveRec(pN-1,tFrom,other);
  MoveRec(0,tFrom,tTo);
  MoveRec(pN-1,other,tTo);
 }
};

// usage :
HanoiTower hn(15);
hn.MoveRec(14,HanoiTower::TOWERS::A,HanoiTower::TOWERS::C);

1 comment :

Sunday, August 12, 2012

Hanoi tower in C++

Here I'm sending a recursive solution for solving Hanoi tower problem with 3 columns and n disks.
Columns are in following order :

    ||                ||             ||
    ||                ||             ||
    ||                ||             ||
    ||                ||             ||
====         ====      ====
 c_from         c_other         c_to

The problem is moving n disks from column c_from to column c_to ( we can't put bigger disks over smaller disks in a column )
Solution is :
1- moving n-1 disks from c_from to c_other
2- moving last disk from c_from to c_to
3- moving n-1 disks from c_other to c_to
.
here is simple code in C++ to solve the problem:

class HanoiTower
{
 
private :
 int N;
 stack<int> towers[3];
public:
 enum TOWERS
 {
  A=0,
  B=1,
  C=2
 };
 HanoiTower(int pN)
 {
  N=pN;
  for(int i=N-1;i>=0;i--)
   towers[A].Push(i);
 }
 void MoveRec(int pN,TOWERS tFrom,TOWERS tTo)
 { 
  if(pN==0)
  {
   int disk=towers[tFrom].Top();
   towers[tFrom].Pop();
   towers[tTo].Push(disk);
   cout <<" move "<<disk<<" from "<<tFrom<< " to "<< tTo<<endl;
   //cout <<disk+1<<tFrom+1<<tTo+1<<endl;
   return;
  }
  TOWERS other=(TOWERS)(3-tFrom-tTo);
  MoveRec(pN-1,tFrom,other);
  MoveRec(0,tFrom,tTo);
  MoveRec(pN-1,other,tTo);
 }
};

// usage :
HanoiTower hn(15);
hn.MoveRec(14,HanoiTower::TOWERS::A,HanoiTower::TOWERS::C);

1 comment :