主题:【原创】由一个简单的面试题想起的 -- 东方射日
F1(x)= 有一个包裹时x层最少试验次数
F2(x)= 有两个包裹时x层最少试验次数
F1(x)=x
F2(x)= MIN(
1+MAX(F1(1),F2(x-2)),
1+MAX(F1(2),F2(x-3)),
...,
1+MAX(F1(x-2),F2(1)))
算一算
x F1 F2
1 1 1
2 2 2
3 3 2
4 4 3
5 5 3
6 6 3
7 7 4
8 8 4
...
F2 = 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, ....
通解:
F2(x)=n
n*(n-1)/2 < x <= (n+1)*n/2
最后一个不等式对自然数很好解。
F2(10) = 4
F2(100) = 14
F2(1000) = 45
换一个角度。 这个问题是在求:
填满一颗高度为n的二叉树, 并且每条从根到叶的路径最多只能经过一条左支。
问能填多少个节点?
x= (2^n-1) - ((2^(n-2)-1) + 2(2^(n-3)-1) + 3(2^(n-4)-1)+...+(n-2)(2-1))
= (2^n-1) - (2^n -n-2-(n-1)(n-2)/2)
= n(n-1)/2
同理可推广到, 有3个包裹的问题, 等效于填一颗高度n的二叉数, 每条从根到叶的路径最多只能经过两条左支。
有y个包裹的问题, 等效于填一颗高度n的二叉数, 每条从根到叶的路径最多只能经过y-1条左支。
谁知道 1^2 + 2^2 + 3^2 + ...+ n^2 这个序列怎么求和?
- 相关回复 上下关系8
🙂这不是原因,注意前提是每层摔坏的几率相同 大洋芋 字190 2007-03-03 06:05:53
🙂噢。。我还没仔细研究算法。。。。不过,这个前提是错的。。 大大的熊 字48 2007-03-03 07:54:41
🙂这种方法已经非常接近最佳方案了 2 大洋芋 字654 2007-02-27 16:45:05
🙂笨笨的解法是这样的
🙂Bernoulli numbers 大洋芋 字78 2007-03-02 19:41:28
🙂f(x,P)的定义不是很清楚 大洋芋 字483 2007-03-02 19:36:55
🙂n^2求和 1 枸杞子 字23 2007-02-28 07:07:04
🙂刚刚算了一下,似乎有个小bug CatOH 字135 2007-02-27 21:31:51