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

changhe325

newkid 发表于 2012-3-29 21:08
可恶的人肉！把我们动脑筋的乐趣都剥夺了。
即使这样，用SQL实现这个算法也是不错的练习题！

额，sorry，我看大家说的跟这个差不多了，所以就发了。。
我下次注意。

newkid

changhe325 发表于 2012-3-30 09:24
额，sorry，我看大家说的跟这个差不多了，所以就发了。。
我下次注意。

你注意到我60楼说的现象了吗？应该怎么修改？
两人的用这个算法真是无比威猛。

jixch

写了个M个人最多N个人同时过桥的判断逻辑.3个多小时的成果啊....，如下：
M个人，每次最多N个人过桥
过桥的时间从小到大依次为 T1、T2、T3、T4、T5、……、Tm

第一次过桥判断：

判断M - N是否小于N-1

M - N < N - 1

第一次过河：过桥时间最小的 M – N + 1 个人过河 时间为TM-N+1

返回：河对面（已经过河的）的 过桥时间最短的返回 时间为 T1

第二次过河：（剩下人数为： M-(M–N+1)+1 = N）没过河的N个人一次过河 时间为Tm            ------结束

M – N >= N - 1

         第一次过河：过桥时间最小的N个人过河 时间为 Tn

         返回：河对面（已经过河的）的 过桥时间最短的返回 T1

         第二次过河：过桥时间最大的N个人过河 时间为 Tm

       返回：河对面（已经过河的）的 过桥时间最短的返回 T2

       第三次过河判断：（设此时还没过河的人数为M1 = M-2N+2）

       判断 M1 - N 与 N - 1 的大小关系

                   M1 – N < N - 1

                            第三次过河：M1人中的最小的M1 – N + 1人过河

                            返回：河对面（已经过河的）的 过桥时间最短的返回 时间为T1

                            第四次过河：剩余人数为：M1-(M1-N+1)+1 = N，没过河的一起过河 时间为Tm      ------------结束

                   M1-N = N-1

                            设剩下的人的过河时间从小到大依次为T1、T2、……Tn-1、Tn、……、Tm1

                            此时河对面的（已经过河的）人群中过桥时间最短的返回 时间为T3

                            判断Tn + T1 + Tm1 与 Tm1 + T3 + max(Tn-1,T3) 的大小关系

                            Tn + T1 + Tm1 >= Tm1 + T3 + max(Tn-1,T3)

                                     第三次过河：M1个人中时间最大的N个人（Tn、……、Tm1）过河

                                     返回：河对面（已经过河的）的 过桥时间最短的返回 时间为T3

                                     第四次过河：剩余人数为：M1–N+1 = N，没过河的一起过河            ------------结束

                            Tn + T1 + Tm1 < Tm1 + T3 + max(Tn-1,T3)

                                     第三次过河：M1个人中时间最小的N个人（T1、……、Tn）过河

                                     返回：河对面（已经过河的）的 过桥时间最短的返回 时间为T3

                                     第四次过河：剩余人数为：M1–N+1 = N，没过河的一起过河           ------------结束

                   M1-N > N-1

                            第三次过河：M1个人中时间最小的N个人过河

                            返回：河对面（已经过河的）的 过桥时间最短的返回 时间为T1

                      第四次过河：没有过河的剩下人中过桥时间最大的N个人过河 时间为 Tm1

                      返回：河对面（已经过河的）的 过桥时间最短的返回

                            后面 重新执行第三次过河和第四次过河

newkid

楼上的很威武！这个算法有论证过程吗？

如果要用一个SQL来实现，我觉得会很困难，这也是乐趣所在。

guostong

桥的容量可以更改：

column name format a10;
column name_BACK format a10;
column name_HIST format a20;
var num number; -- bridge capability
exec :num := 3;

with
t_accessory (totalsteps, cnt, md) as
(
   select ceil((count(1)-1)/(:num-1)) + ceil((count(1)-1)/(:num-1)) - 1 totalsteps, count(1) cnt, mod(count(1)-1,2) md from bridge_crossing
),
t_positions (name, time, ps, od) as
(
  select name, time, power(2,row_number() over (order by name) -1) ps,
    rank() over (order by time) od
    from bridge_crossing
),
t_combinations ( name, ps, p_ps, time, step ) as
(
  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 (name, ps, name_hist, name_back, ps_back, time, step) as
(
   -- step 1
   select name,ps, name, '', 0, time, 1
    from t_combinations where step = :num
   union all
   select
      case when mod(s.step,2) = 1 then replace(s.name, c.name)
           else s.name || c.name
      end name,
      case when mod(s.step,2) = 1 then s.ps - c.ps
           else s.ps + c.ps
      end ps,
      s.name_hist || c.name,
      case when mod(s.step,2) = 1 then s.name_back || c.name
           else s.name_back
      end name_back,
      case when mod(s.step,2) = 1 then c.ps
           else 0
      end ps_back,
      s.time + c.time, s.step + 1
    from steps s, t_combinations c, t_accessory a
    where s.step < a.totalsteps
    -- back
    and (
          (mod(s.step,2) = 1 and bitand(s.ps, c.ps) > 0 and c.step = 1)
    -- forward
          or
          (mod(s.step,2) = 0 and bitand(s.ps, c.ps) = 0
           and(
                (a.totalsteps > s.step + 1 or a.totalsteps = s.step + 1 and a.md = 0 ) and c.step = :num
                or
                 a.totalsteps = s.step + 1 and a.md <> 0 and c.step < :num
                  and s.ps + c.ps = power(2, cnt) - 1
               )
          )
        )
)
select * from
(
  select steps.*, row_number() over (order by steps.time) od from steps, t_accessory t
  where step = t.totalsteps order by time
) where od <= 10;

guostong

有点问题，只对3个人同时过桥工作，正在检查

更正了。

newkid

呵呵，你终于也用BITMAP了，和我的思路基本上一样，只不过我最后一批（不满N人）是拿到递归结束后来做；你的返回部分也没有优化（最快的人返回）。

guostong

newkid 发表于 2012-3-30 13:38
呵呵，你终于也用BITMAP了，和我的思路基本上一样，只不过我最后一批（不满N人）是拿到递归结束后来做；你的 ...

加上回送的限制性能会好些
我的sql对2个人不工作了，正在查

2有点特殊，楼下更正了

guostong

加了回送的限制：

column name format a10;
column name_BACK format a10;
column name_HIST format a20;

var num number;
exec :num := 3;

with
t_accessory (totalsteps, cnt, md) as
(
   select ceil((count(1)-1)/(:num-1)) + ceil((count(1)-1)/(:num-1)) - 1 totalsteps, count(1) cnt, mod(count(1)-1,2) md from bridge_crossing
),
t_positions (name, time, ps, od) as
(
  select name, time, power(2,row_number() over (order by name) -1) ps,
    rank() over (order by time) od
    from bridge_crossing
),
t_combinations ( name, ps, p_ps, time, step, od ) as
(
  select name, ps, ps, time, 1 step, od from t_positions
  union all
  select t.name || b.name, t.ps + b.ps, b.ps, greatest(t.time, b.time), step + 1, t.od
  from t_combinations t, t_positions b
  where b.ps > t.p_ps and t.step < :num
),
steps (name, ps, name_hist, name_back, ps_back, time, step) as
(
   -- step 1
   select name,ps, name, '', 0, time, 1
    from t_combinations where step = :num
   union all
   select
      case when mod(s.step,2) = 1 then replace(s.name, c.name)
           else s.name || c.name
      end name,
      case when mod(s.step,2) = 1 then s.ps - c.ps
           else s.ps + c.ps
      end ps,
      s.name_hist || c.name,
      case when mod(s.step,2) = 1 then s.name_back || c.name
           else s.name_back
      end name_back,
      case when mod(s.step,2) = 1 then c.ps
           else 0
      end ps_back,
      s.time + c.time, s.step + 1
    from steps s, t_combinations c, t_accessory a
    where s.step < a.totalsteps
    -- back
    and (
          (mod(s.step,2) = 1 and bitand(s.ps, c.ps) > 0 and c.step = 1 and c.od <= :num)
    -- forward
          or
          (mod(s.step,2) = 0 and bitand(s.ps, c.ps) = 0
           and(
                (a.totalsteps > s.step + 1 or a.totalsteps = s.step + 1 and a.md = 0 ) and c.step = :num
                or
                 a.totalsteps = s.step + 1 and a.md <> 0 and c.step < case when :num=2 then 3 else :num end
                and s.ps + c.ps = power(2, cnt) - 1
               )
          )
        )
)
select * from
(
  select steps.*, row_number() over (order by steps.time) od from steps, t_accessory t
  where step = t.totalsteps order by time
) where od <= 10;

guostong

newkid 发表于 2012-3-30 13:38
呵呵，你终于也用BITMAP了，和我的思路基本上一样，只不过我最后一批（不满N人）是拿到递归结束后来做；你的 ...

bitmap 是个好东西
你的代码什么时候贴出来？