趣题, 第8道来了。

newkid

明白了题意是求最大次数就很好办了，假设第一次在N层，如果碎了，则最大次数为N-1; 如果不碎，则题目变为 36-N+1层楼的问题了。
F(36)=GREATEST(N-1, F(36-N+1)+1)
递归出口F(2)=1, 对N逐一尝试，写个小程序应该很简单。任意楼层也有希望。
N是变化的，不一定固定为6。

newkid

DECLARE
   TYPE t_egg IS TABLE OF NUMBER INDEX BY PLS_INTEGER;
   v_egg t_egg;
   lv_min NUMBER;
   x NUMBER;
   lv_first NUMBER;
BEGIN
   v_egg(2):=1;
   x := 3;
   WHILE x<=36 LOOP
         lv_min := 999;
         FOR i IN 2..x-1 LOOP
             IF lv_min > GREATEST(i-1,1+v_egg(x-i+1)) THEN
                 lv_min := GREATEST(i-1,1+v_egg(x-i+1));
                 lv_first := i;
             END IF;
         END LOOP;
         v_egg(x):=lv_min;
         DBMS_OUTPUT.PUT_LINE(x||': first try:'||lv_first||' max try:'||v_egg(x));
         x := x+1;
   END LOOP;
END;
/


3: first try:2 max try:2
4: first try:3 max try:2
5: first try:2 max try:3
6: first try:3 max try:3
7: first try:4 max try:3
8: first try:2 max try:4
9: first try:3 max try:4
10: first try:4 max try:4
11: first try:5 max try:4
12: first try:2 max try:5
13: first try:3 max try:5
14: first try:4 max try:5
15: first try:5 max try:5
16: first try:6 max try:5
17: first try:2 max try:6
18: first try:3 max try:6
19: first try:4 max try:6
20: first try:5 max try:6
21: first try:6 max try:6
22: first try:7 max try:6
23: first try:2 max try:7
24: first try:3 max try:7
25: first try:4 max try:7
26: first try:5 max try:7
27: first try:6 max try:7
28: first try:7 max try:7
29: first try:8 max try:7
30: first try:2 max try:8
31: first try:3 max try:8
32: first try:4 max try:8
33: first try:5 max try:8
34: first try:6 max try:8
35: first try:7 max try:8
36: first try:8 max try:8

在总共36层的情况下，第一次尝试8楼，如果没碎把8楼当作1楼，剩下当作29层处理。最多8次。

lastwinner

newkid 发表于 2012-5-12 09:52
DECLARE
   TYPE t_egg IS TABLE OF NUMBER INDEX BY PLS_INTEGER;
   v_egg t_egg;

你这个策略是不固定的
应该求出first try同样的时候， 最大的max try是比所有其他first try分组中最大的max try还要小

lugionline

第五题是经典题目，是有现成答案的，用DP的思想，这种题目再去发明一遍DP思想可能不是每个人都能做到的

newkid

lastwinner 发表于 2012-5-12 15:15
你这个策略是不固定的
应该求出first try同样的时候， 最大的max try是比所有其他first try分组中最大的 ...

我的第一次尝试楼层是不固定的，但我给出了对照表。如果没碎就转换为其他楼层的问题，只要查找对照表就知道下一层应该是什么。如果碎了就很简单，从上次没碎的那层开始尝试。这难道不是一种策略？
你的意思我看不懂，修改后应该是怎么样？

newkid

lugionline 发表于 2012-5-12 17:41
第五题是经典题目，是有现成答案的，用DP的思想，这种题目再去发明一遍DP思想可能不是每个人都能做到的

呵呵，我生得早没有运气接受奥数,OI，动态规划什么的培训，你这种专业选手就负责指导好了。

lugionline

2层需要2次测试才行，
测一层可能不破，还要测一次
测二层可能破，仍然要测一次

最讨厌奥数了，尤其是小学奥数，一群猪头老师就看了几本参考书去害小孩，不光骗了钱还浪费人家好多时间，其实很多东西后面系统学习后都变成很容易的事，幸好我没学过奥数

newkid

lugionline 发表于 2012-5-13 08:20
2层需要2次测试才行，
测一层可能不破，还要测一次
测二层可能破，仍然要测一次

可能我理解有偏差，我理解是一楼肯定不碎（没有下落），所以二楼是一次。让NB哥解释一下吧。

lugionline

让你们转oracle，弄个你不好转的，嘿嘿

With
E1(n, c) As
(
        Select 0, 0
        Union All
        Select n+1, c+1 From E1 Where n < 36
),
E2(n, c) As
(
        Select 1, Cast(Cast(1 As Char(10)) As Varchar(max))
        Union All
        Select E2.n + 1, Cast(E2.c + Cast(T.c As Char(10)) As Varchar(max))
        From E2 Cross Apply
        (
                Select f, Case When c1 > c2 Then c1 Else c2 End c,
                        row_number() Over (Order By Case When c1 > c2 Then c1 Else c2 End) r
                From
                (   -- 需要计算第(E2.n+1)层，从1层到n+1层测试
                        Select E1.n + 1 f, -- 在E1.n + 1层测试
                                1 + E1.c c1, -- 破了，那么一层一层测
                                -- 否则没破，还有两个蛋, 还有E2.n + 1 - (E1.n + 1)层需要测几次
                                1 + Cast(Substring(E2.c, (E2.n - E1.n - 1) * 10 + 1, 10) As Int) c2
                        From E1 Where E1.n > 0 And (E1.n + 1) <= (E2.n + 1)
                ) S
        ) T
        Where E2.n < 36 And T.r = 1
)
Select E1.n, Substring(E2.c, (E1.n - 1) * 10 + 1, 10) c
        From E1, E2 Where E2.n = 36 And E1.n > 0


n           c
-----------
1           1         
2           2         
3           2         
4           3         
5           3         
6           3         
7           4         
8           4         
9           4         
10          4         
11          5         
12          5         
13          5         
14          5         
15          5         
16          6         
17          6         
18          6         
19          6         
20          6         
21          6         
22          7         
23          7         
24          7         
25          7         
26          7         
27          7         
28          7         
29          8         
30          8         
31          8         
32          8         
33          8         
34          8         
35          8         
36          8         

(36 row(s) affected)

其实这个数列看规律应当直接可以出通项公式，懒得写了，人家早研究过了，1个1，2个2，3个3....

newkid

你忘了我以前就转过你的Cross Apply了？在我们ORACLE里面用TABLE()函数。不久前我在微软的过河题目才用过。
周末没时间，下周一吧。