数列通项公式

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

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)