asp做网站的缺点,沈阳设计网站公司网站,上海招聘信息网官网,邯郸房产网签怎么查询题解#xff1a;汉诺塔(递归、搜索与回溯算法) 目录 1.题目2.题目背景(拓展了解)3.题解4.参考代码5.细节6.总结 1.题目
题目链接#xff1a;LINK
2.题目背景(拓展了解)
汉诺塔问题是一个通过隐式使用递归栈来进行实现的一个经典问题#xff0c;该问题最早的发明人是法国… 题解汉诺塔(递归、搜索与回溯算法) 目录 1.题目2.题目背景(拓展了解)3.题解4.参考代码5.细节6.总结 1.题目
题目链接LINK
2.题目背景(拓展了解)
汉诺塔问题是一个通过隐式使用递归栈来进行实现的一个经典问题该问题最早的发明人是法国数学家爱德华·卢卡斯。
汉诺塔传说 传说印度某间寺院有三根柱子上串64个金盘。寺院里的僧侣依照一个古老的预言以上述规则移动这些盘子预言说当这些盘子移动完毕世界就会灭亡。这个传说叫做梵天寺之塔问题Tower of Brahma puzzle。但不知道是卢卡斯自创的这个传说还是他受他人启发。若传说属实僧侣们需要2^64 − 1步才能完成这个任务若他们每秒可完成一个盘子的移动就需要5845亿年才能完成。整个宇宙现在也不过137亿年。这个传说有若干变体寺院换成修道院、僧侣换成修士等等。寺院的地点众说纷纭其中一说是位于越南的河内所以被命名为“河内塔”。另外亦有“金盘是创世时所造”、“僧侣们每天移动一盘”之类的背景设定。佛教中确实有“浮屠”塔这种建筑有些浮屠亦遵守上述规则而建。“汉诺塔”一名可能是由中南半岛在殖民时期传入欧洲的。
与之相似的一个故事就是“棋盘放大米的故事” 故事是这样的最初一位大哥发明了一种玩具叫做围棋这个围棋有64个格子组成国王很高兴问发明者什么赏赐发明者说到“第一个格子放1粒大米第二个格子放2粒大米第三个格子放4粒大米此后每个格子都是前面的两倍大米放满棋盘上的64个格子就好”随后国王欣然接受然而经过实践即使把整个王国的大米搬过来放也不能放满64个棋格。
这两个故事都揭示了一个道理——指数大爆炸。
3.题解
我们枚举不同N情况下移动过程如下 写递归的步骤 函数头的设计 除N 1情况外所有N的情况都可以分为三步即先把A柱上的前N-1个盘子放到B柱上再把A柱的最下面一个盘子放到C上再把B柱上的盘子放到C上。 所以解决此问题我们只需要接受A、B、C、N的个数即可。 函数体的设计 先把A柱上的N-1个盘子放到B柱上再把A的最下的一个盘子放到C上再把B上的N-1个盘子放到C上。 函数结束 当N 1时不再满足上述三步走规律只需要把那个盘子放到C上即可。
4.参考代码
class Solution {
public:void hanota(vectorint A, vectorint B, vectorint C) {dfs(A,B,C,A.size());}void dfs(vectorint A, vectorint B, vectorint C,int n){//出递归if(n 1){C.push_back(A.back());A.pop_back();return;}//1.先把A中的N-1个盘子借助C扔到B上dfs(A,C,B,n-1);//2.再把A中剩下的一个盘子扔到C上C.push_back(A.back());A.pop_back();//3.再把B中的N-1个盘子借助A扔到C上dfs(B,A,C,n-1);}
};5.细节
思考 如果我们把代码C.push_back(A.back())改成C.push_back(A[0])可以吗为什么
答不行。 因为我们思考顺序与实际挪动顺序不一致。 虽然我们直觉上认为A.back()与A[0]在只剩下一个元素时候都表示的是最后的那个盘子但是计算机运行的顺序跟我们脑子想的顺序并不一致计算机先从最小的子问题(不可分割)的情况开始运算而我们想的是先从最大问题的那个开始思考。 在只剩下一个元素的情况下A[0]和A.back()的确是一样的但是计算机运行的时候并不是只有一个元素
举个例子
6.总结
汉诺塔作为经典的简单递归题目是需要好好理解的比如我上面提到的写递归的步骤以及为什么A.back()不能写成A[0]的问题。 EOF
