扔石头解答

constant

有一种石头，从某一高度以上扔下来一定会碎，从这一高度以下扔下来一定不会碎。已知这一高度小于1000层楼。现在有两块这种石头，最少扔几次就一定可以测出这一高度？（准确到一层楼）

如果有4块石头呢？对任意楼层数和石头数，一般算法是什么？

解答

 www.ddhw.com

两块石头，扔 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, www.ddhw.com

S(2,45) = 1+2+3+...+45+1 = 1036www.ddhw.com

所以，两块石头最少扔 45 次就一定可以测出哪层正好摔碎。www.ddhw.com

一般问题是：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)层。

 www.ddhw.com

可以用归纳法证明，k块石头，扔n次，最多能测S(k,n) = C(n,0)+C(n,1)+C(n,2)+...+ C(n,k)  层楼。

 www.ddhw.com

当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)。www.ddhw.com

 www.ddhw.com当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次既可。

www.ddhw.com

 

npt

如果有２块石头，１０００层楼，如何使平均扔石头次数最少？最少是多少？www.ddhw.com

husonghu

一般是如constant问的：最少扔几次就一定可以测出这一高度？ (“一定可以”表示最倒霉的情况下也保证可以测出)。答案是45。www.ddhw.com 你的问法中(如何使平均扔石头次数最少？),"平均"是什么含义呢?www.ddhw.com 很难理解“平均”两字。请注意，弄不好，有可能在没测出来之前２块石头就碎完了。www.ddhw.com

constant

  不知道。应该可以编程序算出来

npt

对不起，最近较忙，来的少。我的意思是： 如果有Ｋ块石头，Ｎ层楼，最好算法的平均时间复杂度是多少？ Constant 给出了最坏情况下的最好时间复杂度（i.e. 最少次数) （也可能是最好的平均时间复杂度），问题是能否找出并证明这就 是最好的平均时间复杂度。 I had a wide guess before, it will be Ｏ（N ^ ( 1 / K ） ）。 请高手解惑。 www.ddhw.com

constant

程序算的结果如下：   两块石头，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次内结束。  www.ddhw.com     本贴由[constant]最后编辑于：2006-3-4 19:1:27