本帖最后由 happy886rr 于 2016-4-10 21:13 编辑
关注无忧公主微信号之后,看到许多奇妙问题。有几个都是关于斐波那契数列的。这个数列到底有多奇妙?百度一下才知道:斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...,即后一项等于之前两项之和。也没感觉有多奇妙,就是个普通加法,而且它的定义很怪,第0项是0,第1项是第一个1。
但是无忧公主说了斐波那契数列第 12 项为 144,是第一个包含 3 个数字的斐波那契数。那第一个包含 1000 个数字的斐波那契数,它的项数是几?我们不妨把它叫做无忧公主项数。还是编程挑战题,限于自己只会批处理,bat模拟大数又太累,字符串也不能超过1024个,无奈跑到python自学网充了下电。
Cool!,原来python这么好用啊!一个len就能表示字符串位数,这下有解了。斐波那契数我只要一个劲的加,每次判断它的位数是不是等于1000,答案不就出来了。于是按照批处理的思路写了一个python,不管它语法规范不规范了,自己也不晓得。- # Python 解无忧公主的编程挑战004:第一个1000位的斐波那契数的项数是
- F1=0;F2=1;n=1;l=1
- while l<1000:
- Fn=F1+F2;F1=F2;F2=Fn;n+=1
- l=len(str(Fn))
- print(n)
- # 偶然发现使用 while F2<10**999: 来中断循环用时最省.
复制代码 运行结果是4782,到底对不对,于是又拼了一个python用来打印斐波那契数列和它的项数、位数。- # 斐波那契数项数与位数打印
- print("斐波那契数Fn 项数n 位数")
- F1=0;F2=1;n=1
- while n<1000:
- Fn=F1+F2;F1=F2;F2=Fn;n+=1
- print(Fn,"(",n,",",len(str(Fn)),")")
复制代码 把结果保存到了txt,当我打开txt,Cool!,这些数字末端堆积的形状怎么看怎么像一条斜线。形状这么规则,不由得一惊。数字末端的位置不就是数字的长度吗,行号不就是项数吗。形状像条斜线,难不成是线性关系,无奈不会python绘图线性拟合,拿批处理线性拟合了一下,得到了一个近似关系:无忧公主项数=4.78*位数-2.39
只是近似线性关系,用这个近似公式每次求出来的结果和正确值比对不是差1就是差0,看来用数学无法描述它的准确关系。百度到python中int就可以取整,恍然大悟,用int就可以把小数部分引起的扰动过滤掉,这样就不会老是差1或不差。思路来了,最终用python结合特征根将这个线性扰动拟合描述出来了,发现网上没有任何资料介绍过这个奇妙关系。干脆起个名算了就叫 ”斐波那契-无忧公主项数定律“吧。
第一个L位的斐波那契数的项数N是:- # 斐波那契-无忧公主项数定律
- N=int((L-1+0.5*math.log10(5))/math.log10((1+5**0.5)/2))+1
-
- # 斐波那契位数估值式
- L=int((N*math.log10((1+5**0.5)/2))-math.log10(5**0.5))+1
复制代码 这下就跳过了不断的加加+...,就有了最优解法,几乎不需时间。- # 线性拟合一行流
- import math;L=1000;N=int((L-1+0.5*math.log10(5))/math.log10((1+5**0.5)/2)+1);print(N)
复制代码
|