主题：【原创】由一个简单的面试题想起的 -- 东方射日
家园 这种方法已经非常接近最佳方案了 假设这样一个方案（实际上也没有别的方案）：
先选取一些节点A_0=1<A_1<A_2<……<A_k<A_{k+1}=N，用第一个包裹依次试验这些节点，得到M所在区间A_{s-1}<=M<A_s，然后再用第二个包裹在这个区间里一个个试上去。当M遍历1——>N时，需要的总次数为
现在需要调整As和k的值使得S最小。先对As求偏导得到
2A_k=A_{k-1}+N
2A_s-A_{s+1}-A_{s-1}=1 1<s<k
2A_1=A_2+2
因此A_s=1+as-s^2/2，代入第一个方程（或者直接要求A_{k+1}=N也差不多）得到a=a(N,k)，把A_s和a代入S，得到S=S(N，k)，现在要找一个k使得S最小，对k求偏导并假设N非常大，即得k^2≈2N，S/N≈2k/3≈Sqrt(8N/9)
直接用等差数列（A_s=as+b）得到k^2≈N，S/N≈k≈Sqrt(N)。
本帖一共被 1 帖 引用 (帖内工具实现)家园 笨笨的解法是这样的 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 这个序列怎么求和？
家园 Bernoulli numbers (40)-(44)
(51)
家园 f(x，P)的定义不是很清楚 大体上应该有sum_{x=1}^{N}f(x,P)/N=G(N，P)≈F(N，P)。
f(x，P)=min{1+MAX(f(i，P-1),f(x-i-1，P))}，只要注意到f(i，P)总是i的单调递增函数，立刻就可以得到f(x，P)=1+f(i0，P-1)=1+f(x-i0-1，P)，
假设1<<i0<<x，解这两个联立方程同样可以得到
f(x，P)=(P!x)^(1/P)+c(P)+o(1)，
c(1)=0，c(P)=2-P，
i0=x^(1-1/P)*P/P!^(1/P)-x^(1-2/P)*P(P-1)/(P!)^(2/P)/2+……注意这跟前面的L(P)完全相同
对x作平均得到sum_{x=1}^{N}f(x,P)/N=A(P)N^(1/P)+c'(P)+o(1)。
c(1)=1/2，c'(P)=2-P，因此到这一阶两个结果就不同了。
家园 n^2求和 n^3-(n-1)^3=3*n^2-3*n+1
家园 刚刚算了一下，似乎有个小bug 前面都是一样的，但是
因此A_s=1+as-s^2/2这个通项公式似乎少了一点，好像应该是A_s=1+A_1*s-(s^2+s)/2
家园 牛，花！ 看来我的直觉很烂
家园 直觉上，第一个大约用[sqrt(N)+0.5]为步长 第二个再一个一个试，总可以在大约小于2*[sqrt(N)+0.5]次内找到