数列通项公式

northwolves

这样似乎比直接递归操作效率高多了

KeyTo9_Fans

很强大.
似乎对所有的n都可以这样计算.
这样计算F(n)分两步就可以了: n移位, 累加a 或 b
northwolves 发表于 2010-1-11 19:02

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。

winxos

这种奇偶互变的递归有点像3X+1问题的过程。

medie2005

我觉得可能还是可解出来的，不过需要对位操作比较精通才可以。
可以参考一下Knuth的taocp卷四 位操作技巧一册。

mathe

通项公式意义不大,我觉得计算复杂度更加重要.
这个递推式如何:
记$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

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)快多了。

（没实现过，可能分析得不正确，大家帮忙检查一下吧）

mathe

我倒是觉得还没有这么好.实际上上面右边有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

谢谢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})$

mathe

呵呵,我那个$n^{3/2}$也是粗心大意了.
发现函数g(n)在$2^k<n<2^{k+1}$之间最大值好像构成菲波那且数列.

shshsh_0510

为什么需要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)