主题:【原创】由一个简单的面试题想起的 -- 东方射日
共:💬43 🌺18
大体上应该有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,因此到这一阶两个结果就不同了。
- 相关回复 上下关系8
🙂这种方法已经非常接近最佳方案了 2 大洋芋 字654 2007-02-27 16:45:05
🙂笨笨的解法是这样的 2 老虎五 字979 2007-02-28 01:42:55
🙂Bernoulli numbers 大洋芋 字78 2007-03-02 19:41:28
🙂f(x,P)的定义不是很清楚
🙂n^2求和 1 枸杞子 字23 2007-02-28 07:07:04
🙂刚刚算了一下,似乎有个小bug CatOH 字135 2007-02-27 21:31:51
😜a=A_1-1/2 1 大洋芋 字0 2007-03-02 19:52:10
🙂Haha, i c why you use a CatOH 字36 2007-03-02 21:37:04