主题：【原创】由一个简单的面试题想起的 -- 东方射日

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 这个序列怎么求和？