【问题】

汉诺塔问题比较经典，这里修改一下游戏规则：

现在限制不能从最左侧的塔直接移动到最右侧，也不能从最右侧直接移动到最左侧，

而是必须经过中间。求当塔有N层的时候，打印最优移动过程和最优移动总步数。

例如，当塔数为两层时，最上层的塔记为1，最下层的塔记为2，则打印：

Move 1 from left to mid

Move 1 from mid to right

Move 2 from left to mid

Move 1 from right to mid

Move 1 from mid to left

Move 2 from mid to right

Move 1 from left to mid

Move 1 from mid to right

It will move 8 steps.

方法一：

使用递归的方法

无论多少层，都看作有两层，最大的一层(命名为X)、(N - 1)层合并起来的作为一层(命名为Y)，目标是将X移动到最右侧，然后再把Y移动到最右侧。

Y从A塔移动到B塔

Y从B塔移动到C塔

X从A塔移动到B塔

Y从C塔移动到B塔

Y从B塔移动到A塔

X从B塔移动到C塔

将Y看做X，继续递归移动

 

1 void Hanota(string l, string m, string r, int n) 2 { 3     if (n == 1)//当为一个时，则分两步直接移动到最右端 4     { 5         cout << n << ": " << l << "->" << m << endl; 6         cout << n << ": " << m << "->" << r << endl; 7         return; 8     } 9     //上面n-1当成一个整体Y10     Hanota(l, m, r, n - 1);//Y直接移动到最右端11     cout << n << ": " << l << "->" << m << endl;//X移动到中间12     Hanota(r, m, l, n - 1);//Y移动到最左边13     cout << n << ": " << m << "->" << r << endl;//n移动到最右端14     Hanota(l, m, r, n - 1);//Y移动到最右端15 }

 

 

方法二：

借助栈来实现

用三个栈来实现，三个栈分别为Ls,Ms,Rs

为了不违反汉诺塔中大不能压小的法则，

三个栈必须维持小数在上，大数在下

限制

当上一步为：LM，下一步的情况分析：

执行LM，违反小压大原则

执行ML，违反逆反原则

执行MR还是RM，按照小压大原则，这两种情况是互斥的，只能按条件二选一

其他分析类似，省略...

1 void Help(string &pre, string preMove, string nowMove, stack
     
      &Fs, stack
      
       &Ts) 2 { 3     if (!Fs.empty() && pre != nowMove && Fs.top() < Ts.top()) 4     { 5         Ts.push(Fs.top()); 6         Fs.pop(); 7         cout << preMove << endl; 8         pre = preMove; 9     }10 }11 12 13 void stackToHanota(int n, string l, string m, string r)14 {15     stack
       
        Ls, Ms, Rs;16     //为了方便比较栈顶元素，我们首先对每个栈都压入一个较大数17     Ls.push(INT_MAX);18     Ms.push(INT_MAX);19     Rs.push(INT_MAX);20     string pre = "LoM";21     for (int i = n; i > 0; --i)22         Ls.push(i);//数据入栈23     int layerSize = Ls.size();24     while (layerSize != Rs.size())25     {
   //左中右->右中左26         Help(pre, "LoM", "MoL", Ls, Ms);27         Help(pre, "MoR", "RoM", Ms, Rs);28         Help(pre, "RoM", "MoR", Rs, Ms);29         Help(pre, "MoL", "LoM", Ms, Ls);30     }31 }