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

lugionline

哦，上面的这组数据有问题

lastwinner

lugionline 发表于 2012-4-9 17:16
哦，上面的这组数据有问题

你是咋想出这些数据的？
另外我121楼的猜测，能证明不？

guostong

我觉得已经到了快走火入魔了。

newkid

lugionline 发表于 2012-4-9 15:04
没有证明的都是错误的

你试试 1,3,4,10这组数据

1 3,1,1 4,1,1 10
总共用时=19
每次都是未过河中最快的两人。
有什么问题？

lugionline

newkid 发表于 2012-4-9 21:45
1 3,1,1 4,1,1 10
总共用时=19
每次都是未过河中最快的两人。

没有问题，是我弄错了

3833020

又向上面各位大师学习了。

写一个简单的：

with t1 as (
select a.name na1, b.name nb1, c.name na2, c.time + b.time total_time, c.time
  from bridge_crossing a, bridge_crossing b, bridge_crossing c
where a.time < b.time
),
t2(na1, nb1, na2, total_time, nak, path, time) as
(
-- start with
select na1,
       nb1,
       na2,
       total_time,
       decode(na1, na2, nb1, na1) nak,
       na1 || nb1 || na2 path,
       time
  from t1
where na1 = na2
    or nb1 = na2
union all
-- 搜索路径
select t1.na1,
       t1.nb1,
       t1.na2,
       t1.total_time + t2.total_time,
       replace(t2.nak || t1.na1 || t1.nb1, t1.na2, ''),
       t2.path || '-' || t1.na1 || t1.nb1 || t1.na2 path,
       t1.time
  from t1, t2
where instr(t2.nak, t1.na1) = 0
   and instr(t2.nak, t1.nb1) = 0 and (t1.na1 = t1.na2 or t1.nb1 = t1.na2 or instr(t2.nak, t1.na2) > 0))
-- 查询结果
select substr(t2.path, 1, length(t2.path) - 1) path, total_time - time
  from t2
where length(nak) = (select count(1) - 1 from bridge_crossing)
   and total_time - time =
       (select min(total_time - time)
          from t2
         where length(nak) = (select count(1) - 1 from bridge_crossing))

newkid

楼上的写法适用于固定两人的情形；t1包含着一个笛卡尔积，回程是没有做优化的，把所有已过河的人都尝试一遍。每次递归都包含了来和回两个步骤，所以从NAK(对岸的人名单)中挑选最快的还不够，还得加上本次要过河的两人，再从中筛选出最快的。

with t1 as (
select a.name na1, b.name nb1, c.name na2, c.time + b.time total_time, c.time
   from bridge_crossing a, bridge_crossing b, bridge_crossing c
where a.time < b.time
),
t2(na1, nb1, na2, total_time, nak, path, time) as
(
-- start with
select na1,
        nb1,
        na2,
        total_time,
        cast(decode(na1, na2, nb1, na1) as varchar2(100)) nak,
        cast(na1 || nb1 || na2 as varchar2(100)) path,
        time
   from t1
where na1 = na2
     or nb1 = na2
union all
-- 搜索路径
select t1.na1,
        t1.nb1,
        t1.na2,
        t1.total_time + t2.total_time,
        replace(t2.nak || t1.na1 || t1.nb1, t1.na2, ''),
        t2.path || '-' || t1.na1 || t1.nb1 || t1.na2 path,
        t1.time
   from t1, t2
where instr(t2.nak, t1.na1) = 0
    and instr(t2.nak, t1.nb1) = 0 and (t1.na1 = t1.na2 or t1.nb1 = t1.na2 or instr(t2.nak, t1.na2) > 0)
   ------- 回程的人只考虑速度最快的
    AND t1.na2=(SELECT MIN(name) KEEP(DENSE_RANK FIRST ORDER BY time) FROM bridge_crossing b WHERE INSTR(t2.nak, b.name)>0 OR b.name IN (t1.na1,t1.nb1))
)
-- 查询结果
SELECT path,time_spent FROM (
select substr(t2.path, 1, length(t2.path) - 1) path, total_time - time as time_spent,RANK() OVER(ORDER BY total_time - time) rnk
   from t2
where length(nak) = (select count(1) - 1 from bridge_crossing)
)
WHERE rnk=1;

newkid

lugionline 发表于 2012-4-9 23:09
没有问题，是我弄错了

我已经按照如下思路写了SQL, 比原来的想法省却了X的计算，反而更简单了，当然效率上要打个折扣。欢迎你举出反例来挑战这个算法：

总共M人，每次最多过N人;
假如未过河人数<=N, 所有人过河，结束；
逐一尝试以下的人过河：未过河中最快的K人(K取值范围2~N)，或者最慢的N人（如果对岸已经没有最快的N人中的任何一个，则最慢的N人就不用尝试了）；然后然后从已过河的人中选最快的把手电送回来。

重复以上步骤。

lastwinner

newkid 发表于 2012-4-10 22:48
我已经按照如下思路写了SQL, 比原来的想法省却了X的计算，反而更简单了，当然效率上要打个折扣。欢迎你举 ...

直觉告诉我，有些时候，过不快不慢的K人会使得总时间最短，不过我数学不好没法证明真伪

newkid

lastwinner 发表于 2012-4-11 00:25
直觉告诉我，有些时候，过不快不慢的K人会使得总时间最短，不过我数学不好没法证明真伪

你的直觉是不对的，等会我有空来写一写。