珍珠湾ART

标题: 扔石头 [打印本页]
作者: constant    时间: 2006-2-24 23:02
标题: 扔石头

前一半大家都做过，试试后一半吧。
难度：+++
有一种石头，从某一高度以上扔下来一定会碎，从这一高度以下扔下来一定不会碎。已知这一高度小于1000层楼。现在有两块这种石头，最少扔几次就一定可以测出这一高度？（准确到一层楼）
如果有4块石头呢？对任意楼层数和石头数，一般算法是什么？
www.ddhw.com

 
作者: husonghu    时间: 2006-2-25 10:46
标题: constant呀, (我不叫你康大帝哦!) 你这题要栽在菜花手里了。一年零十个月前，.......

喵喵咪咪出过此题前一部份，独木桥给了解。www.ddhw.com

hehe出过此题后一部份，野菜花和独木桥给了解，有过讨论。www.ddhw.com

(好题，没见过的朋友当然可以继续啦!)www.ddhw.com

 
作者: constant    时间: 2006-2-25 18:49
标题: 查了一下，他们解了四块石头的情况，并且给了一个递推公式，但没有不递推的公式，所以还可以做。

hu兄怎么一年零十个月以前的题也记得？
www.ddhw.com

 
作者: 野 菜 花    时间: 2006-2-26 03:11
标题: Hu兄的记忆力真是惊人[:O][:B]，我自己都忘了曾给过递推公式[:>]

  Hu兄的记忆力真是惊人 ，我自己都忘了曾给过递推公式




作者: husonghu    时间: 2006-2-26 10:51
标题: 那时正是我们从WXC浩浩荡荡大乔迁来此后的两三天，几个当事人都是重要人物，........

所以印象深刻。www.ddhw.com

野菜花自不必说，风云变幻皆因君。www.ddhw.com

独木桥是当时的顶级数学高手之一，在我看来，他的精湛风格很象现在的constant。因此题，喵喵咪咪对他有一句评语：“独木桥真是变态变态的聪明”。www.ddhw.com

喵喵咪咪是此坛的开坛元勋之一，她当时还是热情的幽你一默的斑竹。她一年多前告别了顶顶，为的是“人生的重大转折”。与她类似情况的还有另一位开坛元勋丫丫。思念她们之余，尤感她们的伟大：或为事业，或为家庭，竟能完全牺牲原来的爱好而彻底转型。不过，还是盼望能重见她们的风采，即便是只再见一面也好。www.ddhw.com

说不定，有一天，我们的清儿，花儿，LUTOSEATER妹妹们也会如此，不由地黯然神伤。www.ddhw.com

 
作者: 那些花儿    时间: 2006-2-26 12:09
标题: Hu大哥放心，花儿会.....[:>]

找个一样喜欢这里的guy，然后生一个胖娃娃，为脑坛培养新的生力军让他/她学数学，谁让花儿碰上数学就晕呢
www.ddhw.com

 
作者: 野 菜 花    时间: 2006-2-26 19:51
标题: 单身的男士们，好好表现，别错失良机!! [:)][:D)]

单身的男士们，好好表现，别错失良机!! [:)][:D)]www.ddhw.com

 

  本贴由[野 菜 花]最后编辑于：2006-2-26 13:10:5  

作者: ob    时间: 2006-2-26 20:34
标题: 需要帮忙的话可以找菜花, 99或康师傅[:D)][:E][:))]

  需要帮忙的话可以找菜花, 99或康师傅




作者: 野 菜 花    时间: 2006-2-26 20:40
标题: 回复：扔石头

设

M(r,s) 是用 r 块石头，扔 s 次, 最多可以测的楼层数。

正如 Hu 兄说的，在

2004年4月我曾给出过递推公式，独木桥在细节上作了修正，这次我又检查了一下，发现还要修正一点。以下是我现在的解答：

1。两 块 石 头 ， 扔 i 次 ， 最 多 可 测
m(2,i)[=1+2+3+...+i] 层 楼 www.ddhw.com

事实上, 先 试 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)] 层 楼 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) )

 

附：我当时给的公式：

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)] 层 楼 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)] 层 楼
（顶顶华闻 www.topchinesenews.com）
四 块 石 头 ， 扔 k 次 ， 最 多 可 测
m(4,k)[=1+sum(m(3,j))， j from 1 to (k-1)] 层 楼

4块石头，1000层楼,我的计算最少需扔13次 .

www.ddhw.com

 
作者: 野 菜 花    时间: 2006-2-26 21:01
标题: 对独木桥大侠，YY，喵喵咪咪等开坛元勋还真挺想念的，[:((][>:D<]

不过论坛本来就是很随意的，无法勉强，他们忙了一阵其他的事可能又会回来的, 希望如此吧.

www.ddhw.com

 
作者: constant    时间: 2006-2-26 21:10
标题: 革命尚未成功，Single guys 努力呀！这么好的MM可别叫别人得去

花儿MM的胖娃娃一定要学数学，而且一定要转行做生意，当老板，好好为我们出气。
www.ddhw.com

 
作者: 野 菜 花    时间: 2006-2-26 21:13
标题: [:))][:))]

  




作者: constant    时间: 2006-2-26 21:14
标题: 独木桥是真正的顶级高手，大约和Yaluzangbu差不多，比YJJ还要厉害一些。

YJJ别生气
www.ddhw.com

 
作者: 野 菜 花    时间: 2006-2-26 21:22
标题: 别拿穷人开心了，我哪里能与你们这些顶级超级的高手同日而语呢[:>][:P]

  别拿穷人开心了，我哪里能与你们这些顶级超级的高手同日而语呢




作者: 那些花儿    时间: 2006-2-27 13:17
标题: [:O][:))][:P][>:D<]

  




作者: ob    时间: 2006-2-27 21:22
标题: PFPF![@};-][@};-]

  PFPF!








欢迎光临 珍珠湾ART (http://zzwav.com/) Powered by Discuz! X3