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

guostong · 发表于 2012-3-29 00:42

本帖最后由 guostong 于 2012-3-28 11:45 编辑

3人容量的测试：

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);
insert into bridge_crossing values ('F', 20);
insert into bridge_crossing values ('E', 15);
COMMIT;

结果：

NAME    PAST_NAME  BACK_NAME       TIME    STEP
---------- ---------- ---------- ---------- ----------
CDEFAB    ABCDEFAB BA                30       5
CDEFAB    ABCDEFAB AB                30       5
CDEFAB    ABCDEFAB BA                30       5
CDEFAB    ABCDEFAB AB                30       5
CDEFAB    ABCDEFAB AB                33       5
CDEFAB    ABCDEFAB BA                33       5
CDEFAB    ACDAEFAB AA                34       5
CDEFAB    ACDAEFAB AA                34       5
EFCDAB    AEFACDAB AA                34       5
EFCDAB    AEFACDAB AA                34       5
EFCDAB    BEFACDAB BA                35       5

lastwinner · 发表于 2012-3-29 01:35

lugionline 发表于 2012-3-28 10:03
记在左岸为0，在右岸为1，于是问题化为：
求状态空间 (0,0,0,0, 0) 到 (1,1,1,1, 1)的最短路径 // 前面四个 ...

又见神仙，欢迎欢迎^_^

lastwinner · 发表于 2012-3-29 01:44

guostong 发表于 2012-3-28 22:50
加上对回头的人的限制以后，效率好多了。
规定用最快两个人做回送。

对，而且第一轮回头总用最快的，第二轮回头才用次快的

若再增加一人，速度分别是1/2/5/7/10，则

1/2:2
1:1
7/10:10
2:2
————————
方案A：
1/2:2
1:1
1/5:5
总计8分钟

方案B：
2/5:5
2:2
1/2:2
总计9分钟

再次增加一人，速度分别是1/2/5/7/8/10，则
1/2:2
1:1
8/10:10
2:2
————————
接下来问题变为和四个人相似，显然1/2/5/7的行走方法应该和1/2/5/10的类似，先最快的一组过，最快的回，最慢的一组过，次快的回，最快的一组再过，即可

所以问题经过逻辑推演，就变为一组往复不断的循环操作，只不过奇偶有别而已