当前位置: 技术问答>linux和unix
最后一个汉诺塔问题，如果有3 + n个柱子，n为任意正整数，有谁有一个通用的最优解法？
来源: 互联网 发布时间：2016-04-09
本文导语: 如题 | 重赏之下，来试一试。 3+n的情况下，可以把M层移动变成n+1个M/(n+1)层的移动。总移动次数约为(n+1)*2^(M/(n+1))-1。 不过这显然不是最优，每次移动只利用了一根空闲的柱子。抛砖引玉吧。 ...
如题
|
重赏之下，来试一试。
3+n的情况下，可以把M层移动变成n+1个M/(n+1)层的移动。总移动次数约为(n+1)*2^(M/(n+1))-1。
不过这显然不是最优，每次移动只利用了一根空闲的柱子。抛砖引玉吧。
3+n的情况下，可以把M层移动变成n+1个M/(n+1)层的移动。总移动次数约为(n+1)*2^(M/(n+1))-1。
不过这显然不是最优，每次移动只利用了一根空闲的柱子。抛砖引玉吧。
|
对于多根柱子，设柱子数t，盘子n，另设将最大盘子移到最终柱子上时，最小盘子所在的柱子上盘子数位x，则最优步数为：
H(t,n)=2H(t,x)+H(t-1,n-x) t>3
H(3,n)=2^n-1
经证明，去x为ceil(t/2)(往上取整)或floor(t/2)往下取整时，H(t,n)最小，即最优
H(t,n)=2H(t,x)+H(t-1,n-x) t>3
H(3,n)=2^n-1
经证明，去x为ceil(t/2)(往上取整)或floor(t/2)往下取整时，H(t,n)最小，即最优
|
to suwein:
H(t,n)=2H(t,x)+H(t-1,n-x) t>3
H(3,n)=2^n-1
---------经证明，去x为ceil(t/2)(往上取整)或floor(t/2)往下取整时，H(t,n)最小，即最优
这个结论不对吧，应该要枚举所有的x取一个最小的做最优
H(t,n)=2H(t,x)+H(t-1,n-x) t>3
H(3,n)=2^n-1
---------经证明，去x为ceil(t/2)(往上取整)或floor(t/2)往下取整时，H(t,n)最小，即最优
这个结论不对吧，应该要枚举所有的x取一个最小的做最优
您可能感兴趣的文章:
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术，将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外，均为转载、整理或搜集自网络。欢迎任何形式的转载，转载请注明出处。
本站(WWW.)站内文章除注明原创外，均为转载、整理或搜集自网络。欢迎任何形式的转载，转载请注明出处。