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

guostong

hythuyateng 发表于 2012-3-26 20:26
look this:

select  sum(times) total_time from (

没考虑回程，不对

jixch

hythuyateng 发表于 2012-3-27 09:26
look this:

select  sum(times) total_time from (

貌似不对呀
如果时间换成 1、2、9、10 结果就不对了....
1、2、9、10 最少时间应该还是 17 的
你的结果是21 ....

newkid

加菲猫的方法还是固定人数的。另外，同时过河的两人可以排序以去重复。如果不同批次之间的重复就很难预先判断了，因为不同顺序可能决定了最终结果不同。

lastwinner

印象中这个题大概三四年前在本版出现并解决过

lastwinner

Go1/2:2
Back1:1
Go5/10:10
Back2:2
Go1/2:2
Total:17
______________________________________
这种问题重要的是思路，而不是用SQL暴力蛮干，换其他语言也如是
这个问题的人数要是增加到10人，你们看看楼上的SQL改改，都要多长时间才能 写 出来，然后又要多长时间才能算出来吧！

newkid

lastwinner 发表于 2012-3-27 21:55
印象中这个题大概三四年前在本版出现并解决过

也是SQL方法？您给搜搜？
另外告诉大家一个好消息，美女贝贝已经确认本次活动将有精美沙漏作为奖品：


心动了吧？连我都想注册马甲来答题了！

solomon_007

newkid 发表于 2012-3-27 21:54
加菲猫的方法还是固定人数的。另外，同时过河的两人可以排序以去重复。如果不同批次之间的重复就很难预先判 ...

所以我说很垃圾嘛,明天通用化,再想想,你先不要给你的答案,明天给我考虑一下

lastwinner

newkid 发表于 2012-3-27 22:08
也是SQL方法？您给搜搜？
另外告诉大家一个好消息，美女贝贝已经确认本次活动将有精美沙漏作为奖品：

...

以前Jackywood喜欢搞这些，而且常常有精妙解法出现，我刚的确去搜索了一下，不过没找到

newkid

我把CONNECT BY的也写出来了，和递归大同小异，只是必须事后计算总时间。

如果把桥的容量修改一下，比如3个人以下，又会怎么样？

lugionline

记在左岸为0，在右岸为1，于是问题化为：
求状态空间 (0,0,0,0, 0) 到 (1,1,1,1, 1)的最短路径 // 前面四个表示a,b,c,d的位置，最后一个表示 电筒的位置

路径的构造很容易的(全路径去掉不在各自位置的就可以了,位操作)，一共只有 32个点

耶，问题解决了