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

newkid

对109楼的补充：
关于X的计算有这么一个上限：在N和“慢”组的组数+1 中取较小的那个。
随着“慢”组一批批过河，X的上限也会发生变化，从而影响到X的值，所以X在这个过程中是可能变化的，但可以事先算好。

newkid

109的X求法还不够严密，将F(X+1)和F(X)+F(2)比较还不够，还得考虑F(X-1)+F(3) ......等等

lugionline

56楼即使2人过河的结论也是错误的啊，比方经典24点题目 1,5,5,5

newkid

lugionline 发表于 2012-4-5 10:07
56楼即使2人过河的结论也是错误的啊，比方经典24点题目 1,5,5,5

呃！你真是找茬大师！
修改我的算法：
X不一定从2开始，可以是从1..N的数；
“快”组的人数不限于X, 可以是2..N, 这就不得不逐个尝试，事先计算的希望破灭了。算法复杂度又上升为指数级。但是 1..X-1的快组可以不考虑。
确定X的意义还在于快慢组要如何交替，当对岸没有1..X的人才需要再次输送快组。
问题是确定X的算法到底有木有？

lastwinner

靠，兔子按耐不住给射了呀

lastwinner

lugionline 发表于 2012-4-5 10:07
56楼即使2人过河的结论也是错误的啊，比方经典24点题目 1,5,5,5

印象中原题有限制条件，就是大家的速度各不一样

newkid

lastwinner 发表于 2012-4-6 00:26
印象中原题有限制条件，就是大家的速度各不一样

换成1,98,99,100 也足以推翻56的算法。

56 算法：
1+98,1,99+100,98,1+98 用时 395

最优解：
1+98,1,1+99,1,1+100 用时 299

可见让猪结伴过河不一定是最好办法。

tree_new_bee

newkid 发表于 2012-4-6 02:18
换成1,98,99,100 也足以推翻56的算法。

56 算法：

之前的帖子我曾怀疑过是否应该考虑让第三个、第四个人充当摆渡人的角色。
从最后这几个例子来看， 第二个人是否充当摆渡人的角色都要权衡。

这样，也许算法应该改成：
1. 计算确定摆渡人的数目 (如何计算是个问题?)
2. 让摆渡人都过去， 有空位的话让最大的跟着一起过去
3. 让对岸最小的回来
4. 如果摆渡人都在出发地，则摆渡人都过去(有空位的话让最大的跟着一起过去)， 否则让最大的N个人过去
5. 让对岸最小的回来
。。。

这里有两个大的问题：
1. 摆渡人的数目如何计算是个难题
2. 是否存在那种传输过程中一半路程需要某个数量的摆渡人，另一半路程需要不同数目的摆渡人，想不清楚。

tree_new_bee

对于容量为2的时候进行评估：
假设是4人， t1-t4
那么2个摆渡人时：
t1+t2
t1
t3+t4
t2
t1+t2
总和为s2= (t2+t1+t4) + 2t2+t1
1个摆渡人时(为了容易与上面对比，略微调整顺序但不影响结果)：
t1+t2
t1
t1+t4
t1
t1+t3
s1=(t2+t1+t4)+2t1+t3
两者都消去同样的项目后， s2-s1 = 2t2 - (t1+t3)
也就是说如果t2大于t1和t3的平均值，则用一个摆渡人更优， 反之则是2个摆渡人好。


5个人的时候同样：
2个摆渡人时：
t1+t2
t1
t4+t5
t2
t1+t2
t1
t1+t3

s2= (t2+t1+t5)+2t2+t1+t3
1个摆渡人时：
t1+t2
t1
t1+t5
t1
t1+t4
t1
t1+t3

s1=(t2+t1+t5)+ 2t1+t4+t3

s2-s1 = 2t2 - (t1+t4)


同样的方法， 分析6-8个人， 可以得到：
6个人
s2-s1 = 4t2 - (2t1 + t3 + t5)
7个人
s2-s1 = 4t2 - (2t1 + t6+t4)
8个人
s2-s1 = 6t2 - (3t1 + t7+t5+t3)

这样，似乎找到了规律：
假设n个人的s2-s1为diff(n),则：
diff(n) = (n|2) * 2 - ((n|2) t1 + t(n-1) + t(n-3) + ... )
(n|2) 表示n整除2


对于给定的n, 计算diff(n),如果为正， 那么应该只用一个摆渡人， 如果为负，则用两个摆渡人， 为0则两种方法都可以。

lastwinner

newkid 发表于 2012-4-6 02:18
换成1,98,99,100 也足以推翻56的算法。

56 算法：

嗯，之前我们都犯了一个错，没人去推演一下总让最快的回来和猪结伴过河，到底哪个更快
现在有了这些实例，可以推出这是不一定的，与具体的数值有关