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 的大作中提到】
: 大家都知道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 的大作中提到】
: 我来说一个笨办法。
: 首先我们来分析一下：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 的大作中提到】
: 大家都知道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 的大作中提到】
: 错了，最大的到了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 的大作中提到】
: 原题并没有说到底是挪到b还是c吧？这两种情况都该考虑到啊
| b*******m
发帖数: 5492 | 7 而且通过我的算法，得出f(0,3)=15，就是最优解啊
【在 o********r 的大作中提到】
: 原体说的是从一根柱子到另一根，自然应该算最少的次数。 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 的大作中提到】
: 而且通过我的算法，得出f(0,3)=15，就是最优解啊
| o********r
发帖数: 775 | 9 对啊，你定义的f(0,n)是把n个disc从A到B的
【在 b*******m 的大作中提到】
: 而且通过我的算法，得出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 的大作中提到】
: 对啊，你定义的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 的大作中提到】
: 这个是有通项公式的
: 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 的大作中提到】
: 这个是有通项公式的
: 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 的大作中提到】
: 最少步数的通向公式:
: (1/2+sqrt(3)/6)*(1+sqrt(3))^n + (1/2-sqrt(3)/6)*(1-sqrt(3))^n - 1
|
|
