傳說中的微軟面試題：

有一群人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>

點評：雖然這種方法有局限性，但思路還是可以的，至少能將最佳結果過濾出來！

總結

以上是生活随笔為你收集整理的四人过桥问题c语言编程,SQL趣题：四人过桥的问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。