ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

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

求助 汉诺塔 编程

[复制链接]

TA的精华主题

TA的得分主题

发表于 2013-11-14 12:16 | 显示全部楼层 |阅读模式
本帖已被收录到知识树中,索引项:递归
[p=140, null, left]1883

[p=140, null, left]年法国数学家


[p=140, null, left]Edouard Lucas

[p=140, null, left]曾提及这个故事,

[p=140, null, left]据说

[p=140, null, left]创世纪时

[p=140, null, left]Benares

[p=140, null, left]有一座波罗教塔,是由三支钻石棒(

[p=140, null, left]Pag

[p=140, null, left])所支撑,开始时神在第一根棒上放

[p=140, null, left]置

[p=140, null, left]64

[p=140, null, left]个由上至下依由小至大排列的金盘(

[p=140, null, left]Disc

[p=140, null, left])

[p=140, null, left],并命令僧侣将所有的金盘从第一根石棒移至第

[p=140, null, left]三根石棒,且搬运过程中遵守大盘子在小盘子之下的原则,若每日仅搬一个盘子,则当盘子全

[p=140, null, left]数搬运完毕之时,此塔将毁损,而也就是世界末日来临之时。

点评

知识树内容索引:4楼、5楼  发表于 2013-11-15 22:44

TA的精华主题

TA的得分主题

发表于 2013-11-14 13:28 | 显示全部楼层
标记 一下,有空研究研究

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-11-15 12:27 | 显示全部楼层
看C语言的编程,写个VBA代码,但最近不是很清楚,请大家分析下。
Dim nm As Integer
Sub ssss()
Dim n As Integer
n = InputBox("ÇëÊäÈëÒ»¸öÕýÕûÊý", "ÊäÈëÊý¾Ý", 2)
Call chu(n, "A", "B", "C")
End Sub
Sub chu(m As Integer, str1 As String, str2 As String, str3 As String)
If m = 1 Then
   
   MsgBox (m & " Move " & str1 & " to " & str3)
   Else: Call chu(m - 1, str1, str3, str2)
        MsgBox (m & " Move " & str1 & " to " & str3)
         Call chu(m - 1, str2, str1, str3)
   
   End If
   
End Sub

TA的精华主题

TA的得分主题

发表于 2013-11-15 15:20 | 显示全部楼层
hanoi 塔,典型的递归问题。

…………
用数组也能做……代码变成了几十行……

几十行也不算稀奇,为了创记录,我一生气写了100多行的代码,详细分解了各个过程呢。
  1. Sub Hanoi3()
  2.     tms = Timer
  3.     N = [a1]
  4.     For i = 1 To N
  5.         If i > 9 Then t = Chr(55 + i) & t Else t = i & t
  6.     Next
  7.     m = 2 ^ N
  8.     ReDim arr(m - 1, 3)
  9.     arr(0, 0) = N
  10.     arr(0, 1) = t
  11.     Dim e(3)
  12.     Dim l(3)
  13.     l(1) = N
  14.    
  15.     On Error GoTo Ext
  16.     If N Mod 2 = 1 Then '321
  17.         For i = 1 To m - 1 Step 6
  18.             arr(i, 0) = "A→C"
  19.             arr(i, 3) = arr(i - 1, 3) & 1: e(3) = 1: l(3) = l(3) + 1 'Move 1 from A to C
  20.             arr(i, 2) = arr(i - 1, 2) 'No Change B
  21.             arr(i, 1) = Left(arr(i - 1, 1), l(1) - 1): e(1) = Right(arr(i, 1), 1): l(1) = l(1) - 1 'Remove 1 from A
  22.             
  23.             arr(i + 1, 3) = arr(i, 3) 'No Change C
  24.             If l(2) = 0 Or (l(1) > 0 And e(1) < e(2)) Then
  25.                 arr(i + 1, 0) = "A→B"
  26.                 arr(i + 1, 2) = arr(i, 2) & e(1): e(2) = e(1): l(2) = l(2) + 1 'Move k from A to B
  27.                 arr(i + 1, 1) = Left(arr(i, 1), l(1) - 1): e(1) = Right(arr(i + 1, 1), 1): l(1) = l(1) - 1 'Remove k from A
  28.             Else
  29.                 arr(i + 1, 0) = "B→A"
  30.                 arr(i + 1, 1) = arr(i, 1) & e(2): e(1) = e(2): l(1) = l(1) + 1 'Move k from B to A
  31.                 arr(i + 1, 2) = Left(arr(i, 2), l(2) - 1): e(2) = Right(arr(i + 1, 2), 1): l(2) = l(2) - 1 'Remove k from B
  32.             End If
  33.             
  34.             
  35.             arr(i + 2, 0) = "C→B"
  36.             arr(i + 2, 2) = arr(i + 1, 2) & 1: e(2) = 1: l(2) = l(2) + 1 'Move 1 from C to B
  37.             arr(i + 2, 1) = arr(i + 1, 1) 'No Change A
  38.             arr(i + 2, 3) = Left(arr(i + 1, 3), l(3) - 1): e(3) = Right(arr(i + 2, 3), 1): l(3) = l(3) - 1 'Remove 1 from C
  39.             
  40.             arr(i + 3, 2) = arr(i + 2, 2) 'No Change B
  41.             If l(3) = 0 Or (l(1) > 0 And e(1) < e(3)) Then
  42.                 arr(i + 3, 0) = "A→C"
  43.                 arr(i + 3, 3) = arr(i + 2, 3) & e(1): e(3) = e(1): l(3) = l(3) + 1 'Move k from A to C
  44.                 arr(i + 3, 1) = Left(arr(i + 2, 1), l(1) - 1): e(1) = Right(arr(i + 3, 1), 1): l(1) = l(1) - 1 'Remove k from A
  45.             Else
  46.                 arr(i + 3, 0) = "C→A"
  47.                 arr(i + 3, 1) = arr(i + 2, 1) & e(3): e(1) = e(3): l(1) = l(1) + 1 'Move k from C to A
  48.                 arr(i + 3, 3) = Left(arr(i + 2, 3), l(3) - 1): e(3) = Right(arr(i + 3, 3), 1): l(3) = l(3) - 1 'Remove k from C
  49.             End If
  50.             
  51.             
  52.             arr(i + 4, 0) = "B→A"
  53.             arr(i + 4, 1) = arr(i + 3, 1) & 1: e(1) = 1: l(1) = l(1) + 1 'Move 1 from B to A
  54.             arr(i + 4, 3) = arr(i + 3, 3) 'No Change C
  55.             arr(i + 4, 2) = Left(arr(i + 3, 2), l(2) - 1): e(2) = Right(arr(i + 4, 2), 1): l(2) = l(2) - 1 'Remove 1 from B
  56.             
  57.             arr(i + 5, 1) = arr(i + 4, 1) 'No Change A
  58.             If l(3) = 0 Or (l(2) > 0 And e(2) < e(3)) Then
  59.                 arr(i + 5, 0) = "B→C"
  60.                 arr(i + 5, 3) = arr(i + 4, 3) & e(2): e(3) = e(2): l(3) = l(3) + 1 'Move k from B to C
  61.                 arr(i + 5, 2) = Left(arr(i + 4, 2), l(2) - 1): e(2) = Right(arr(i + 5, 2), 1): l(2) = l(2) - 1 'Remove k from B
  62.             Else
  63.                 arr(i + 5, 0) = "C→B"
  64.                 arr(i + 5, 2) = arr(i + 4, 2) & e(3): e(2) = e(3): l(2) = l(2) + 1 'Move k from C to B
  65.                 arr(i + 5, 3) = Left(arr(i + 4, 3), l(3) - 1): e(3) = Right(arr(i + 5, 3), 1): l(3) = l(3) - 1 'Remove k from C
  66.             End If
  67.         Next
  68.         
  69.     Else '231
  70.         For i = 1 To m - 1 Step 6
  71.             arr(i, 0) = "A→B"
  72.             arr(i, 2) = arr(i - 1, 2) & 1: e(2) = 1: l(2) = l(2) + 1 'Move 1 from A to B
  73.             arr(i, 3) = arr(i - 1, 3) 'No Change C
  74.             arr(i, 1) = Left(arr(i - 1, 1), l(1) - 1): e(1) = Right(arr(i, 1), 1): l(1) = l(1) - 1 'Remove 1 from A
  75.             
  76.             arr(i + 1, 2) = arr(i, 2) 'No Change B
  77.             If l(3) = 0 Or (l(1) > 0 And e(1) < e(3)) Then
  78.                 arr(i + 1, 0) = "A→C"
  79.                 arr(i + 1, 3) = arr(i, 3) & e(1): e(3) = e(1): l(3) = l(3) + 1 'Move k from A to C
  80.                 arr(i + 1, 1) = Left(arr(i, 1), l(1) - 1): e(1) = Right(arr(i + 1, 1), 1): l(1) = l(1) - 1 'Remove k from A
  81.             Else
  82.                 arr(i + 1, 0) = "C→A"
  83.                 arr(i + 1, 1) = arr(i, 1) & e(3): e(1) = e(3): l(1) = l(1) + 1 'Move k from C to A
  84.                 arr(i + 1, 3) = Left(arr(i, 3), l(3) - 1): e(3) = Right(arr(i + 1, 3), 1): l(3) = l(3) - 1 'Remove k from C
  85.             End If
  86.             
  87.             
  88.             arr(i + 2, 0) = "B→C"
  89.             arr(i + 2, 3) = arr(i + 1, 3) & 1: e(3) = 1: l(3) = l(3) + 1 'Move 1 from B to C
  90.             arr(i + 2, 1) = arr(i + 1, 1) 'No Change A
  91.             arr(i + 2, 2) = Left(arr(i + 1, 2), l(2) - 1): e(2) = Right(arr(i + 2, 2), 1): l(2) = l(2) - 1 'Remove 1 from B
  92.             
  93.             arr(i + 3, 3) = arr(i + 2, 3) 'No Change C
  94.             If l(2) = 0 Or (l(1) > 0 And e(1) < e(2)) Then
  95.                 arr(i + 3, 0) = "A→B"
  96.                 arr(i + 3, 2) = arr(i + 2, 2) & e(1): e(2) = e(1): l(2) = l(2) + 1 'Move k from A to B
  97.                 arr(i + 3, 1) = Left(arr(i + 2, 1), l(1) - 1): e(1) = Right(arr(i + 3, 1), 1): l(1) = l(1) - 1 'Remove k from A
  98.             Else
  99.                 arr(i + 3, 0) = "B→A"
  100.                 arr(i + 3, 1) = arr(i + 2, 1) & e(2): e(1) = e(2): l(1) = l(1) + 1 'Move k from B to A
  101.                 arr(i + 3, 2) = Left(arr(i + 2, 2), l(2) - 1): e(2) = Right(arr(i + 3, 2), 1): l(2) = l(2) - 1 'Remove k from B
  102.             End If
  103.             
  104.             
  105.             arr(i + 4, 0) = "C→A"
  106.             arr(i + 4, 1) = arr(i + 3, 1) & 1: e(1) = 1: l(1) = l(1) + 1 'Move 1 from C to A
  107.             arr(i + 4, 2) = arr(i + 3, 2) 'No Change B
  108.             arr(i + 4, 3) = Left(arr(i + 3, 3), l(3) - 1): e(3) = Right(arr(i + 4, 3), 1): l(3) = l(3) - 1 'Remove 1 from C
  109.             
  110.             arr(i + 5, 1) = arr(i + 4, 1) 'No Change A
  111.             If l(3) = 0 Or (l(2) > 0 And e(2) < e(3)) Then
  112.                 arr(i + 5, 0) = "B→C"
  113.                 arr(i + 5, 3) = arr(i + 4, 3) & e(2): e(3) = e(2): l(3) = l(3) + 1 'Move k from B to C
  114.                 arr(i + 5, 2) = Left(arr(i + 4, 2), l(2) - 1): e(2) = Right(arr(i + 5, 2), 1): l(2) = l(2) - 1 'Remove k from B
  115.             Else
  116.                 arr(i + 5, 0) = "C→B"
  117.                 arr(i + 5, 2) = arr(i + 4, 2) & e(3): e(2) = e(3): l(2) = l(2) + 1 'Move k from C to B
  118.                 arr(i + 5, 3) = Left(arr(i + 4, 3), l(3) - 1): e(3) = Right(arr(i + 5, 3), 1): l(3) = l(3) - 1 'Remove k from C
  119.             End If
  120.         Next
  121.         
  122.     End If
  123.    
  124. Ext:
  125.     [g1].CurrentRegion = ""
  126.     [g1].Resize(m, 4) = arr
  127.     [j1] = Timer - tms
  128. End Sub
复制代码

TA的精华主题

TA的得分主题

发表于 2013-11-15 15:23 | 显示全部楼层
递归代码是最简单的:
  1. Private Sub Hanoi1(ByVal n%, ByVal A$, ByVal B$, ByVal C$)
  2.     If n = 1 Then
  3.         k = k + 1: arr1(k) = A & "→" & C
  4.     Else
  5.         Hanoi1 n - 1, A, C, B
  6.         k = k + 1: arr1(k) = A & "→" & C
  7.         Hanoi1 n - 1, B, A, C
  8.     End If
  9. End Sub
复制代码

TA的精华主题

TA的得分主题

发表于 2013-11-15 15:49 | 显示全部楼层

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-11-15 22:26 | 显示全部楼层
香川群子 发表于 2013-11-15 15:23
递归代码是最简单的:

谢谢,以前以为自己懂递归,现在看这个例子,彩感觉到自己的差距!顺便问下美女,你是不是学计算机的啊,很精通算法啊!

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-11-15 22:30 | 显示全部楼层
qq348104184 发表于 2013-11-15 22:26
谢谢,以前以为自己懂递归,现在看这个例子,彩感觉到自己的差距!顺便问下美女,你是不是学计算机的啊, ...

关键是对汉诺塔计算方法有深刻的认识!

TA的精华主题

TA的得分主题

发表于 2013-11-16 13:58 | 显示全部楼层
附件是完整的汉诺威塔移动的递归算法代码,
增加了完整的移动过程。

因为是直接用123456789来表示各种状态,所以允许计算塔层数最大=9。
(理论上对层数是没有限制的。)
  1. Dim jg(), k
  2. Sub Hanoi()
  3.     n = Val(InputBox("Hanoi塔层数n=:(1-9)", "递归移动汉诺威塔", 9))
  4.     If n > 9 Then MsgBox n & " > 9 !": Exit Sub
  5.     k = 2 ^ n: ReDim jg(k + 1, 1 To 7)
  6.     jg(0, 1) = "A": jg(0, 2) = "B": jg(0, 3) = "C": jg(0, 4) = "解题步骤"
  7.     jg(0, 5) = "a": jg(0, 6) = "b": jg(0, 7) = "c": jg(1, 1) = Left("123456789", n)
  8.    
  9.     k = 1: Call dg_Hanoi(1, 2, 3, n)
  10.    
  11.     [a1].CurrentRegion = ""
  12.     [a1].Resize(k + 1, 7) = jg
  13. End Sub
  14. Sub dg_Hanoi(a, b, c, n)
  15.     If n = 1 Then
  16.         k = k + 1
  17.         jg(k, a) = Mid(jg(k - 1, a), 2)
  18.         jg(k, b) = jg(k - 1, b)
  19.         jg(k, c) = n & jg(k - 1, c)
  20.         jg(k, 4) = jg(0, a) & "→" & jg(0, c) & " " & n
  21.         jg(k, 5) = a: jg(k, 6) = b: jg(k, 7) = c
  22.     Else
  23.         Call dg_Hanoi(a, c, b, n - 1)
  24.         k = k + 1
  25.         jg(k, a) = Mid(jg(k - 1, a), 2)
  26.         jg(k, b) = jg(k - 1, b)
  27.         jg(k, c) = n & jg(k - 1, c)
  28.         jg(k, 4) = jg(0, a) & "→" & jg(0, c) & " " & n
  29.         jg(k, 5) = a: jg(k, 6) = b: jg(k, 7) = c
  30.         Call dg_Hanoi(b, a, c, n - 1)
  31.     End If
  32. End Sub
复制代码

递归 Hanoi.rar

16.34 KB, 下载次数: 46

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-11-17 10:45 | 显示全部楼层
香川群子 发表于 2013-11-16 13:58
附件是完整的汉诺威塔移动的递归算法代码,
增加了完整的移动过程。

谢谢大师的指点,个人感觉,写代码前一定把思路(算法)讲清楚,否则别人从代码反推你的思路是很费事的。
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

关闭

最新热点上一条 /1 下一条

关注官方微信,每天学会一个新技能

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

GMT+8, 2019-10-14 18:25 , Processed in 0.081913 second(s), 19 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2020 Wooffice Inc.

   

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

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

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