数学研发论坛

 找回密码
 欢迎注册
查看: 203|回复: 5

[游戏] 至少要移动几次?

[复制链接]
发表于 7 天前 | 显示全部楼层 |阅读模式

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

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

x
我来出道题,活跃活跃(气氛有点闷):
甲柱有 1~64 号盘,要移动到乙柱 2,5,8,11,14,....62 号,
丙柱 3,6,9,12,15,.....63 号,甲柱自留 1,4,7,10,13,.....64 号,
至少要移动多少次?(汉诺塔问题的移动规则不能变)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 7 天前 | 显示全部楼层
64号盘一开始就移动好了
全部最优解把63号移动到丙柱的次数都是相同的
因为63号移动到丙柱需要1-62号在乙柱,此时我们也同样完成了62号盘的移动
下一步移动61号盘到甲,需要把1-60移动到丙
……
把每一步的最优解加起来,就是这道题的答案
然而不想加
好累
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 6 天前 来自手机 | 显示全部楼层
完全将n个盘从一根柱子移动到另外一根需要2^n-1次。
64根问题保持64不动,花费2^62次移动前62根和移动63好盘转化为62个盘问题。所以最终需要2^62+2^60+...+2^0
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 5 天前 | 显示全部楼层
mathe 发表于 2018-12-5 22:09
完全将n个盘从一根柱子移动到另外一根需要2^n-1次。
64根问题保持64不动,花费2^62次移动前62根和移动63好 ...


谢谢mathe!答案是\(\frac{4^{32}-1}{3}\)

主帖可以是3道题。
1,甲柱有 1~64 号盘,要移动到乙柱 2,5,8,11,14,....62 号,
丙柱 3,6,9,12,15,.....63 号,甲柱自留 1,4,7,10,13,.....64 号,
至少要移动多少次?(汉诺塔问题的移动规则不能变)
2,甲柱有 1~64 号盘,要移动到乙柱 3,6,9,12,15,....63 号,
丙柱 1,4,7,10,13,.....64 号,甲柱自留 2,5,8,11,14,....62  号,
至少要移动多少次?(汉诺塔问题的移动规则不能变)
3,甲柱有 1~64 号盘,要移动到乙柱 1,4,7,10,13,....64 号,
丙柱 2,5,8,11,14,.....62 号,甲柱自留 3,6,9,12,15,.....63 号,
至少要移动多少次?(汉诺塔问题的移动规则不能变)

64个盘太大了,我们退回去:
甲柱有 1个盘,出3道题,
甲柱有 2个盘,出3道题,
甲柱有 3个盘,出3道题,......则有
           甲=3n+0   甲=3n+1   甲=3n+2
01个盘       1             0              1
02个盘       2             3              1
03个盘       2             5              7
04个盘      15            5              10
05个盘      21           31             10
06个盘      21           42             63
07个盘     127          42             85
08个盘     170         255            85
09个盘     170         341           511   
10个盘    1023        341           682
11个盘    1365       2047          682
12个盘    1365       2730         4095
13个盘    8191       2730         5461
14个盘   10922     16383         5461
15个盘   10922     21845        32767
16个盘   65535     21845        43690
3道题有一个共同的数字串:0,1,2,5,10,21,42,85,170,341,682,1365,2730,5461,10922,.....
数字串的通项公式:\[a(n)=\frac{2^n}{3}+\frac{(-1)^n}{6}-\frac{1}{2}\]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 4 天前 | 显示全部楼层
再出 4 道题(汉诺塔问题的移动规则不能变):

第 1 道题。
甲柱有 1~64 号盘,要移动到乙柱为 1,5,9,13,17,....61 号
丙柱为 2,6,10,14,18,....62 号,,丁柱为 3,7,11,15,19,....63 号,
甲柱为 4,8,12,16,20,....64 号,至少要移动几次?

第 2 道题。
甲柱有 1~64 号盘,要移动到乙柱为 2,6,10,14,18,....62 号,
丙柱为 3,7,11,15,19,....63 号,丁柱为 4,8,12,16,20,....64 号,
甲柱为 1,5,9,13,17,....61 号,至少要移动几次?

第 3 道题。
甲柱有 1~64 号盘,要移动到乙柱为 3,7,11,15,19,....63 号,
丙柱为 4,8,12,16,20,....64 号,丁柱为 1,5,9,13,17,....61 号,
甲柱为 2,6,10,14,18,....62 号,至少要移动几次?

第 4 道题。
甲柱有 1~64 号盘,要移动到乙柱为 4,8,12,16,20,....64 号,
丙柱为 1,5,9,13,17,....61 号,丁柱为 2,6,10,14,18,....62 号,
甲柱为 3,7,11,15,19,....63 号,至少要移动几次?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 前天 11:00 | 显示全部楼层
本帖最后由 王守恩 于 2018-12-9 12:51 编辑
.·.·. 发表于 2018-12-4 21:23
64号盘一开始就移动好了
全部最优解把63号移动到丙柱的次数都是相同的
因为63号移动到丙柱需要1-62号在乙 ...


谢谢  .·.·. !请为下面的题也指点一下思路。
(汉诺塔问题的移动规则不能变)。谢谢 !
甲柱有 1~15 号盘, 1~15 号盘的重量分别是 1~15 ,
要移动到乙柱 5 个盘,丙柱 5 个盘,甲柱自留  5 个盘。
要使每根柱上盘的重量都是40,至少要移动多少次?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2018-12-11 03:28 , Processed in 0.048880 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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