ITPub博客

首页 > Linux操作系统 > Linux操作系统 > SQL趣题:四人过桥的问题

SQL趣题:四人过桥的问题

原创 Linux操作系统 作者:0x0x0x 时间:2012-06-26 14:41:06 0 删除 编辑
传说中的微软面试题:
有一群人A,B,C,D (人数>=2)要在夜里走过独木桥过河,他们只有一把手电筒。四个人的速度不同,
过河分别需要1,2,5,10分钟,桥上最多走两个人,两个人一起走时按速度慢的计算。过河一定要用手电筒。
请问最快的方法是如何安排,需要几分钟?
例子输出:
A B,A,A C,A,A D  19
表示:
A B 过去 2 分钟
A   返回 1 分钟
A C 过去 5 分钟
A   返回 1 分钟
A D 过去 10 分钟
这个例子总共用19分钟。
CREATE TABLE bridge_crossing (
       name  VARCHAR2(10) PRIMARY KEY
      ,time  NUMBER
      );
     
INSERT INTO bridge_crossing VALUES ('A', 1);
INSERT INTO bridge_crossing VALUES ('B', 2);
INSERT INTO bridge_crossing VALUES ('C', 5);
INSERT INTO bridge_crossing VALUES ('D', 10);
COMMIT;

以下是我的实现方法:
SQL> set timing on;
SQL> with t as
  2  (select rownum rn,t.name,t.time from bridge_crossing t),
  3  tt as (select t1.name n1,t2.name n2,t3.name n3,t4.name n4,t5.name n5,t6.name n6,
  4  t1.time time1,t2.time time2,t3.time time3,t4.time time4,t5.time time5,t6.time time6,
  5  greatest(t1.time,t2.time)+least(t1.time,t2.time)+
  6  greatest(t3.time,t4.time)+
  7  least(greatest(t1.time,t2.time),t3.time,t4.time)+
  8  greatest(t5.time,t6.time) sum_time
  9  from t t1,t t2,t t3,t t4,t t5,t t6
10  where t1.name<>t2.name and t3.name<>t4.name and t5.name<>t6.name
11  and t1.rn12  and instr(t1.name||t2.name||t3.name||t4.name||t5.name||t6.name,'A',1,1)>0
13  and instr(t1.name||t2.name||t3.name||t4.name||t5.name||t6.name,'B',1,1)>0
14  and instr(t1.name||t2.name||t3.name||t4.name||t5.name||t6.name,'C',1,1)>0
15  and instr(t1.name||t2.name||t3.name||t4.name||t5.name||t6.name,'D',1,1)>0
16  and t1.name||t2.name<>t3.name||t4.name
17  and t3.name||t4.name<>t5.name||t6.name),
18  ttt as (select min(sum_time) min_time from tt)
19  select n1,n2,n3,n4,n5,n6,sum_time from tt,ttt where tt.sum_time=ttt.min_time
20  /
N1         N2         N3         N4         N5         N6           SUM_TIME
---------- ---------- ---------- ---------- ---------- ---------- ----------
A          B          C          D          A          B                  17
已用时间:  00: 00: 00.09
SQL>

点评:虽然这种方法有局限性,但思路还是可以的,至少能将最佳结果过滤出来!
 
 
 
 

 

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/26977915/viewspace-733824/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2012-06-26

  • 博文量
    35
  • 访问量
    92200