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

newkid · 发表于 2012-3-29 10:28

guostong 发表于 2012-3-29 10:22
此话怎讲?

DB2也有递归WITH.

你再来写一个容量不限的？比如每次最多可过:N个人。

changhe325 · 发表于 2012-3-29 14:31

guostong 发表于 2012-3-29 10:22
此话怎讲?

我之前只见过db2的递归with，以为是db2的语句呢。刚才知道是11gR2的新特性。我还停留在10g呢。

cwjl11 · 发表于 2012-3-29 16:52

好吧。。。我用最烂的方法实现了，再多个人我就要死了。。。
CREATE TABLE bridge_crossing (
      name  NUMBER PRIMARY KEY
   ,time  NUMBER
   );

INSERT INTO bridge_crossing VALUES (1, 1);
INSERT INTO bridge_crossing VALUES (2, 2);
INSERT INTO bridge_crossing VALUES (3, 5);
INSERT INTO bridge_crossing VALUES (4, 10);
COMMIT;

with b as
(select c.onecol1,c.onecol2,d.name ret
      from bridge_crossing d,
      (select a.name onecol1 ,b.name onecol2  from bridge_crossing a,bridge_crossing b where a.name<>b.name) c --组合第一次去的人
      where c.onecol1=d.name or c.onecol2=d.name
), --组合第一次去加回来的人
  c as
(select b.onecol1,b.onecol2,b.ret,g.name from bridge_crossing g,b where g.name<>(case when b.onecol1<>b.ret then b.onecol1 else b.onecol2 end))

, d as
(
select x.*,x.name second1,m.name second2  from c x,c m where x.name<>m.name
)
--组合第二次去的可能性 onecol1和onecol2代表第一次去的组合，ret代表回来的人，second1和second2代表第二次去的人
,
e as (
select d.onecol1,d.onecol2,d.ret,d.second1,d.second2 from d where
  (case when d.onecol1<>d.ret then d.onecol1 else d.onecol2 end)<>d.second1
and (case when d.onecol1<>d.ret then d.onecol1 else d.onecol2 end)<>d.second2 --这里排除不可能的情况
group by d.onecol1,d.onecol2,d.ret,d.second1,d.second2
order by d.onecol1,d.onecol2,d.ret
)
/* select * from e*/
,h as (
  select e.*, f.name ret2 from e, bridge_crossing f where f.name in ((case when e.onecol1=e.ret then e.onecol2 else e.onecol1 end),e.second1,e.second2)
),
o as (
select h.*,j.name from h ,bridge_crossing j where
/*(j.name = (case when h.onecol1=h.ret  then h.onecol1 else h.onecol2 end) and j.name= (case when h.second1=ret2 then second1 else second2 end))
and*/ j.name<>( case when h.onecol1= h.ret  then h.onecol2 else h.onecol1 end )
and (j.name = (case when ret not in (second1,second2) then ret end) or (j.name not in (onecol1,onecol2,second1,second2))) --这里最后一个人是第一次去回来后第二次没去的人，或者一次都没去的人
and j.name<>( case when h.second1= h.ret2  then h.second2 else h.second1 end )
and j.name<>h.ret2
)
select o.*, case when onecol1>onecol2 then onecol1 else onecol2 end|| ret
||case when second1>second2 then second1 else second2 end ||ret2||case when ret2>name then ret2 else name end as time,
decode(case when onecol1>onecol2 then onecol1 else onecol2 end,1,1,2,2,3,5,4,10)+ decode(ret,1,1,2,2,3,5,4,10)
+decode(case when second1>second2 then second1 else second2 end,1,1,2,2,3,5,4,10)+decode(ret2,1,1,2,2,3,5,4,10)+
decode(case when ret2>name then ret2 else name end,1,1,2,2,3,5,4,10) as sumtime
  from o
order by sumtime

结果：
1 2 1 3 4 2 1 21422 17
1 2 1 4 3 2 1 21422 17
1 2 2 3 4 1 2 22412 17
1 2 2 4 3 1 2 22412 17
2 1 1 3 4 2 1 21422 17
2 1 1 4 3 2 1 21422 17
2 1 2 3 4 1 2 22412 17
2 1 2 4 3 1 2 22412 17
1 2 1 1 3 1 4 21314 19
1 2 1 1 4 1 3 21413 19
1 2 1 3 1 1 4 21314 19
1 2 1 4 1 1 3 21413 19
1 3 1 1 2 1 4 31214 19
1 3 1 1 4 1 2 31412 19
1 3 1 2 1 1 4 31214 19
1 3 1 4 1 1 2 31412 19
1 4 1 1 2 1 3 41213 19
1 4 1 1 3 1 2 41312 19
1 4 1 2 1 1 3 41213 19

后面还有很多组合。。。不知道对不对。。

nyfor · 发表于 2012-3-29 17:06

这个问题我觉得只要速度最快的一个人作为手电筒传递人员, 就应该是最快的呀.

nyfor · 发表于 2012-3-29 17:13

nyfor 发表于 2012-3-29 17:06
这个问题我觉得只要速度最快的一个人作为手电筒传递人员, 就应该是最快的呀.

晕,我太想当然了

changhe325 · 发表于 2012-3-29 19:33

从网上搜了一个结论：
1.过河时间最短的和次数最短的人先过。2.在已过的人中最短时间的人返回。3.过河时间最长和次最长的人过河。4.在已过的人中次最短时间的人返回。5.在剩下的人中过河时间最短和次最短的人过河。。。重复以上的过程即可。

基本知识： 1.M个人过河，船上能载N个人，由于需要一人划船，故共需过河M-1N-1次（分子、分母分别减“1”是因为需要1个人划船，如果需要n个人划船就要同时减去n）； 2.“过一次河”指的是单程，“往返一次”指的是双程；3.载人过河的时候，最后一次不再需要返回。