趣味SQL：微软面试题：过河

guostong

其实返回的人可以在过河的时候来选定，可能效率要好些

guostong

guostong 发表于 2012-4-13 12:51
其实返回的人可以在过河的时候来选定，可能效率要好些

一样的，也要用到分析函数

guostong

选已经过去的人中间最快的人：

c.ps = (select min(ps) keep (DENSE_RANK FIRST ORDER BY time) from t_positions tt where bitand(tt.ps, s.ps) > 0 )


可以改成这样，不用join t_positions:
c.ps =
(
select power(2, level-1) ps
from dual
where bitand(power(2, level-1), s.ps) > 0
and bitand(power(2, level-2), s.ps) = 0
connect by power(2, level-1) <= s.ps
)

newkid

我早就叫你生成ps  的时候不要ORDER BY NAME, 改成ORDER BY TIME不就行了？然后你就可以用 SELECT MIN(...) FROM DUAL CONNECT BY了。
今天争取把我自己那个证明写完。

guostong

newkid 发表于 2012-4-13 14:33
我早就叫你生成ps  的时候不要ORDER BY NAME, 改成ORDER BY TIME不就行了？然后你就可以用 SELECT MIN(...) ...

居然写成了 order by name， 还好我的time的顺序和name相同。
#150已经改了.

guostong

-- od 已经去掉了

column name_HIST format a20;

var num number;
------ num 为每次过河的人数限制
exec :num := 3;
with
t_accessory (total_ps, cnt) as
(
     select power(2, count(1)) - 1 as ps -- 放弃total_steps
           , count(1) cnt
      from bridge_crossing  
),
t_positions (name, time, ps) as
(
    select name, time, power(2,row_number() over (order by time) -1) ps  ---- 每个人编为二进制的一位。
      from bridge_crossing
),
t_combinations ( name, ps, p_ps, time, step ) as ------- 用递归的方法生成 1~num人的所有组合，每种组合需要耗费的时间。
(
    select name, ps, ps, time, 1 step from t_positions
    union all
    select t.name||' ' || b.name, t.ps + b.ps, b.ps, greatest(t.time, b.time), step + 1
    from t_combinations t, t_positions b
    where b.ps > t.p_ps and t.step < :num
),
steps (ps, name_hist, time, step) as
---- 用递归的方法模拟过河的每一步, name: 已过河的人名单 ps:已过河的人的二进制之和，name_hist: 过河名单历史
-----time:已用总时间  step: 用了几步
(
     -- step 1
     select ps, name, time, 1
      from t_combinations where step > 1  -------- 假设第一步总是过去最多的人, 这个也有问题 (已更正，第一步过去至少2个人)
     union all
     select
        case when mod(s.step,2) = 1 then s.ps - c.ps --- 类似上面，用的是二进制的和来表示哪些人已过河。返回的扣减，过河的增加
             else s.ps + c.ps
        end ps,
        s.name_hist||','|| c.name, ----- 过河名单历史
        s.time + c.time, s.step + 1
      from steps s, t_combinations c, t_accessory a
      where s.ps <> a.total_ps  -----由s.step < a.totalsteps 改为 s.ps<>power(2, cnt) - 1
      -- back
      and (  ---------- 如果是返回，则总是单人(c.step = 1)            
             (mod(s.step,2) = 1 and bitand(s.ps, c.ps) > 0 and c.step = 1
              -- 选已经过的人中最快的人返回, 不join t_combination
and c.ps = ( select min(power(2,level-1)) from dual
                   where bitand(power(2,level-1), s.ps) > 0 and bitand(power(2,level-2), s.ps) = 0
                   connect by power(2,level-1) <= s.ps )
            )
      -- forward
            or
            (mod(s.step,2) = 0 and bitand(s.ps, c.ps) = 0
             and c.step > 1 -- 不一定过最多的人, 但至少2人
            )
          )
)
select * from
(
   select steps.name_hist, steps.time, row_number() over (order by steps.time) od
   from steps, t_accessory a
   where steps.ps = a.total_ps
) where od <= 10;

yangtingkun

昨天看到Newkid版主给我短信，发现了这道题。
明明最近忙的要死，就是忍不住手痒。
今天ITPUB大会上琢磨了一下，导致两个演讲完全没有听
坐车回来的路上想了一下，有点心得，于是晚上就写下来了

SQL> WITH C AS
  2  (SELECT NAME, TIME, POWER(2, ROWNUM - 1) POS FROM BRIDGE_CROSSING),
  3  A AS
  4  (SELECT 0 RN, A.NAME || ' ' || B.NAME NAME, GREATEST(A.TIME, B.TIME) TIME, A.POS + B.POS POS
  5  FROM C A, C B
  6  WHERE A.NAME < B.NAME
  7  UNION ALL
  8  SELECT 1, NAME, TIME, POS FROM C),
  9  B (RN, NAME, F_NAME, TIME, POS) AS
10  (SELECT 0 RN, CAST ('' AS VARCHAR2(4000)) NAME, CAST('' AS VARCHAR2(4000)) F_NAME, 0, 0 POS FROM DUAL
11  UNION ALL
12  SELECT B.RN + 1,
13     LTRIM(B.NAME || DECODE(MOD(B.RN, 2), 0, ' ', ',') || A.NAME),
14     DECODE(MOD(B.RN, 2), 0, B.F_NAME || REPLACE(A.NAME, ' ', ''), REPLACE(B.F_NAME, A.NAME, '')),
15     B.TIME + A.TIME,
16     DECODE(MOD(B.RN, 2), 0, B.POS + A.POS, B.POS - A.POS)
17  FROM B, A
18  WHERE MOD(B.RN, 2) = A.RN
19  AND DECODE(MOD(B.RN, 2), 0, BITAND(B.POS, A.POS), BITAND(B.POS - A.POS, A.POS)) = 0)
20  SELECT NAME, TIME FROM
21  (SELECT NAME, TIME, RANK() OVER(ORDER BY TIME) RN
22  FROM B
23  WHERE POS = 15)
24  WHERE RN = 1;

NAME                                 TIME
------------------------------ ----------
A B,A C D,B A B                        17
A B,B C D,A A B                        17

yangtingkun

贴上才发现，之前思路中用来判断的路径F_NAME已经不需要了，而且格式有问题，贴一个精简的：

SQL> WITH C AS
  2  (SELECT NAME, TIME, POWER(2, ROWNUM - 1) POS FROM BRIDGE_CROSSING),
  3  A AS
  4  (SELECT 0 RN, A.NAME || ' ' || B.NAME NAME, GREATEST(A.TIME, B.TIME) TIME, A.POS + B.POS POS
  5  FROM C A, C B
  6  WHERE A.NAME < B.NAME
  7  UNION ALL
  8  SELECT 1, NAME, TIME, POS FROM C),
  9  B (RN, NAME, TIME, POS) AS
10  (SELECT 0 RN, CAST ('' AS VARCHAR2(4000)) NAME, 0, 0 POS FROM DUAL
11  UNION ALL
12  SELECT B.RN + 1,
13     B.NAME || ',' || A.NAME,
14     B.TIME + A.TIME,
15     DECODE(MOD(B.RN, 2), 0, B.POS + A.POS, B.POS - A.POS)
16  FROM B, A
17  WHERE MOD(B.RN, 2) = A.RN
18  AND DECODE(MOD(B.RN, 2), 0, BITAND(B.POS, A.POS), BITAND(B.POS - A.POS, A.POS)) = 0)
19  SELECT LTRIM(NAME, ',') NAME, TIME FROM
20  (SELECT NAME, TIME, RANK() OVER(ORDER BY TIME) RN
21  FROM B
22  WHERE POS = 15)
23  WHERE RN = 1;

NAME                                 TIME
------------------------------ ----------
A B,A,C D,B,A B                        17
A B,B,C D,A,A B                        17

等过两天有时间我在博客里面简单描述一下思路。
顺便等newkid公布最佳答案

lastwinner

yangtingkun 发表于 2012-4-14 22:57
贴上才发现，之前思路中用来判断的路径F_NAME已经不需要了，而且格式有问题，贴一个精简的：

SQL> WITH  ...

22行中，POS为什么要等于15？

yangtingkun

哦，应该是power(2, 4) - 1更严谨一些