趣题, 第8道来了。

lastwinner

1+2+...+n=n*(n+1)/2
1+2+...+n+(n+1)=(n+1)*(n+2)/2
当N between n*(n+1)/2+1 and (n+1)*(n+2)/2 时，最多需要n+1次就可以测出总共N层的楼中，碎蛋的楼层（设为f(N)）是多少，所以
f(N)=ceil(1/2*(sqrt(1+8N)-1))
解出f(N)，就可以知道对于N层大楼：

• 应该首先从f(N)开始扔第一个蛋，若碎，则从1楼开始扔第二个蛋，若不碎，则转2
• 第二次从f(N)+(f(N)-1)层开始扔第一个蛋，若碎,则从f(N)+1层开始扔第二个蛋，若不碎，则以此类推，照本次的做法，开始第三次尝试
  

由此，可以得出非常确定的规律，令A＝f(N)，如果蛋一直不碎，则测试楼层依次是
A, 2A-1, 3A-3,4A-6....
他们的差为
A-1,A-2,A-3.....
假设m*A-m*(m+1)/2层还不碎，到下一次要增加的楼层为A-m时，若增加A-m就会超过N，那么就从m*A-m*(m+1)/2＋1层开始测就行了，即便最后测出来还剩下一个蛋，总次数也不会超过A次。当然，此时最好的方案是从以N-(m*A-m*(m+1)/2)为新的N，记为N'，然后按前述公式f(N)=ceil(1/2*(sqrt(1+8N)-1))得出应从何处开始扔第一颗蛋。

tree_new_bee

newkid 发表于 2012-5-13 08:27
可能我理解有偏差，我理解是一楼肯定不碎（没有下落），所以二楼是一次。让NB哥解释一下吧。

恩，题出的有点模糊。
这里还是按照地面是0层来理解吧。也就是说1楼就会碎。

没想到这个题竟然是讨论最激烈的一道。 看来出题人太多参与，不利于讨论的气氛啊。

lugionline

newkid 发表于 2012-5-13 21:56
ORACLE版本来了。你还有什么东西是认为ORACLE做不到的？尽管往我身上招呼。

With

果然强

lastwinner

tree_new_bee 发表于 2012-5-14 07:50
恩，题出的有点模糊。
这里还是按照地面是0层来理解吧。也就是说1楼就会碎。

你的结论是错的，及时指出不对，大伙儿更有目标冲向正确结果啊！

rollingpig

newkid 发表于 2012-5-6 07:02
小伙子一表人才，怎么不学ORACLE偏去学什么SQLSERVER呢？

有什么六脉神剑，如来神掌什么的秘籍送不？

tree_new_bee

lastwinner 发表于 2012-5-15 21:00
你的结论是错的，及时指出不对，大伙儿更有目标冲向正确结果啊！

呵呵，问题是我总是不光是指出不对之处，老是喜欢将自己的理解和思路说出来。

tree_new_bee

趣题6： 不同地的6个人各自知道一条不同的消息，要使每个人都知道所有消息，如果通过一对一的打电话方式，至少要打多少次电话？ 推广到n呢？

解释一下： 通过打一次电话，两个人会把各自知道的全部消息都告诉对方。

hudingchen

趣题6：
n           f(n)
1            0
2            1
3            3
4            5
5            7
...
n            f(n)

找规律，f(n)以2为公差的等差数列
等差数列公式：
f(n) = f(k) + (n - k) * d

将k = 5,d = 2代入公式，得到
f(n) = f(5) + (n - 5) * 2

f(5) = 7,代入
f(n) = 7 + (n - 5) * 2 = 2n - 3 ,其中n >= 3

〇〇

lastwinner 发表于 2012-5-14 01:47
newkid:
.........................
以36楼为例，尝试发生在8,15,21,26,30,33

2次差分

tree_new_bee

hudingchen 发表于 2012-5-16 16:31
趣题6：
n           f(n)
1            0

前面总结的f(n)是错的。
比如f(4)<>5, 应该只要4次就可以了。
比如abcd四人， ab打一次，cd打一次， ac打一次， bd打一次。