扔石头

constant · 发表于 2006-2-24 23:02:36

前一半大家都做过，试试后一半吧。

难度：+++

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

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

husonghu · 发表于 2006-2-25 10:46:13

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

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

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

constant · 发表于 2006-2-25 18:49:27

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

野菜花 · 发表于 2006-2-26 03:11:41

Hu兄的记忆力真是惊人

，我自己都忘了曾给过递推公式

husonghu · 发表于 2006-2-26 10:51:39

所以印象深刻。

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

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

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

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

那些花儿 · 发表于 2006-2-26 12:09:44

找个一样喜欢这里的guy，然后生一个胖娃娃，为脑坛培养新的生力军

让他/她学数学，谁让花儿碰上数学就晕呢

野菜花 · 发表于 2006-2-26 19:51:37

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

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

ob · 发表于 2006-2-26 20:34:34

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

野菜花 · 发表于 2006-2-26 20:40:58

设

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次 .

野菜花 · 发表于 2006-2-26 21:01:07

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

constant · 发表于 2006-2-26 21:10:58

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

野菜花 · 发表于 2006-2-26 21:13:01

constant · 发表于 2006-2-26 21:14:14

YJJ别生气

野菜花 · 发表于 2006-2-26 21:22:03

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

那些花儿 · 发表于 2006-2-27 13:17:38

ob · 发表于 2006-2-27 21:22:12

PFPF!

		自动登录	找回密码
密码			立即注册

动态微博

扔石头

constant呀, (我不叫你康大帝哦!) 你这题要栽在菜花手里了。一年零十个月前，.......

查了一下，他们解了四块石头的情况，并且给了一个递推公式，但没有不递推的公式，所以还可以做。

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

那时正是我们从WXC浩浩荡荡大乔迁来此后的两三天，几个当事人都是重要人物，........

Hu大哥放心，花儿会.....[:>]

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

需要帮忙的话可以找菜花, 99或康师傅[:D)][:E][:))]

回复：扔石头

对独木桥大侠，YY，喵喵咪咪等开坛元勋还真挺想念的，[:((][>:D<]

革命尚未成功，Single guys 努力呀！这么好的MM可别叫别人得去

[:))][:))]

独木桥是真正的顶级高手，大约和Yaluzangbu差不多，比YJJ还要厉害一些。

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

[:O][:))][:P][>:D<]

PFPF![@};-][@};-]