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

solomon_007

上面讨论的那些个算法，只是猜测，没有严格证明，就可能有问题。。。

lwhjava

漂过

jimn1982

当四个人的速度分别是 1,2,3,4的时候，两种算法的时间一样，应该当速度差别很大的时候有明显的差异

jixch

要是是总共5个人时间分别是1、2、100、101、102，每次最多三人过河
这样的话，过河最少次数为2次，但是过河最短时间明显为3次
这样的话，最少次数 过河时间最短也不对了

tree_new_bee

solomon_007 发表于 2012-4-1 12:46
上面讨论的那些个算法，只是猜测，没有严格证明，就可能有问题。。。

有些东西不好证明， 但有些猜测是可以证明的。
比如说， 最慢的人必须一起过河，可以这样证明：(虽说也算不上严格)

以容量为2人为例， 我们假设有t1,t2, .... tn个人。
那么根据前面结论， 最少过河次数为(n-1)/(2-1) = n-1, 这个次数指的是单向的次数， 如果往返都算就是(n-1)*2 - 1
现在设过河时间为s
那么s = k1*t1 + k2*t2 + ... + kn*tn
因为总次数已确定， 所以k1+k2+...+kn = (n-1)*2-1
因为tn至少要过一次河，所以kn>0
要是s最小， 那么越慢的人要求过河次数越少， 所以应该kn=1， 而kn-1 = 0

kn=1,kn-1 = 0 意味着这两个人是一起过河的。

容量>2的情况也同理。

jixch

我头大了
不看了
我推算M个人每次最多3个人过河的逻辑都推得理不清了....

tree_new_bee

jixch 发表于 2012-4-1 13:27
要是是总共5个人时间分别是1、2、100、101、102，每次最多三人过河
这样的话，过河最少次数为2次，但是过河 ...

你这个例子一出来， 我后面的"证明"也就有问题了。

lastwinner

jixch 发表于 2012-4-1 13:27
要是是总共5个人时间分别是1、2、100、101、102，每次最多三人过河
这样的话，过河最少次数为2次，但是过河 ...

是的，这种时候宁肯多跑一趟
真是就怕“猪一样的队友”啊！！！！！！！！！！！！！

jixch

tree_new_bee 发表于 2012-4-1 15:15
你这个例子一出来， 我后面的"证明"也就有问题了。

jixch

lastwinner 发表于 2012-4-1 15:50
是的，这种时候宁肯多跑一趟
真是就怕“猪一样的队友”啊！！！！！！！！！！！！！

这个....
在上班啊....差点笑喷了....