文章
20
粉丝
147
获赞
13
访问
52.7k
Hanoi问题绝对是一个理解递归的好题,对一个将N个圆盘从A移动到C的问题,我们可以将它分解成三步
将其上的N-1个圆盘从A移动到B。
将第N个圆盘从A移动到C。
将B上的N-1个圆盘移动到C。
每次移动都有一个起点S,一个终点T,还有一个中介M,另外还有想要移动的盘子的数目cnt,当需要移动的数目为1时,我们就可以打印移动的方法。写成程序就是下面这样
//将cnt个圆盘从S盘经过M移动到T
void hanoi(char S, char T, char M, ll cnt) {
if (cnt == 1)
pprint(S, T);
else {
hanoi(S, M, T, cnt - 1);//把上面cnt-1个硬盘从S经过T移动到M
hanoi(S, T, M, 1);//把最底下的1个硬盘移动到T
hanoi(M, T, S, cnt - 1);//把移动到M上的cnt-1个硬盘通过S移到终点T
}
}
然后就是需要注意路径的打印五个一组,使用一个全局变量进行监控即可
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define inf 0x3ffffff
#define vec vector<ll>
ll tot = 0;
void pprint(char s, char t) {
if (tot == 5)printf("\n"), tot = 0;
printf("%c-->%c ", s, t); tot++;
}
//将cnt个圆盘从S盘经过M移动到T
void hanoi(char S, char T, char M, ll cnt) {
if (cnt == 1)
pprint(S, T);
else {
hanoi(S, M, T, cnt - 1);//把上面cnt-1个硬盘从S经过T移动到M
hanoi(S, T, M, 1);//把最底下的1个硬盘移动到T
hanoi(M, T, S, cnt - 1);//把移动到M上的cnt-1个硬盘通过S移到终点T
}
}
...
登录后发布评论
暂无评论,来抢沙发