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

lastwinner

lastwinner 发表于 2012-4-7 02:32
嗯，之前我们都犯了一个错，没人去推演一下总让最快的回来和猪结伴过河，到底哪个更快
现在有了这些实例 ...

现在的问题是，如果可以确认，这两种算法，一定能有其中之一是最佳解法，那也是一个进步，很大的进步，解题相对就容易多了

newkid

tree_new_bee 发表于 2012-4-6 09:13
对于容量为2的时候进行评估：
假设是4人， t1-t4
那么2个摆渡人时：

有没有必要考虑混合的情况?

tree_new_bee

newkid 发表于 2012-4-7 03:29
有没有必要考虑混合的情况?

不知道啊。
再往深处研究，就超出我的IQ范围了。

newkid

确实有混合的情况，比如先两人摆渡（因为后面的都很大），然后剩下不多时又变成一人摆渡，当数据分为三个不同数量级就可以构造这样的例子。

abcd9com

这个我有一个自己写的js的版本和别人写的as3版本

lugionline

这个问题状态数摆在哪里，N个人至少2^(N-1)个状态需要处理,计算量不可能比这个更小

N人每次过2个的计算量大概是：
Sum[C[N - 1, K] * C[N - 1, K + 1], {K, 0, N-2}], C 是组合函数

10人每次过两个也就做50000次加法，不应当算不出来

lastwinner

abcd9com 发表于 2012-4-7 15:13
这个我有一个自己写的js的版本和别人写的as3版本

是游戏还（出题）是解题（答案）？贴出来看看？

mengxianyao

根据过桥人数是奇数还是偶数有两种不同的递归策略

newkid

lugionline 发表于 2012-4-7 22:49
这个问题状态数摆在哪里，N个人至少2^(N-1)个状态需要处理,计算量不可能比这个更小

N人每次过2个的计算量 ...

脑细胞恢复到正常水平了吧？赶快来写一个。
不是所有状态都需要考虑的，现在过河的策略要么是最慢的N人，要么是未过河中最快的2..N人，返回肯定是最快的那个，其他组合都可以忽略。

lugionline

newkid 发表于 2012-4-9 03:15
脑细胞恢复到正常水平了吧？赶快来写一个。
不是所有状态都需要考虑的，现在过河的策略要么是最慢的N人， ...

没有证明的都是错误的

你试试 1,3,4,10这组数据