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

牛MAN牛

http://www.itpub.net/forum.php?m ... =1597884&extra=
求帮忙啊！

newkid

tree_new_bee 发表于 2012-3-31 16:22
上面的算法也许应该这样：
设人数M, 容量为N
1.先计算Mod(M-1, N-1),

TNB终于出手了！
你这3,4有问题，因为我们得保证第三步中每次回来的都是最快、次快这两人中的一个。

我在试图模拟56楼的步骤时有个意外收获，因为递归WITH是不允许用分析函数的，所以找下一步的TOP N记录就成了障碍，后来用其他办法绕了过去。

lastwinner

newkid 发表于 2012-3-30 04:15
N个人的做法，按照二进制位的思路也很容易写出来。

56楼的算法，碰到容量为3的就不符合了：

4个人，3个人可同时过，应最快的2个先过，最快的1个回来，然后剩下的全过去(耗时：t2+t1+t4)
5个人，3个人可同时过，应最快的3个先过，最快的1个回来，然后剩下的全过去（耗时：t3+t1+t5）
6个人，3个人可同时过，则应最快的2个先过，最快的1个回来，最慢的三个过去，次快的回来，最快的三个一起过去（耗时：t2+t1+t6+t2+t3）。当然，最快的3个先过，得到的时长是一样的

大致推测一下，首先要使来回的次数最少，然后在来回次数最少的里选择一个最优的方案，即应得到所求
假设有M个人，每次最多N个人可同时过桥，则最少来回次数为：
TURN:=ceil((M+ceil(M/N)-1)/N)

暂时想到这里。

lastwinner

changhe325 发表于 2012-3-29 19:33
从网上搜了一个结论：
1.过河时间最短的和次数最短的人先过。2.在已过的人中最短时间的人返回。3.过河时间 ...

前一段跟我43楼的演算思路没啥差别
后一段我认为不对，详见我在83楼的分析

newkid

看来答案已经呼之欲出了。
回程必在最快的两人之中，这个没有疑问；
过去的时候，奇数次选最快的X人（X=2..N之间），偶数次选最慢的N人。
现在问题是怎么确定这个X。

tree_new_bee

newkid 发表于 2012-3-31 23:26
TNB终于出手了！
你这3,4有问题，因为我们得保证第三步中每次回来的都是最快、次快这两人中的一个。

恩，写的粗糙了。 中间漏后续把最小的再送过去的步骤。

实际上，这个算法的思路是，保证每次时间最慢的人尽量多的在一起过去， 而时间快的人只是起摆渡作用而已， 而摆渡工作只需要2人足以(假设为t1,t2)， 但为了保证往返次数最少，在t1/t2过去时，可让除t1/t2外最快的人(t3,t4....)跟着过去 。

修正一下：
设人数M, 容量为N,最快的两个人为t1/t2
1.先计算Mod(M-1, N-1),
2.如果为余数为0， 则第一次装最小的N个人(t1,t2, .. tN)
如果不为0， 则装最小的"余数+1"个人 (t1,t2,.. t(余数+1))
3. 让对岸最小的回来(t1)
4. 最大的N个人过去
5. 让对岸最小的回来(t2)
6. 最小的N个人过去(t1,t2, ....)
.....
循环3..6

这样，t1和t2就有了明确分工： t1回来是为了让最慢的过河， t2回来则是为了把t1带过去。


这里有一个问题就是， 要不要让t3以及t3以后的人充当摆渡人？ 如果t3也可负责摆渡，那么第6步可改成还是最慢的N个人过去，然后t3回来接应t1/t2.  这样的方案是否一定比上面的慢？ 不好证明。或者说不同的具体数值会产生不同的最优方案？
比如说t1,t2,t3分别是1, 1.01, 1.02, 而t4以上都很大， 那么也许t3也负责摆渡效果会很好？

jixch

63楼写的
各位给个评价啊~

jixch

我发现了我写的有问题
86楼的貌似也有问题....
就像最后的：t1,t2,t3分别是1, 1.01, 1.02, 而t4以上都很大， 那么也许t3负责摆渡效果确实会更好
看来要么循环过程要加数据大小判断
再要么就只能具体情况具体分析了....

happy8650

不错哦，一般人单纯的想法，就是 19分钟的那种。o(∩_∩)o 哈哈，有点脑筋急转弯的感觉

让情伤过的心

回帖给我看到非常多的乐趣啊！