t*****l 发帖数: 39 | 1 大家都知道Hanoi Tower游戏,给三根柱子A,B,C,n个盘子,
可以通过2^n-1步把所有的盘子移到另外一个柱子上去。
现在考虑一个限制:
移动任何一个盘子只能从A->B,B->C,C->A.
也就是说B->A,C->B,A->C不合法
问,n个盘子要多少步才能从一根柱子移到另外一根?
不需要给准确步数,给个idea怎么算就可以了 =) | b*******m 发帖数: 5492 | 2 我来说一个笨办法。
首先我们来分析一下:n个盘子,从A到C
先把n-1个盘子从A挪到C,然后把最大的从A挪到B,再把n-1个盘子从C挪到A,然后
把最大的从B挪到C,最后把n-1个盘子挪到C,完毕
然后我们来分析一下:n个盘子,从A到B
先把n-1个盘子从A挪到C,然后把最大的从A挪到B,再把n-1个盘子从C挪到B,完毕
这里面实际上有两种情况,一种是正向移动,从A到B,从B到C,从C到A;一种是反
向移动,从A到C,从C到B,从B到A。我们可以设立两个函数进行迭代,比如说f(0,n)
代表n个盘子从A到B(正向移动),f(1,n)代表n个盘子从B到A(反向移动),
那么,情况一可以简化成
f(1,n) = f(1,n-1) + 1 + f(0,n-1) + 1 + f(1,n-1)
情况二则是
f(0,n) = f(1,n-1) + 1 + f(1,n-1)
这样我们就设立了递推公式,再加上初始条件f(0,1)=1,f(1,1)=2就可以进行计算了
我没有时间继续推下去,所以只给出一个想法,不知道是否正确
【在 t*****l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 大家都知道Hanoi Tower游戏,给三根柱子A,B,C,n个盘子, : 可以通过2^n-1步把所有的盘子移到另外一个柱子上去。 : 现在考虑一个限制: : 移动任何一个盘子只能从A->B,B->C,C->A. : 也就是说B->A,C->B,A->C不合法 : 问,n个盘子要多少步才能从一根柱子移到另外一根? : 不需要给准确步数,给个idea怎么算就可以了 =)
| o********r 发帖数: 775 | 3 错了,最大的到了B就不用动了,把其他的移到B就可以了,
最笨的做法
f(n) = Number of moves needed to move n discs from one pile to another
step 1: n-1个A->C(<=2 * f(n - 1))
Step 2: 第n个A->B(1)
Step 3: n-1个C->B(<=2 * f(n - 1))
Total: Upper bound: 4*f(n-1) + 1 (O(4^n))
问题时这个办法不是最佳的,比如f(1) = 1; f(2) = 5, f(3) != 5 * 4 + 1 = 21,
instead, f(3) = 15,因为中间有些move可以被省略
但是问题是这个算法得出的不是最优的解(次数最少)。
【在 b*******m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我来说一个笨办法。 : 首先我们来分析一下:n个盘子,从A到C : 先把n-1个盘子从A挪到C,然后把最大的从A挪到B,再把n-1个盘子从C挪到A,然后 : 把最大的从B挪到C,最后把n-1个盘子挪到C,完毕 : 然后我们来分析一下:n个盘子,从A到B : 先把n-1个盘子从A挪到C,然后把最大的从A挪到B,再把n-1个盘子从C挪到B,完毕 : 这里面实际上有两种情况,一种是正向移动,从A到B,从B到C,从C到A;一种是反 : 向移动,从A到C,从C到B,从B到A。我们可以设立两个函数进行迭代,比如说f(0,n) : 代表n个盘子从A到B(正向移动),f(1,n)代表n个盘子从B到A(反向移动), : 那么,情况一可以简化成
| p*******e 发帖数: 1167 | 4 一样的啊,如果想反着挪就换个方向多挪一次
【在 t*****l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 大家都知道Hanoi Tower游戏,给三根柱子A,B,C,n个盘子, : 可以通过2^n-1步把所有的盘子移到另外一个柱子上去。 : 现在考虑一个限制: : 移动任何一个盘子只能从A->B,B->C,C->A. : 也就是说B->A,C->B,A->C不合法 : 问,n个盘子要多少步才能从一根柱子移到另外一根? : 不需要给准确步数,给个idea怎么算就可以了 =)
| b*******m 发帖数: 5492 | 5 原题并没有说到底是挪到b还是c吧?这两种情况都该考虑到啊
【在 o********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 错了,最大的到了B就不用动了,把其他的移到B就可以了, : 最笨的做法 : f(n) = Number of moves needed to move n discs from one pile to another : step 1: n-1个A->C(<=2 * f(n - 1)) : Step 2: 第n个A->B(1) : Step 3: n-1个C->B(<=2 * f(n - 1)) : Total: Upper bound: 4*f(n-1) + 1 (O(4^n)) : 问题时这个办法不是最佳的,比如f(1) = 1; f(2) = 5, f(3) != 5 * 4 + 1 = 21, : instead, f(3) = 15,因为中间有些move可以被省略 : 但是问题是这个算法得出的不是最优的解(次数最少)。
| o********r 发帖数: 775 | 6 原体说的是从一根柱子到另一根,自然应该算最少的次数。 Anyway, just my
understanding
【在 b*******m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 原题并没有说到底是挪到b还是c吧?这两种情况都该考虑到啊
| b*******m 发帖数: 5492 | 7 而且通过我的算法,得出f(0,3)=15,就是最优解啊
【在 o********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 原体说的是从一根柱子到另一根,自然应该算最少的次数。 Anyway, just my : understanding
| s****d 发帖数: 28 | 8 yes, I think your solution is right.
a little simplification:
f(0,n)=2*f(0,n-1)+2*f(0,n-2)+3
f(1,n)=2*f(1,n-1)+2*f(1,n-2)+3
f(1,n) = 1,5,15,...
f(0,n) = 2,7,15,...
They both grow in O( (1+sqrt(3))^n )
【在 b*******m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 而且通过我的算法,得出f(0,3)=15,就是最优解啊
| o********r 发帖数: 775 | 9 对啊,你定义的f(0,n)是把n个disc从A到B的
【在 b*******m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 而且通过我的算法,得出f(0,3)=15,就是最优解啊
| b*******m 发帖数: 5492 | 10 这个是有通项公式的
let g(n) = f(0,n)+5/3, then g(n) = 2*g(n-1) + 2*g(n-2),类似于菲波纳契数列
有兴趣的朋友可以把它算出来,我现在没时间检查,算错了也不好,嗬嗬
【在 o********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对啊,你定义的f(0,n)是把n个disc从A到B的
| s****d 发帖数: 28 | 11 最少步数的通向公式:
(1/2+sqrt(3)/6)*(1+sqrt(3))^n + (1/2-sqrt(3)/6)*(1-sqrt(3))^n - 1
【在 b*******m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个是有通项公式的 : let g(n) = f(0,n)+5/3, then g(n) = 2*g(n-1) + 2*g(n-2),类似于菲波纳契数列 : 有兴趣的朋友可以把它算出来,我现在没时间检查,算错了也不好,嗬嗬
| o********r 发帖数: 775 | 12 赞。
通项公式应该是:
g(n) = f(0, n) + 1, then g(n) = 2 *g(n-1) + 2*g(n-2)
有兴趣的朋友可以把它算出来,我现在没时间检查,算错了也不好,嗬嗬
【在 b*******m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个是有通项公式的 : let g(n) = f(0,n)+5/3, then g(n) = 2*g(n-1) + 2*g(n-2),类似于菲波纳契数列 : 有兴趣的朋友可以把它算出来,我现在没时间检查,算错了也不好,嗬嗬
| t*****l 发帖数: 39 | 13 答案:
B(n)=(3+2sqrt3)/6*(1+sqrt3)^n + (3-2sqrt3)/6*(1-sqrt3)^n - 1
F(n)=(9+sqrt3)/6*(1+sqrt3)^n + (9-sqrt3)/6*(1-sqrt3)^n - 3
-> O((1+sqrt3)^n) = O(2.73205^n)
【在 s****d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最少步数的通向公式: : (1/2+sqrt(3)/6)*(1+sqrt(3))^n + (1/2-sqrt(3)/6)*(1-sqrt(3))^n - 1
|
|