ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

EH搜索     
EH云课堂-专业的职场技能充电站 Excel转在线管理系统,怎么做看这里 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
Excel不给力? 何不试试FoxTable! Excel 2016函数公式学习大典 高效办公必会的Office实战技巧 免费下载Excel行业应用视频
300集Office 2010微视频教程 Tableau-数据可视化工具 精品推荐-800套精选PPT模板,点击获取 ExcelHome出品 - VBA代码宝免费下载
你的Excel 2010实战技巧学习锦囊 欲罢不能, 过目难忘的 Office 新界面 Excel VBA经典代码实践指南
查看: 4753|回复: 22

[分享] 经典汉诺塔游戏

[复制链接]

TA的精华主题

TA的得分主题

发表于 2013-11-24 17:07 | 显示全部楼层 |阅读模式
本帖已被收录到知识树中,索引项:递归
汉诺塔的数学分析:


我们先来讲故事:

汉诺塔(Hanoi塔)问题是印度的一个古老的传说。

在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。
印度教的主神梵天(开天辟地的神勃拉玛) 在创造世界的时候,
在其中一根针上从下到上地穿好了由大到小的64片金片,
最大的一个金片放在最底下,其余一个比一个小,依次叠加上去。
这就是所谓的汉诺塔。

不论白天黑夜,庙里总有一个僧侣在按照下面的法则移动这些金片:
1、可以把任何一根针上的金片移动到其它另外两根针中的一个针上去;
2、但一次只能移动最上面的那一片金片;
3、不管在哪根针上,小片必须放在大片上面。

……当所有的金片都从梵天穿好的那根针上(A针)移到第3根针(C针)上时,
世界就将在一声霹雳中消灭,梵塔、庙宇和众生都将同归于尽。

后来,这个传说就演变为汉诺塔游戏。

我们把金片的数量叫做阶,那么64个金片就叫做64阶汉诺塔。

经数学计算,64阶汉诺塔移动圆片的次数=2^64-1=18446744073709551615,
以每次移动耗时1秒来计算,大约需要5850亿年。
看来,即使到地球毁灭,众僧们也不可能完成金片的移动。


为了方便说明,我们将从3阶汉诺塔游戏开始说起。

评分

参与人数 2鲜花 +4 收起 理由
micch + 3
aoe1981 + 1 生动有趣,讲得好!

查看全部评分

TA的精华主题

TA的得分主题

发表于 2013-11-24 17:14 | 显示全部楼层
嵌套吗,这个原来看着就 有点晕的

TA的精华主题

TA的得分主题

发表于 2013-11-24 17:26 | 显示全部楼层

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-11-24 17:40 | 显示全部楼层
本帖最后由 香川群子 于 2013-11-24 20:08 编辑

归纳法证明:

首先,规定起始针叫做A、目标针叫做C、中间B针作为过渡。
设 函数 f(x)

1.
1阶汉诺塔只需要移动 1次
A → C 完成

即 f(1)=1


2.
2阶汉诺塔只需要移动 3次
金片1: A → B  (过渡)
金片2: A → C  (金片2到位)
金片1: B → C  (金片1从过渡B针到目标C针、完成)

即 f(2)=3


3.
3阶汉诺塔只需要移动 7次
金片1: A → C  (过渡)
金片2: A → B  (过渡)
金片1: C → B  (金片12到达过渡B针)

金片3: A → C  (金片3到位)
金片1: B → A  (过渡)
金片2: B → C  (金片2到位)

金片1: A → C  (全部完成)

即 f(3)=7


…………
下面证明,f(k+1)=f(k)*2+1

对于第k+1阶汉诺塔,有:
第一步骤,把A针上所有1-k的金片全部移动到过渡B针上去。
相当于把k阶汉诺塔,从A针开始,以C针为过渡,以B针为目标进行转移,
转移次数为已知的 f(k)次

第二步骤,直接把第k+1个金片从A针移动到目标C针,需要1步

第三步骤,把过渡B针上所有1-k的金片全部移动到目标C针上去。
相当于把k阶汉诺塔,从B针开始,以A针为过渡,以C针为目标进行转移,
转移次数为已知的 f(k)次

这样就完成了所有K+1个金片的转移。
总数 f(k+1)= f(k)+1+f(k)

即 f(k+1)=f(k)*2+1


那么,已知f(1)=1 (或者按照f(0)=0记忆亦可)
那么代入即可得到:
f(2)=1*2+1=3
f(3)=3*2+1+7
…………

[f(k+1)-1]/f(k)=2 存在2^n关系。

而f(1)=1 (或f(0)=0)
所以假设f(1)=2^1+c (或f(0)=2^0+c)时,c=-1

因此最后有:
f(K)=2^k-1

评分

参与人数 1鲜花 +1 收起 理由
aoe1981 + 1 精辟,严谨,极具数学素养!

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-11-24 17:50 | 显示全部楼层
这个游戏和我们熟知的九连环游戏一样,很多步骤都是简单重复的。

因此,引入递归概念以后,可以非常方便地得到游戏的每一个移动步骤解。


……
事实上,学习递归时,汉诺塔往往被作为最基本的一个递归练习题来介绍、学习。

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-11-24 17:59 | 显示全部楼层
首先我们先来看一下这个例子:

用递归方法计算自然数的阶乘:
  1. Sub test()
  2.     MsgBox Fct(5)
  3. End Sub
  4. Function Fct(n)
  5.     If n = 1 Then Fct = 1 Else Fct = Fct(n - 1) * n
  6. End Function
复制代码
本来,如果使用For……Next循环,也可以轻松地计算出自然数的阶乘结果:
Function Fct2(n)
    s = 1
    For i = 1 To n
        s = s * i
    Next
    Fct2 = s
End Function

用递归计算阶乘,未必是一个好主意,但这个例子,却提供了理解递归算法思路的一个很好的切入点。

(有人不认为递归是一种算法……但大部分人认可递归可以作为算法归类,因为递归肯定不能当做是数据结构)



TA的精华主题

TA的得分主题

 楼主| 发表于 2013-11-24 18:45 | 显示全部楼层
回过头,继续通过解析阶乘的递归算法来 进一步介绍递归思路。

首先,递归必须是一种相同计算过程的重复。(即可归纳的算法)

例如,5的阶乘= 1*2*3*4*5  或者也可以理解为 = 5*4*3*2*1

那么,阶乘的数学计算必须是分步进行的,
借用变量s,我们观察结果如下:

s=1
s=s*2=1*2=2
s=s*3=2*3=6
s=s*4=6*4=24
s=s*5=24*5=120 结束。


总结一下上述过程,把上述过程倒过来看,就可以发现:
每一步的计算过程= s * n (n为当前序号)
到最后(第1行时)是 s=1 (n=1 时)


那么,上述相同的计算过程中的s,我们可以把它看作是一个递变变量s,
即每次的计算结果都会更新,且其计算结果依赖于下一次计算过程。(相同的计算过程)
直至计算至条件底部(n=1时),可以返回一个定值。(s=1)

然后,再把上述过程逐层退回(回归),就能得到最终计算结果。

这个一层一层把变量计算过程(s=s*n)传递下去,
到条件底部(s=1)时再逐层返回计算结果的计算方法,
就称之为 递归过程 (或称迭代递归过程)

具体如下:
s=s*5
s=(s*4)*5
s=((s*3)*4)*5
s=(((s*2)*3)*4)*5
s=(((1*2)*3)*4)*5
s=(((2)*3)*4)*5
s=((6)*4)*5
s=(24)*5
s=120

就是这样一个过程。






评分

参与人数 1鲜花 +1 收起 理由
aoe1981 + 1 讲得好,看此楼就清晰了……

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-11-24 18:58 | 显示全部楼层
递归算法的结构:

1. 一个封装为递归函数(Function)或递归过程(Sub)的代码过程
2. 该函数有参数(递归变量,例如 n)的传递,以及相同的处理过程(例如 s*n)
3. 进入下一递归过程以后计算中有变量的改变(递增、递减或其它变化)
4. 存在底部条件(即退出、返回条件,例如 n=1)
5. 最终递归结果是收敛的(可以逐层退出直至结束)


按照高手的概括性总结,还可以描述为:
1. 过程中存在入口和出口
2. 进行规则相同的过程计算
3. 可以收敛退出

只要满足这些条件,就是一个合格的递归过程了。

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-11-24 19:52 | 显示全部楼层
本帖最后由 香川群子 于 2013-11-24 20:12 编辑

下面我们回到汉诺塔问题:


但是,首先再次回顾一下阶乘的递归算法:
1. 参数 n
2. 递归过程计算规则:
    f(k) =f(k-1)*n
3. 底部条件 n=1 时 s=1

于是就有:
Function f(n)
   If n=1 Then
     f=1
   Else
     f=f(n-1)*n
   End If
End Function

……明白了吧。

那么,对于汉诺塔有:
1. 参数 n ,以及3根针的状态(源针A、过渡针B、目标针C)

2. 递归过程计算规则:
    f(k) =f(k-1) [1~n-1金片作为整体全部: A→B,C过渡]+[n金片: A-C直接]+f(k-1)[1~n-1金片作为整体全部:B→C,A过渡]

3. 底部条件 n=1 时 f(1)=1[A-C直接]

因此有:



  1. Sub Hanoi()'汉诺塔解法过程
  2.     Call dg_Hanoi2(5, "A", "C", "B") '以5阶塔为例计算,以"A"针起始,目标"C"针,以"B"针过渡
  3. End Sub

  4. Sub dg_Hanoi(n, a, c, b) '汉诺塔递归计算过程
  5.      '参数为: n阶塔,以a针起始,目标c针,以b针过渡
  6.     '需要注意的是:在递归过程中随着参数变化,
  7.     '这时候的a针并非一定等于"A"针,同样b针/c针也并非一定是等于"B"针/"C"针


  8.     If n = 1 Then
  9.         Debug.Print "Move " & n & ": " & a & "→" & c
  10.         '到n=1时为底部退出条件,并将第1个金片从a针移动到c针(不需要过渡)
  11.         '需要注意的是:这时候的a针并非一定等于"A"针,同样c针也并非一定是等于"C"针

  12.     Else
  13.         Call dg_Hanoi(n - 1, a, b, c)
  14.         '过程1: 模拟把全部n-1个金片,全部从a针移动到b针(c针过渡)
  15.         '同样a针/b针/c针 并非一定是等于"A"针/"B"针/"C"针

  16.         Debug.Print "Move " & n & ": " & a & "→" & c
  17.         '过程2: 然后把第n个金片,直接从a针移动到目标c针(不需要过渡)
  18.         '同样这里的a针/c针 并非一定是等于"A"针/"C"针
  19.         
  20.         Call dg_Hanoi(n - 1, b, c, a)
  21.         '过程3: 然后模拟把全部n-1个金片,从过渡b针再移动到目标c针(以a针为过渡)
  22.         '同样a针/b针/c针 并非一定是等于"A"针/"B"针/"C"针

  23.     End If
  24. End Sub
复制代码
…………
需要注意的是:
a、b、c 3个针参数,并非固定的(如果固定就不需要把参数作为变量传递了)
而是根据目前的状态而确定哪个针是源针、哪个针是目标针,哪个针是过渡针。


这一点,可能是很多人无法直接理解的原因吧。



TA的精华主题

TA的得分主题

 楼主| 发表于 2013-11-24 20:05 | 显示全部楼层
不加注释的话,代码看上去非常简洁:
  1. Sub Hanoi2()
  2.     Call dg_Hanoi2(5, "A", "C", "B")
  3. End Sub

  4. Sub dg_Hanoi2(n, a, c, b)
  5.     If n = 1 Then
  6.         Debug.Print "Move " & n & ": " & a & "→" & c
  7.     Else
  8.         Call dg_Hanoi2(n - 1, a, b, c)
  9.         Debug.Print "Move " & n & ": " & a & "→" & c
  10.         Call dg_Hanoi2(n - 1, b, c, a)
  11.     End If
  12. End Sub
复制代码

点评

简洁就是一种美,基础是:“有力”!  发表于 2014-11-26 21:08
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

关注官方微信,高效办公专列,每天发车

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2019-8-17 21:11 , Processed in 0.120501 second(s), 20 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2020 Wooffice Inc.

   

沪公网安备 31011702000001号 沪ICP备11019229号

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:徐怀玉律师 李志群律师

快速回复 返回顶部 返回列表