Hanoi problem

In the classic problem of the Towers of Hanoi, you have 3 rods and N disks
of different sizes which can slide onto any tower. The puzzle starts with disks
sorted in ascending order of size from top to bottom (e.g., each disk sits on top
of an even larger one). You have the following constraints:
(A) Only one disk can be moved at a time.
(B) A disk is slid off the top of one rod onto the next rod.
(C) A disk can only be placed on top of a larger disk.
Write a program to move the disks from the first rod to the last using Stacks

记得以前毕业的时候都弄不清楚那三行递归是什么意思，今天自己写写居然写出来了，
泪飙~~

思路：
如果想从a到c移动n个盘子:
1. 需要从a到b移动n-1个盘子
2. 然后将最下边的盘子从a移动到c
3. 移动从b到c移动n-1个盘子

1. 
   
2. int GetOther(int nFrom, int nTo)
   
3. {
   
4.         assert(nFrom >= 1 && nFrom <= 3 && nTo >= 1
   
5.                 && nTo <= 3 && nFrom != nTo);
   
6. 
   
7.         return 6 - nFrom - nTo;
   
8. }
   
9. 
   
10. void mov(int nPalates, int nFrom, int nTo)
    
11. {
    
12.         assert(nFrom >= 1 && nFrom <= 3 && nTo >= 1
    
13.                 && nTo <= 3 && nFrom != nTo && nPalates >= 0);
    
14. 
    
15.         if (0 == nPalates) return;
    
16. 
    
17.         int nOther = GetOther(nFrom, nTo);
    
18.         mov(nPalates-1, nFrom, nOther);
    
19.         cout<<nFrom<<" -> "<<nTo<<endl;
    
20.         mov(nPalates-1, nOther, nTo);
    
21. }
    

复制代码

用stack替代递归

struct Step
{
     char from;
     char temp;
     char to;
     int n;
};

void Move(char from, char temp, char to, int n)
{
     stack< Step > ss;
     Step s = {from, temp, to, n};
     ss.push(s);
     while(ss.size() > 0)
     {
          Step intent = ss.top();
          assert(intent.n != 0);
          if(intent.n == 1)
          {
               cout << "move " << " from " << intent.from << " to " << intent.to << endl;
               ss.pop();
               continue;               
          }
          Step step1 = {intent.from, intent.to, intent.temp, intent.n - 1};
          Step step2 = {intent.from, intent.temp, intent.to, 1};          
          Step step3 = {intent.temp, intent.from, intent.to, intent.n - 1};

          ss.pop();
          ss.push(step3);
          ss.push(step2);
          ss.push(step1);
     }
}