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

newkid

lastwinner 发表于 2012-4-1 15:50
是的，这种时候宁肯多跑一趟
真是就怕“猪一样的队友”啊！！！！！！！！！！！！！

精P!  ^_^

xgghxkhuang

我试验了用model去完成这个任务，好像不行，newkid的解法是用递归with吗？
期待看newkid的解法。

newkid

xgghxkhuang 发表于 2012-4-2 10:56
我试验了用model去完成这个任务，好像不行，newkid的解法是用递归with吗？
期待看newkid的解法。

我和65楼的写法很像；
另有一种写法是对56楼的算法的逐步模拟（直接归纳公式又是另外的写法了），这个比较有意思，因为递归SQL里面不允许用分析函数求TOP N. 但我钻了个空子，因为这个TOP N最终还是合并为一行，所以可以用LISTAGG弄出来。看看有没有人搞出类似的写法。

newkid

当每组限定两人时，用56楼方法归纳公式如下：

SELECT LISTAGG(CASE WHEN grp>1 THEN name1||' '||name2||','||name1||','||grp_name1||' '||grp_name2||','||name2 ---- 每组人员构成：最快两(往)+最快的人(返)+本组两人(往)+第二快的人(返)
                    WHEN MOD(cnt,2)=0 THEN name1||' '||name2  ------- 最后一组，人数为奇偶则稍有不同
                    ELSE name1||' '||name2||','||name1||','||name1||' '||grp_name2
               END,',') WITHIN GROUP (ORDER BY -grp) names
      ,SUM(CASE WHEN grp>1 THEN time2+time1+grp_time+time2 ---- 每组时间构成：最快两人用时(往)+最快的人用时(返)+本组用时(往)+第二快的人用时(返)
                WHEN MOD(cnt,2)=0 THEN time2     ------- 最后一组，人数为奇偶则稍有不同
                ELSE time2+time1+grp_time
           END) total_time
  FROM (SELECT grp,name1,name2,time1,time2,MAX(time) grp_time,MIN(name) grp_name1,MAX(name) grp_name2,cnt
          FROM (SELECT t.*
                      ,MAX(CASE WHEN rn=1 THEN name END) OVER() name1    ---- 最快的人的姓名
                      ,MAX(CASE WHEN rn=2 THEN name END) OVER() name2    ---- 第二快的人的姓名
                      ,MAX(CASE WHEN rn=1 THEN time END) OVER() time1    ---- 最快的人所用时间
                      ,MAX(CASE WHEN rn=2 THEN time END) OVER() time2    ---- 第二快的人所用时间
                      ,CASE WHEN MOD(cnt,2)=0 THEN CEIL(rn/2) ELSE FLOOR(rn/2) END  grp   ---- 把所有人从速度最慢的开始两两分组
                  FROM (SELECT b.*
                              ,ROW_NUMBER() OVER(ORDER BY time) rn
                              ,COUNT(*) OVER() cnt
                          FROM bridge_crossing b
                        ) t
                )
        WHERE grp>0  ---- 当人数为奇数时会出现最快的人单独一组，这组不算，最后一次渡河是第一人和第三人
        GROUP BY grp,name1,name2,time1,time2,cnt
        );

虽然写法比较复杂，但难度不大，也用不着递归，因为每组的构成都是可以事先算出来的。

如果每组限定N人，则“慢”组过河为N人，“快”组过河人数不定，取决于后面的人和第二快的人的速度差异，到底多摆渡一次是否合算？这个算法暂时还没搞清楚。

xgghxkhuang

newkid厉害，本贴应该可以申请精华贴了，newkid能具体讲解一下104楼的帖子算法吗？等待newkid的讲解。

lastwinner

newkid 发表于 2012-4-3 02:40
当每组限定两人时，用56楼方法归纳公式如下：

SELECT LISTAGG(CASE WHEN grp>1 THEN name1||' '||name2| ...

56楼的这个结论是错的，不知你有无在代码中用到这一点？

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

复制代码

很明显，但M＝5而N＝2时，4次是不可能过去的，看我43楼的推演就知道最少要7次(单程)

而我83楼的公式是计算来回程多少次的

1. 假设有M个人，每次最多N个人可同时过桥，则最少来回次数为：
   
2. TURN:=ceil((M+ceil(M/N)-1)/N)

复制代码

TURN:=ceil((M+ceil(M/N)-1)/N)＝ceil((5+ceil(5/2)-1)/2)=4
由于最后一次一定是过去，因此4*2-1=7次就可以完成过河，与实际推演的7次一致

lastwinner

xgghxkhuang 发表于 2012-4-3 19:20
newkid厉害，本贴应该可以申请精华贴了，newkid能具体讲解一下104楼的帖子算法吗？等待newkid的讲解。

还差一点，只要解决了N>=3的……

newkid

我用的是56楼的上半截，我的次数（最少，不一定最优）公式是：CEIL((M-1)/(N-1))*2-1

给xgghxkhuang的解释：看一个例子就清楚了。假设有10人按速度编号1-10, 则过河顺序为：
1 2,1,9 10,2,1 2,1,7 8,2,1 2,1,5 6,2,1 2,1,3 4,2,1 2  ---- 人数为偶数的情况

假设人数为奇数，不妨看1-9的例子，
1 2,1,8 9,2,1 2,1,6 7,2,1 2,1,4 5,2,1 2,1,1 3

所以这个过程就是不断从尾部减去两人；每个步骤相当于在前面拼上 1 2,1, 后面拼上2, 比如：1 2,1,7 8,2 就是以7和8为一组的例子。

我在85楼的思路也想得差不多了，等会看有没有时间整理出来。

newkid

85楼提到一个未知数X, X 为2..N之中的一个数。假设我们已经知道了这个X, 则过河步骤为：

如果未过河的人数<=N: 全部过河，结束；
假如对岸有1~X（最快的X人）中的人：选最慢的N人过河，然后从已过河的人中选最快的（此人必在1~X中）把手电送回来；
假如对岸没有1~X中的人，则分两种情况：
    剩下人数>X+N: 让1~X过河，然后最快的（第1号）把手电送回；
    剩下人数 C<=X+N: 让1~(C-N) 过河，然后最快的（第1号）把手电送回。

重复以上步骤。

X的确定：X这组人属于“快”组，他们的任务是回送手电。X人过河后，总共可以回送X次，其中第一次是自己的开销，其他X-1次是为“慢”组服务的。

现在我们要根据X的成本F(X)，从中找出最佳的X。X的上限为：在N和“慢”组的组数+1 中取较小的那个。

F(2)=T2+T1+T2  ---- 共可服务1组
F(X)=TX+T1+T2+...+TX --- 共可服务X-1组
F(X+1)=T(X+1)+T1+T2+...+T(X+1) --共可服务X组

从X=2开始，把F(X+1)和F(X)+F2 (同样可服务X组)比较，如果F(X+1)较小则X:=X+1继续; 否则，我们已经找到了最佳的X。

请各位砖家拍砖。如果这算法得以成立，写成SQL也是够忙活一通的，仍然可以不用递归；用递归只是为了试验那个TOP N技巧。

lastwinner

newkid 发表于 2012-4-3 22:23
我用的是56楼的上半截，我的次数（最少，不一定最优）公式是：CEIL((M-1)/(N-1))*2-1

给xgghxkhuang的解 ...

你这个公式是没问题的
我83楼推的那个有点问题
  1  with t as (select rownum+1 r from dual connect by rownum<9)
  2  , t1 as (select a.r m, b.r n from t a, t b where a.r>=b.r*2)
  3* select M, N, ceil((M+ceil(M/N)-1)/N) lw, CEIL((M-1)/(N-1))*2-1 nk from t1
SQL> /

         M          N         LW         NK
---------- ---------- ---------- ----------
         4          2          3          5
         5          2          4          7
         6          2          4          9
         7          2          5         11
         8          2          6         13
         9          2          7         15
         6          3          3          5
         7          3          3          5
         8          3          4          7
         9          3          4          7
         8          4          3          5
         9          4          3          5

————————————————————————
我的红字那几行有问题，羞愧～～