左神算法书籍《程序员代码面试指南》——1_06用栈来求解汉诺塔问题
2020-12-13 06:15
标签:汉诺塔问题 amp rem 最优 修改 限制 int 最大的 rsize 【问题】 汉诺塔问题比较经典,这里修改一下游戏规则: 方法一: 方法二: 借助栈来实现 执行LM,违反小压大原则 左神算法书籍《程序员代码面试指南》——1_06用栈来求解汉诺塔问题 标签:汉诺塔问题 amp rem 最优 修改 限制 int 最大的 rsize 原文地址:https://www.cnblogs.com/zzw1024/p/11172260.html
现在限制不能从最左侧的塔直接移动到最右侧,也不能从最右侧直接移动到最左侧,
而是必须经过中间。求当塔有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 ": " "->" endl;
6 cout ": " "->" endl;
7 return;
8 }
9 //上面n-1当成一个整体Y
10 Hanota(l, m, r, n - 1);//Y直接移动到最右端
11 cout ": " "->" //X移动到中间
12 Hanota(r, m, l, n - 1);//Y移动到最左边
13 cout ": " "->" //n移动到最右端
14 Hanota(l, m, r, n - 1);//Y移动到最右端
15 }
用三个栈来实现,三个栈分别为Ls,Ms,Rs
为了不违反汉诺塔中大不能压小的法则,
三个栈必须维持小数在上,大数在下
限制
当上一步为:LM,下一步的情况分析:
执行ML,违反逆反原则
执行MR还是RM,按照小压大原则,这两种情况是互斥的,只能按条件二选一
其他分析类似,省略... 1 void Help(string &pre, string preMove, string nowMove, stackint>&Fs, stackint>&Ts)
2 {
3 if (!Fs.empty() && pre != nowMove && Fs.top() Ts.top())
4 {
5 Ts.push(Fs.top());
6 Fs.pop();
7 cout endl;
8 pre = preMove;
9 }
10 }
11
12
13 void stackToHanota(int n, string l, string m, string r)
14 {
15 stackint>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 }
文章标题:左神算法书籍《程序员代码面试指南》——1_06用栈来求解汉诺塔问题
文章链接:http://soscw.com/essay/32759.html