靠，大家看看我这工作还有戏么？

chenpu

类似经历，也不知道最后结果会怎么样！但愿大家都好运！

cppbug

原帖由 菜地一块 于 2011-8-15 00:11 发表

就是在解决回溯类问题的时候，介绍JOSEPHUS PROBLEM时引入的，说形如
f(1) = α;
f(2n) = 2f(n) + β , for n >= 1
f(2n+1)=2f(n) + γ,  for n >= 1
的递归，

则closed form将为：
f(n) = A(n) α + B(n)β  + C(n) γ,
...

这里f(n)的close form是n的多项式，有可能含有常数项，一次项，二次项等等，因此当α,β,γ
取某个特定值时，可以使仅仅剩下n的某一项，这也就是令f(n)=1，或n，n^2, 2^n的基本出发点，当然
这个过程是一个try的过程，不见得一定成立，比如有的例子中,f(n)=n^2就可能无法成立，当你找到3个
成立的方程时，也有了三组独立的α,β,γ的值，就可以带入f(n) = A(n) α + B(n)β  + C(n) γ
来联立方程组求取A(n),B(n),C(n)的函数。这是repertoire方法求取recurrence的close form的基本思路。