这样似乎比直接递归操作效率高多了
很强大.
似乎对所有的n都可以这样计算.
这样计算F(n)分两步就可以了: n移位, 累加a 或 b
northwolves 发表于 2010-1-11 19:02 http://bbs.emath.ac.cn/images/common/back.gif
n为偶数的时候才是这样做。
当k>0的时候，10^k都是偶数，所以不用考虑n为奇数的情况。
当n为奇数的时候，好像要用
F(2n+1)=F(n)
这个式子来算。
例如计算F(99)的步骤如下：
F(99)=F(49)=F(24)
24是偶数了，这时才可以用7#的方法。
当然，直接用7#的方法也可以。
99的二进制为1100011，操作结果如下：
b,b, a,a,a, b, b
1,2,3,5,7,9,16
只要注意无论n是奇数还是偶数，一律以a的结果作为最终结果既可。
所以上述操作结果以a=7为准，忽略b=16。
所以F(99)=7。
这种奇偶互变的递归有点像3X+1问题的过程。
我觉得可能还是可解出来的，不过需要对位操作比较精通才可以。
可以参考一下Knuth的taocp卷四 位操作技巧一册。
通项公式意义不大,我觉得计算复杂度更加重要.
这个递推式如何:
记$g(n)=F(n-1)$,那么
$g(2^k*n+t)=g(2^k-t)*g(n)+g(t)*g(n+1), "where "1<=t<2^k$
本帖最后由 KeyTo9_Fans 于 2010-1-12 11:09 编辑
mathe太强大了，你是怎么想到这个递推式的？
考虑到要对长度为n的二进制序列进行操作，当n很大的时候，a和b要用高精度来表示。
如果一步一步操作的话，那么每进行一次加法，需要O(n)的时间，所以n次加法需要O(n^2)的时间。
mathe每次把二进制序列折半，然后变成两次大整数乘法运算了。
我们假设大整数乘法运算需要O(n*log(n))的复杂度。
于是根据mathe的递推式，有
T(n) = 2T(n/2)+2n*log(n)
解得 T(n) ~ O(n*(log(n))^2)
比O(n^2)快多了。
（没实现过，可能分析得不正确，大家帮忙检查一下吧）
我倒是觉得还没有这么好.实际上上面右边有4个一半长度的序列需要计算,只是它们之间关联比较密切
实际上上面的公式中通常计算g(n)和g(n+1)都要伴随出现,为此,我们总可以同时计算两个相邻的数,于是可以
${:(g(2^kn+t)=g(2^k-t)g(n)+g(t)g(n+1)),(g(2^kn+t+1)=g(2^k-t-1)g(n)+g(t+1)g(n+1)):}$
也就是计算一组2k比特的数$(g(2^kn+t),g(2^kn+t+1))$可以化为3组k比特数的计算
$(g(n),g(n+1)),(g(2^k-t),g(2^k-t-1)),(g(t),g(t+1))$
所以$T(2k)=3T(k)+O(klog(k))$,得到$T(k)~=O(k^{3//2}log(k))$
本帖最后由 KeyTo9_Fans 于 2010-1-12 17:34 编辑
谢谢mathe。我确实分析错了。
(n/2)规模的数量弄错了。
如果以4个来算，T(n)就是n^2的了。
考虑到那4个序列联系紧密，我猜想可以简化成2个，所以就没有去改了。
实际上简化成3个已经很不容易了。
连这一步我都没有做出来，还是多亏了mathe好不容易想出来的。
所以
$T(n)=3T(n/2)+O(n*log(n))$
解得
$T(n)=O(n^{log_2 3})$
其中
$log_2 3=1.585$
所以
$T(n)=O(n^{1.585})$
呵呵,我那个$n^{3/2}$也是粗心大意了.
发现函数g(n)在$2^k<n<2^{k+1}$之间最大值好像构成菲波那且数列.
为什么需要O(n^2)呢？
F(2n+1)=F(n)，所以一个奇数n可被归结到一个小于n/2的偶数
F(2n)=F(n)+F(n-1)，所以一个偶数n可被归结到一个小于n/2的奇数和小于等于n/2的偶数，亦即一个小于n/4的偶数和小于n/2的偶数
于是 T(n)<(T(n/2)+1)+(T(n/4)+2)+3
其中
T(n/4)+2 表示将n变为n/4需要两次除2操作
T(n/2)+1 表示将n变 n/2需要1次操作
最后的加3为由F(n/4)和F(n/2)求F(n)