一个01序列的计算题

kofeffect · 发表于 2008-4-26 15:52:16

原帖由 shshsh_0510 于 2008-4-24 20:32 发表
0
Fibonacci word

shshsh_0510说的对！^_^
有兴趣的朋友看这个link：http://en.wikipedia.org/wiki/Fibonacci_word
可以看到：
　　The n^th digit of the word is $|__(n+2)\frac{varphi}{1+2varphi}__| - |__(n+1)\frac{varphi}{1+2varphi}__|$ and $\varphi $is the golden ratio and $|__x__|$ is the floor function

mathe · 发表于 2008-4-26 18:42:20

原帖由 kofeffect 于 2008-4-26 15:16 发表
使用一个笨方法得出第100000!位的数字是0
分析规律：
设定：基为：01，生成元为：0->001 ,1->01
根： 0 1
第一层：001  01
第二层：00100101  00101
第三层：001001010010010100101  0010010100101
第四 ...

这个方法应该不对

无心人 · 发表于 2008-4-26 19:15:38

那正确的是?

mathe · 发表于 2008-4-26 20:45:26

主要是他方法中这一步：

s 值:456575

而100000!的位数是456574位

加上注意到每一层的最右边都是01，所以第100000!位数就是0

是不对的，两个位数差一位的数值差值是非常大的，所以第100000!位不在某一层的倒数第二位

mathe · 发表于 2008-4-26 20:45:59

具体数值我也没有计算过：）不过用GMP进行浮点计算并不难。

无心人 · 发表于 2008-4-26 20:48:27

哦

俺们还糊涂着呢

你们几个能不能不用黑话聊天

能详细翻译下么？

kofeffect · 发表于 2008-4-26 21:34:51

math够细心，我错了！

mathe · 发表于 2008-4-27 18:27:08

利用kofeffect找到的这个公式，解决这个问题已经不难了。我没有认真推导去确认kofeffect的公式是否正确，但是我至少知道最终结果可以写成这种形式，这个已经够了。这个题目来源于:http://blog.csdn.net/mathe/archive/2007/05/08/1600057.aspx
我稍微修改了一下，注意链接中下面zgg的评论

账号		自动登录	找回密码
密码			欢迎注册

[擂台] 一个01序列的计算题