趣题, 第8道来了。

newkid

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

lastwinner

newkid 发表于 2012-5-13 02:21
我的第一次尝试楼层是不固定的，但我给出了对照表。如果没碎就转换为其他楼层的问题，只要查找对照表就知 ...

关键就在于第一次的尝试为什么是不固定的？不固定的话你的策略如何落地（落地即施行的意思）？

lastwinner

lugionline 发表于 2012-5-13 09:25
让你们转oracle，弄个你不好转的，嘿嘿

With

你的结果跟newkid的结果差不多
我就提一个问题，如果在29层才碎，但你们是不知道这个结果的，那你们的策略是怎样的?

lugionline

lastwinner 发表于 2012-5-13 16:38
你的结果跟newkid的结果差不多
我就提一个问题，如果在29层才碎，但你们是不知道这个结果的，那你们的策 ...

第一次的测试当然是固定的，但是后面的策略是按照测试的结果变的

36 一共实验8次

测第 8 楼
  如果碎了，那么一个蛋依次测 1-7楼
  如果没碎，那么还有2个蛋，还有9 - 36 层 共 28层楼需要测试
        测试9-36楼哪层才会碎这个问题和测试1-28楼是一样的

28 层楼需要7次才知道结果 (实际 9-36)
测第 7 楼 (实际测试在 15 楼)
  如果碎了，那么一个蛋依次测 1-6楼 (实际 9 - 14 楼)
  如果没碎，那么还有2个蛋，还有8-28 层共21层楼需要测试
        测试8-28楼哪层才会碎这个问题和测试从1-21楼是一样的

21 层楼需要6次才知道结果 (实际 16 - 36 楼)
。。。。后面的推理都是一样的


29层楼的测试肯定会发生，但是发生时很多情况都已经排除了，不需要再从29楼测试到36楼

lugionline

newkid 发表于 2012-5-13 09:39
你忘了我以前就转过你的Cross Apply了？在我们ORACLE里面用TABLE()函数。不久前我在微软的过河题目才用过。 ...

我知道能用啊，但是貌似很复杂吧，呵呵

lastwinner

lugionline 发表于 2012-5-13 20:36
第一次的测试当然是固定的，但是后面的策略是按照测试的结果变的

36 一共实验8次

第一次尝试的楼层是固定，那我就理解你的策略了

newkid

lastwinner 发表于 2012-5-13 15:05
关键就在于第一次的尝试为什么是不固定的？不固定的话你的策略如何落地（落地即施行的意思）？

为什么不是固定的？只要给定了总楼层，策略就是固定的，不管答案最终落在几楼。
如果一楼会碎，我的代码要稍微调整一下：
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(1):=1;
    DBMS_OUTPUT.PUT_LINE('1: first try:1 max try:1');
    x := 2;
    WHILE x<=36 LOOP
          lv_min := 999;
          FOR i IN 1..x-1 LOOP
              IF lv_min > GREATEST(i,1+v_egg(x-i)) THEN
                  lv_min := GREATEST(i,1+v_egg(x-i));
                  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;
/

1: first try:1 max try:1
2: first try:1 max try:2
3: first try:2 max try:2
4: first try:1 max try:3
5: first try:2 max try:3
6: first try:3 max try:3
7: first try:1 max try:4
8: first try:2 max try:4
9: first try:3 max try:4
10: first try:4 max try:4
11: first try:1 max try:5
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:1 max try:6
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:1 max try:7
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:1 max try:8
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,15,21,26,30,33
第一次固定发生在8.

newkid

lugionline 发表于 2012-5-13 20:37
我知道能用啊，但是貌似很复杂吧，呵呵

你对集合t的结果只是引用一个t.c, 所以我连table()都不用了，直接用标量子查询搞定。
你的代码和我思路完全一样，对我来说一点也不复杂。
有趣的是SQL SERVER的子查询里面超过了两层依然可以看到外层的数据。ORACLE严守ANSI的规定只能一层。它曾经也有能看到两层的版本，后来反而给改没了。

newkid

lugionline 发表于 2012-5-13 20:37
我知道能用啊，但是貌似很复杂吧，呵呵

ORACLE版本来了。你还有什么东西是认为ORACLE做不到的？尽管往我身上招呼。

With
E1(n, c) As
(
        Select 0, 0 FROM DUAL
        Union All
        Select n+1, c+1 From E1 Where n < 36
),
E2(n, c) As
(
        Select 1, Cast(LPAD(1,10) As Varchar2(2000)) FROM DUAL
        Union All
        Select E2.n + 1, E2.c || LPAD((SELECT MIN(GREATEST(1 + E1.c,1 + TO_NUMBER(SUBSTR(E2.c, (E2.n - E1.n - 1) * 10 + 1, 10))))
                                         From E1 Where E1.n > 0 And (E1.n + 1) <= (E2.n + 1)
                                       ) ,10)
        From E2
        Where E2.n < 36
)
Select E1.n, SUBSTR(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 rows selected.

lastwinner

newkid:
.........................
以36楼为例，尝试发生在8,15,21,26,30,33
第一次固定发生在8.
___________________________________________________________
偶看出新规律了——等等差数列

不要认为我写多了一个“等”字，他们的差是等差数列，所以才说等等差数列