汉诺塔递归算法,团队圣塔移动步骤公式

汉诺塔递归算法|团队圣塔移动步骤公式

文章来源:杭州拓展训练公司|作者:户外旅行|发布时间:2018-08-30 12:24|点击数:

很多的团队在体验团队圣塔拓展的过程中非常懵逼,移着移着发现移动错了,渐渐的没有了思路,不知道该如何巧移圣塔了,因此,整个过程非常茫然。

想知道巧移团队圣塔规律吗,想知道团队圣塔移动步骤公式吗,想知道汉诺塔递归算法吗,如果你正在困惑中,那就详细看看户外旅行为您解说的汉诺塔递归算法。

汉诺塔递归算法

如下图所示,从左到右有A、B、C三根柱子,其中A柱子上面有从小叠到大的n个圆盘,现要求将A柱子上的圆盘移到C柱子上去,期间只有一个原则:一次只能移到一个盘子且大盘子不能在小盘子上面,求移动的步骤和移动的次数。

团队圣塔模拟图解

团队圣塔模拟图解

解:(1)n == 1

第1次 1号盘 A---->C sum = 1 次

(2) n == 2

第1次 1号盘 A---->B

第2次 2号盘 A---->C

第3次 1号盘 B---->C sum = 3 次

(3)n == 3

第1次 1号盘 A---->C

第2次 2号盘 A---->B

第3次 1号盘 C---->B

第4次 3号盘 A---->C

第5次 1号盘 B---->A

第6次 2号盘 B---->C

第7次 1号盘 A---->C sum = 7 次

不难发现规律:1个圆盘的次数2的1次方减1,2个圆盘的次数2的2次方减1,3个圆盘的次数2的3次方减1,n个圆盘的次数2的n次方减1。

故:移动次数为:2^n - 1

99%的网友还浏览了团队圣塔拓展训练相关文章

团队圣塔|汉诺塔拓展项目

拓展项目团队圣塔玩法|移动步骤技巧答案解说

汉诺塔递归算法分析

我们在利用计算机求汉诺塔问题时,必不可少的一步是对整个实现求解进行算法分析。到目前为止,求解汉诺塔问题最简单的算法还是同过递归来求,至于是什么是递归,递归实现的机制是什么,我们说的简单点就是自己是一个方法或者说是函数,但是在自己这个函数里有调用自己这个函数的语句,而这个调用怎么才能调用结束呢?,这里还必须有一个结束点,或者具体的说是在调用到某一次后函数能返回一个确定的值,接着倒数第二个就能返回一个确定的值,一直到第一次调用的这个函数能返回一个确定的值。

实现这个算法可以简单分为三个步骤:

(1) 把n-1个盘子由A 移到 B;

(2) 把第n个盘子由 A移到 C;

(3) 把n-1个盘子由B 移到 C;

从这里入手,在加上上面数学问题解法的分析,我们不难发现,移到的步数必定为奇数步:

(1)中间的一步是把最大的一个盘子由A移到C上去;

(2)中间一步之上可以看成把A上n-1个盘子通过借助辅助塔(C塔)移到了B上,

(3)中间一步之下可以看成把B上n-1个盘子通过借助辅助塔(A塔)移到了C上;

递归算法的答案已经告诉你了,你是否已经找到了团队圣塔移动步骤公式了呢,相信你的团队智慧还是很高的,加油吧。

上一篇:沙场点兵拓展游戏项目应该怎么玩?

下一篇:极速60秒拓展游戏1到30张答案图片大全