两块石头，扔 n 次，最多可测 S(2, n) = (1+2+3+...+n)+1 层楼
document.write(String.fromCharCode(119,119,119,46,84,111,112,67,104,105,110,101,115,101,78,101,119,115,46,99,111,109));
先试 n 层楼，如果碎了，只剩一块石头，只好老老实实从第一层试起，最多扔 (n-1) 次就能测出哪一层。如果不碎，仍有两块，但只有(n-1) 次扔的机会，所以从 (n+n-1) 层试 ... 所以S(2, n)= n+(n-1)+...+1+1。最后一个加1是因为最高一层不用测。
S(2,44) = 1+2+3+...+44+1 = 991,
S(2,45) = 1+2+3+...+45+1 = 1036
所以，两块石头最少扔 45 次就一定可以测出哪层正好摔碎。
一般问题是：k块石头，扔n次，（n>=k）最多能测几层楼？这个问题的解和一个看起来完全不同的题一样：在k维空间中，n 个k-1维超平面最多能把空间分成多少部分？这两个问题都满足递归关系S(k+1, n+1) = S(k+1, n) + S(k, n)：如果第一颗石头第一次碎了，为了使剩下的k颗石头能测出第几层高度会碎，第一颗石头的第一次测试不能超过S(k, n)层高，如果第一颗石头不碎，上面还可以再测S(k+1, n)层。
可以用归纳法证明，k块石头，扔n次，最多能测S(k,n) = C(n,0)+C(n,1)+C(n,2)+...+ C(n,k) 层楼。
当k=1时，S(1, n) = n+1，结论显然成立。当n=k时，S(n,n) = 2^n = C(n,0)+C(n,1)+C(n,2)+...+ C(n,n)。对一般的k与n，S(k+1, n+1) = S(k+1, n) + S(k, n) = )=(C(n,0)+C(n,1)+…+C(n,k)+ C(n,k+1)) + (C(n,0)+C(n,1)+…+C(n,k)) = C(n+1,0)+C(n+1,1)+…+C(n+1,k)+C(n+1,k+1)。
当k=4，n=13时， S(4,13) = C(13,0)+C(13,1)+C(13,2) +C(13,3)+C(13,4) = 1+13+78+286+715=1093，故对1000层的高楼，用4颗石头，测13次既可。
如果有２块石头，１０００层楼，如何使平均扔石头次数最少？最少是多少？ |
一般是如constant问的：最少扔几次就一定可以测出这一高度？ (“一定可以”表示最倒霉的情况下也保证可以测出)。答案是45。 你的问法中(如何使平均扔石头次数最少？),"平均"是什么含义呢? 很难理解“平均”两字。请注意，弄不好，有可能在没测出来之前２块石头就碎完了。 |
对不起，最近较忙，来的少。我的意思是： 如果有Ｋ块石头，Ｎ层楼，最好算法的平均时间复杂度是多少？ Constant 给出了最坏情况下的最好时间复杂度（i.e. 最少次数) I had a wide guess before, it will be Ｏ（N ^ ( 1 / K ） ）。 |
程序算的结果如下： 两块石头，n 层楼，第一次在第 [sqr(n)] 层扔。期望值为一个分母为n的分数。当 n = k(k+1) 时，分子为 n(n+1)(8n+1)/6 - 1，n 在 k(k-1) 和 k(k+1) 之间时，前k个每个增长 2k-1，后k个每个增长 2k。n = 1000 时分子为41671，即期望值为41.671，第一次在31层楼扔。 这个最佳方法并不能保证在45次内结束。 本贴由[constant]最后编辑于：2006-3-4 19:1:27 |
| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |