前些天的扔玻璃球问题. 在长期置顶的<constant / fzy 脑坛数学题集汇总>有讨论

husonghu

前几天的题:www.ddhw.com

一座共100层的高楼0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">
现有2个玻璃球可以用来测试，若球摔破就不能用了。0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">
用这两个玻璃球来测试，找出从哪层掉落 玻璃球恰好摔碎（即在此层以下的楼层掉落时，玻璃球不会摔碎）0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">
问 用何种方法最有效率、最便捷？（即平均次数最少）
（假设 玻璃球在各楼层恰好掉落摔碎的几率相同）0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">
请试述其方法。0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">
www.ddhw.com

0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">constant的<扔石头>题和讨论在此:

husonghu

在这之前的讨论找不回了. 所有04年11月前的贴子都损失了.    www.ddhw.com 扔石头   上贴时间: 2006-2-24 15:2:36   文章来源: constant®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 710    现金: 179元 （更多个人信息）   用户博客地址: http://constant.ddhw.cn （11 篇） [ 回第100 页 ] [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] [ 推荐管理 ] 前一半大家都做过，试试后一半吧。 难度：+++ 有一种石头，从某一高度以上扔下来一定会碎，从这一高度以下扔下来一定不会碎。已知这一高度小于1000层楼。现在有两块这种石头，最少扔几次就一定可以测出这一高度？（准确到一层楼） www.ddhw.com 如果有4块石头呢？对任意楼层数和石头数，一般算法是什么？ 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com   constant呀, (我不叫你康大帝哦!) 你这题要栽在菜花手里了。一年零十个月前，.......   上贴时间: 2006-2-25 2:46:13   文章来源: husonghu®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 3224    现金: 822元 （更多个人信息） [ 回第100 页 ] [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] 喵喵咪咪出过此题前一部份，独木桥给了解。0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com hehe出过此题后一部份，野菜花和独木桥给了解，有过讨论。0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;"> (好题，没见过的朋友当然可以继续啦!)0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com   查了一下，他们解了四块石头的情况，并且给了一个递推公式，但没有不递推的公式，所以还可以做。   上贴时间: 2006-2-25 10:49:27   文章来源: constant®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 710    现金: 179元 （更多个人信息）   用户博客地址: http://constant.ddhw.cn （11 篇） [ 回第100 页 ] [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] hu兄怎么一年零十个月以前的题也记得？ 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com   www.ddhw.com Hu兄的记忆力真是惊人 ，我自己都忘了曾给过递推公式   上贴时间: 2006-2-25 19:11:41   文章来源: 野 菜 花®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 2768    现金: 148元 （更多个人信息）  用户博客: 58 篇 [ 回第100 页 ] [ 脑筋一动 首页 ] [ 回复此贴 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ]   Hu兄的记忆力真是惊人 ，我自己都忘了曾给过递推公式 www.ddhw.com 那时正是我们从WXC浩浩荡荡大乔迁来此后的两三天，几个当事人都是重要人物，........   上贴时间: 2006-2-26 2:51:39   文章来源: husonghu®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 3224    现金: 822元 （更多个人信息） [ 回第100 页 ] [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] 所以印象深刻。0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;"> 野菜花自不必说，风云变幻皆因君。0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com 独木桥是当时的顶级数学高手之一，在我看来，他的精湛风格很象现在的constant。因此题，喵喵咪咪对他有一句评语：“独木桥真是变态变态的聪明”。0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;"> 喵喵咪咪是此坛的开坛元勋之一，她当时还是热情的幽你一默的斑竹。她一年多前告别了顶顶，为的是“人生的重大转折”。与她类似情况的还有另一位开坛元勋丫丫。思念她们之余，尤感她们的伟大：或为事业，或为家庭，竟能完全牺牲原来的爱好而彻底转型。不过，还是盼望能重见她们的风采，即便是只再见一面也好。0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com 说不定，有一天，我们的清儿，花儿，LUTOSEATER妹妹们也会如此，不由地黯然神伤。0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com   Hu大哥放心，花儿会.....   上贴时间: 2006-2-26 4:9:44   文章来源: 那些花儿®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 2413    现金: 118元 （更多个人信息）   用户博客地址: http://nx_hua_er.ddhw.cn （13 篇） [ 回第100 页 ] [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] 找个一样喜欢这里的guy，然后生一个胖娃娃，为脑坛培养新的生力军让他/她学数学，谁让花儿碰上数学就晕呢www.ddhw.com 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com   单身的男士们，好好表现，别错失良机!!   上贴时间: 2006-2-26 11:51:37   文章来源: 野 菜 花®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 2768    现金: 148元 （更多个人信息）  用户博客: 58 篇 [ 回第100 页 ] [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] 单身的男士们，好好表现，别错失良机!! [:)][:D)]0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com     本贴由[野 菜 花]最后编辑于：2006-2-26 13:10:5   www.ddhw.com 需要帮忙的话可以找菜花, 99或康师傅   上贴时间: 2006-2-26 12:34:34   文章来源: ob®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 1992    现金: 540元 （更多个人信息） [ 回第100 页 ] [ 脑筋一动 首页 ] [ 回复此贴 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ]   需要帮忙的话可以找菜花, 99或康师傅 www.ddhw.com 回复：扔石头   上贴时间: 2006-2-26 12:40:58   文章来源: 野 菜 花®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 2768    现金: 148元 （更多个人信息）  用户博客: 58 篇 [ 回第100 页 ] [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] 设 M(r,s) 是用 r 块石头，扔 s 次, 最多可以测的楼层数。www.ddhw.com 正如 Hu 兄说的，在 2004年4月我曾给出过递推公式，独木桥在细节上作了修正，这次我又检查了一下，发现还要修正一点。以下是我现在的解答： www.ddhw.com 1。两 块 石 头 ， 扔 i 次 ， 最 多 可 测 m(2,i)[=1+2+3+...+i] 层 楼 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;"> 事实上, 先 试 i 层 楼 ， 如 果 碎 了 ， 只 剩 一 块 石 头 ， 只 好 老 老 实 实 从 第 一 层 试 起 ， 最 多 扔 (i-1) 次 就 能 测 出 哪 一 层 。 如 果 不 碎 ， 仍 有 两 块 ， 但 只 有 (i-1) 次 扔 的 机 会 ， 所 以 从 (i+i-1) 层 试 ... 所 以 m(2,i)=i+(i-1)+...+1 M(2,44)=1+2+3+...+44=990, M(2,45)=1+2+3+...+45=1035 所以，两块石头至少扔 45 次就一定可以测出哪层正好摔碎。www.ddhw.com 2。三 块 石 头 ， 扔 j 次 ， 最 多 可 测 m(3,j)=1+ Sum[1+(m(2,i)]， i from 1 to (j-1)] 层 楼 四 块 石 头 ， 扔 k 次 ， 最 多 可 测 m(4,k)=1+Sum[1+m(3,j)]， j from 1 to (k-1)] 层 楼 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com 以 此 类 推 。 。 。 4 块石头至少扔 13 次就一定可以测出哪层正好摔碎。 3。由此我只能得到这个不是递推的公式: M(4,k)=1/2* {(k-1)*(k+2)+Sum[(k-i)*(i-1)*i]} ( i is from 2 to (k-1) )   www.ddhw.com 附：我当时给的公式： 4块石头，1000层楼最少需扔12次 两 块 石 头 ， 扔 i 次 ， 最 多 可 测 m(2,i)[=1+2+3+...+i] 层 楼 三 块 石 头 ， 扔 j 次 ， 最 多 可 测 m(3,j)[=sum(m(2,i))， i from 1 to (j-1)] 层 楼 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com 四 块 石 头 ， 扔 k 次 ， 最 多 可 测 m(4,k)[=sum(m(3,j))， j from 1 to (k-1)] 层 楼 以 此 类 推 。 。 。 独木桥的修正： 野菜花的公式应作一点修改: 两 块 石 头 ， 扔 i 次 ， 最 多 可 测 m(2,i)[=1+2+3+...+i] 层 楼 三 块 石 头 ， 扔 j 次 ， 最 多 可 测 m(3,j)[=1+sum(m(2,i))， i from 1 to (j-1)] 层 楼 四 块 石 头 ， 扔 k 次 ， 最 多 可 测 m(4,k)[=1+sum(m(3,j))， j from 1 to (k-1)] 层 楼 www.ddhw.com 4块石头，1000层楼,我的计算最少需扔13次 . 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com   对独木桥大侠，YY，喵喵咪咪等开坛元勋还真挺想念的，   上贴时间: 2006-2-26 13:1:7   文章来源: 野 菜 花®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 2768    现金: 148元 （更多个人信息）  用户博客: 58 篇 [ 回第100 页 ] [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] 不过论坛本来就是很随意的，无法勉强，他们忙了一阵其他的事可能又会回来的, 希望如此吧. www.ddhw.com 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com   革命尚未成功，Single guys 努力呀！这么好的MM可别叫别人得去   上贴时间: 2006-2-26 13:10:58   文章来源: constant®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 710    现金: 179元 （更多个人信息）   用户博客地址: http://constant.ddhw.cn （11 篇） [ 回第100 页 ] [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] 花儿MM的胖娃娃一定要学数学，而且一定要转行做生意，当老板，好好为我们出气。 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com     上贴时间: 2006-2-26 13:13:1   文章来源: 野 菜 花®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 2768    现金: 148元 （更多个人信息）  用户博客: 58 篇 [ 回第100 页 ] [ 脑筋一动 首页 ] [ 回复此贴 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ]    www.ddhw.com 独木桥是真正的顶级高手，大约和Yaluzangbu差不多，比YJJ还要厉害一些。   上贴时间: 2006-2-26 13:14:14   文章来源: constant®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 710    现金: 179元 （更多个人信息）   用户博客地址: http://constant.ddhw.cn （11 篇） [ 回第100 页 ] [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] YJJ别生气www.ddhw.com 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com   别拿穷人开心了，我哪里能与你们这些顶级超级的高手同日而语呢   上贴时间: 2006-2-26 13:22:3   文章来源: 野 菜 花®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 2768    现金: 148元 （更多个人信息）  用户博客: 58 篇 [ 回第100 页 ] [ 脑筋一动 首页 ] [ 回复此贴 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ]   别拿穷人开心了，我哪里能与你们这些顶级超级的高手同日而语呢 www.ddhw.com   上贴时间: 2006-2-27 5:17:38   文章来源: 那些花儿®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 2413    现金: 118元 （更多个人信息）   用户博客地址: http://nx_hua_er.ddhw.cn （13 篇） [ 回第100 页 ] [ 脑筋一动 首页 ] [ 回复此贴 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ]    www.ddhw.com PFPF!   上贴时间: 2006-2-27 13:22:12   文章来源: ob®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 1992    现金: 540元 （更多个人信息） [ 回第100 页 ] [ 脑筋一动 首页 ] [ 回复此贴 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ]   PFPF!

husonghu

扔石头解答   上贴时间: 2006-2-28 20:29:18   文章来源: constant®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 710    现金: 179元 （更多个人信息）   用户博客地址: http://constant.ddhw.cn （11 篇） [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] [ 推荐管理 ] 有一种石头，从某一高度以上扔下来一定会碎，从这一高度以下扔下来一定不会碎。已知这一高度小于1000层楼。现在有两块这种石头，最少扔几次就一定可以测出这一高度？（准确到一层楼） 如果有4块石头呢？对任意楼层数和石头数，一般算法是什么？ 解答www.ddhw.com 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com 两块石头，扔 n 次，最多可测 S(2, n) = (1+2+3+...+n)+1 层楼 www.ddhw.com (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 = 10360||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com 所以，两块石头最少扔 45 次就一定可以测出哪层正好摔碎。www.ddhw.com  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  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当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次既可。 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com   www.ddhw.com 如果有２块石头，１０００层楼，如何使平均扔石头次数最少？最少是多少？   上贴时间: 2006-3-2 9:55:31   文章来源: npt®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 25    现金: 47元 （更多个人信息） [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] 如果有２块石头，１０００层楼，如何使平均扔石头次数最少？最少是多少？0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com   答案constant给了呀！但有点不懂你的问题的含义.......   上贴时间: 2006-3-2 11:15:54   文章来源: husonghu®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 3226    现金: 359元 （更多个人信息） [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] 一般是如constant问的：最少扔几次就一定可以测出这一高度？ (“一定可以”表示最倒霉的情况下也保证可以测出)。答案是45。0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com 你的问法中(如何使平均扔石头次数最少？),"平均"是什么含义呢?0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;"> 很难理解“平均”两字。请注意，弄不好，有可能在没测出来之前２块石头就碎完了。0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com   不知道。应该可以编程序算出来   上贴时间: 2006-3-2 14:48:26   文章来源: constant®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 710    现金: 179元 （更多个人信息）   用户博客地址: http://constant.ddhw.cn （11 篇） [ 脑筋一动 首页 ] [ 回复此贴 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ]   不知道。应该可以编程序算出来 www.ddhw.com 对不起，最近较忙，来的少。我的意思是：如果有Ｋ块石头，Ｎ层楼，最好算法的平均时间复杂度是多少？   上贴时间: 2006-3-3 21:49:53   文章来源: npt®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 25    现金: 47元 （更多个人信息） [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] 对不起，最近较忙，来的少。我的意思是：0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com 如果有Ｋ块石头，Ｎ层楼，最好算法的平均时间复杂度是多少？0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;"> Constant 给出了最坏情况下的最好时间复杂度（i.e. 最少次数) （也可能是最好的平均时间复杂度），问题是能否找出并证明这就 是最好的平均时间复杂度。0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com I had a wide guess before, it will be Ｏ（N ^ ( 1 / K ） ）。 请高手解惑。 0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com   程序算的结果如下   上贴时间: 2006-3-3 22:28:30   文章来源: constant®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 710    现金: 179元 （更多个人信息）   用户博客地址: http://constant.ddhw.cn （11 篇） [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] 程序算的结果如下：   两块石头，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  0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">     本贴由[constant]最后编辑于：2006-3-4 19:1:27

idiot94

师傅的敬仰犹如滔滔江水。。。。。

husonghu

相信他一定会回来. www.ddhw.com

idiot94

喜欢做数学题，那里很多啊，而且那边新来了几个弟兄，也都不错啊。。。此外，师傅还在万教授那里当版主，不过那里全靠他们两个人，所以出题慢了点，小小的一个沙龙，呵呵，情调独特嘛。。。

孜孜不倦@.

以每4楼递进...www.ddhw.com   www.ddhw.org---