数学研发论坛

 找回密码
 欢迎注册
查看: 8970|回复: 32

[原创] 多柱汉诺塔算法

[复制链接]
发表于 2017-1-15 09:31:25 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x



有兴趣的朋友,做一做下面的题目:
3根柱, 6个盘, 最小挪动步数是?次:
4根柱,11个盘,最小挪动步数是?次:
5根柱,14个盘,最小挪动步数是?次:
6根柱,17个盘,最小挪动步数是?次:
7根柱,19个盘,最小挪动步数是?次:
8根柱,20个盘,最小挪动步数是?次:
............
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-1-16 08:32:46 | 显示全部楼层
有兴趣的朋友,不妨做一做下面的题目:
3根柱, 6个盘, 最小挪动步数是63次:
4根柱,11个盘,最小挪动步数是65次:
5根柱,14个盘,最小挪动步数是63次:
6根柱,17个盘,最小挪动步数是65次:
7根柱,19个盘,最小挪动步数是63次:
8根柱,20个盘,最小挪动步数是65次:
............

希望有网友找到更小的挪动步数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-1-16 08:34:32 | 显示全部楼层
多柱汉诺塔解数统计表
091733u64iku2y6iim86v6.jpg
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-1-16 08:35:58 | 显示全部楼层
多柱汉诺塔算法

补充内容 (2017-3-2 17:34):
   n≥A(A+1)(A+2)......改:  n>A(A+1)(A+2)......        
   n<(A+1)(A+2).......改:   n≤(A+1)(A+2).......
091722u5twmm5z8bf55ebe.jpg
091728j2ql880820pzr9vq.jpg
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-1-16 08:37:12 | 显示全部楼层
一般地,我们有:
多柱汉诺塔题目。m根柱,n个盘,v种规格。
问题1:符合题意的最小移动步数是多少?
问题2:符合题意的最大移动步数是多少?

譬如:4根柱,16个盘,7种规格。
问题1:符合题意的最小移动步数是多少?
问题2:符合题意的最大移动步数是多少?

譬如:5根柱,20个盘,10种规格。
问题1:符合题意的最小移动步数是多少?
问题2:符合题意的最大移动步数是多少?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-1-16 09:17:02 | 显示全部楼层
本帖最后由 王守恩 于 2017-1-16 09:18 编辑

四柱汉诺塔最大移动步数统计表
有兴趣的网友让我们一起填一填下面的表格
QQ截图20170116091631.jpg
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-2-6 07:40:05 | 显示全部楼层
王守恩 发表于 2017-1-16 09:17
四柱汉诺塔最大移动步数统计表
有兴趣的网友让我们一起填一填下面的表格

manthanein先生:能给本帖《多柱汉诺塔算法》找一下类似解法?在此先谢谢了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-2-6 13:16:43 来自手机 | 显示全部楼层
fans版主以前发过一个类似的帖子的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-2-9 18:02:54 | 显示全部楼层
https://en.wikipedia.org/wiki/To ... our_pegs_and_beyond
Although the three-peg version has a simple recursive solution as outlined above which has long been known, the optimal solution for the Tower of Hanoi problem with four pegs (called Reve's puzzle) has not been verified until 2014, and in the case of more than four pegs the optimal solution is still an open problem, even if a proof that the Frame-Stewart algorithm is optimal is proposed by Demontis in 2016.

也就是说,这方面仍然有很多不清楚的东西,最优解是啥样的就不清楚
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-2-9 18:04:17 | 显示全部楼层
http://oeis.org/A007664

这个可能是目前所知最好的结果,但也许有比它更好的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-4-8 10:18 , Processed in 0.138233 second(s), 22 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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