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

newkid

等没新人参与了我就贴出来。
假设桥容量为两个人，总共10个人，你的做法能算出来吗？
用56楼的算法瞬间完成。

newkid

c.od <= :num 改成 c.od IN (1,2)更好，这不就是你自己的发明吗？

guostong

newkid 发表于 2012-3-30 14:22
等没新人参与了我就贴出来。
假设桥容量为两个人，总共10个人，你的做法能算出来吗？
用56楼的算法瞬间完 ...

10个人很痛苦，让我来理解一下56楼的算法

newkid

63楼更猛，相当于把56楼的方法推广到N个人，我希望楼主来论证一下。

guostong

newkid 发表于 2012-3-30 14:22
等没新人参与了我就贴出来。
假设桥容量为两个人，总共10个人，你的做法能算出来吗？
用56楼的算法瞬间完 ...

56楼算两个人确实很快

newkid

即使知道了算法，用递归SQL实现也是很有挑战，你有空玩玩！

guostong

newkid 发表于 2012-3-30 15:52
即使知道了算法，用递归SQL实现也是很有挑战，你有空玩玩！

好的，这星期每时间了，下星期再搞之

newkid

两人的很有规律，不用SQL逐步模拟也能把时间公式归纳出来，写SQL只是找乐子罢了。看看N人的如何。

tree_new_bee

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

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

56楼算法的关键点不在于开始的两个最小的先过， 而是要保证每次最大的两个过。 两个最小的先过只不过是保证大的过去后有人往回传手电筒而已。

注意到这个关键点， 你的容量为3的就容易了：
所以第一次运过去的人只负责往回送，所以只需要2个人过去
这样的操作就是：
AB ->    2
A  <-     1
ACD ->  10
共13分钟。


不过，这里也许需要根据前面的(M-1)/(N-1)的公式先判断次数， 否则，也许因为首次少装一个人导致多过一次河，就不划算了。
比如，如果是1 2 5 10 20， 每次可以3个人一起走，因为按公式需要(5-1)/(3-1）=2, 所以首次必须装满人。

tree_new_bee

tree_new_bee 发表于 2012-3-31 16:17
56楼算法的关键点不在于开始的两个最小的先过， 而是要保证每次最大的两个过。 两个最小的先过只不过是保 ...

上面的算法也许应该这样：
设人数M, 容量为N
1.先计算Mod(M-1, N-1),
2.如果为余数为0， 则第一次装最小的N个人
如果不为0， 则装最小的"余数+1"个人
3. 让对岸最小的回来
4. 最大的N个人过去
.....
循环3和4