|
斐波那契数列 斐波纳契数列(Fibonacci Sequence),又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1960年代起出版了《斐波纳契数列》季刊,专门刊载这方面的研究成果。
随着数列项数的增加,前一项与后一项之比越来越逼近黄金分割的数值0.6180339887……
从第二项开始,每个奇数项的平方都比前后两项之积多1,每个偶数项的平方都比前后两项之积少1。(注:奇数项和偶数项是指项数的奇偶,而并不是指数列的数字本身的奇偶,比如第四项3是奇数,但它是偶数项,第五项5是奇数,它是奇数项,如果认为数字3和5都是奇数项,那就误解题意,怎么都说不通)
为什么会提到这个呢?还是因为这个题目:
斐波那契数列的第n项同时也代表了集合{1,2,...,n}中所有不包含相邻正整数的子集个数。
斐波那契数列(f(n),f(0)=0,f(1)=1,f(2)=1,f(3)=2……)的其他性质:
1.f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1。
2.f(1)+f(3)+f(5)+…+f(2n-1)=f(2n)。
3.f(2)+f(4)+f(6)+…+f(2n) =f(2n+1)-1。
4.[f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)·f(n+1)。
5.f(0)-f(1)+f(2)-…+(-1)^n·f(n)=(-1)^n·[f(n+1)-f(n)]+1。
6.f(m+n-1)=f(m-1)·f(n-1)+f(m)·f(n)。
利用这一点,可以用程序编出时间复杂度仅为O(log n)的程序。
斐波那契数列的整除性与素数生成性 每3个数有且只有一个被2整除,
每4个数有且只有一个被3整除,
每5个数有且只有一个被5整除,
每6个数有且只有一个被8整除,
每7个数有且只有一个被13整除,
每8个数有且只有一个被21整除,
每9个数有且只有一个被34整除,
.......
我们看到第5、7、11、13、17、23位分别是素数:5,13,89,233,1597,28657(第19位不是)
斐波那契数列的素数无限多吗?
斐波那契数列的个位数:一个60步的循环 11235,83145,94370,77415,61785.38190,
99875,27965,16730,33695,49325,72910…
斐波那契数与植物花瓣 3………………………百合和蝴蝶花
5………………………蓝花耧斗菜、金凤花、飞燕草、毛茛花
8………………………翠雀花
13………………………金盏和玫瑰
21………………………紫宛
34、55、89……………雏菊
斐波那契数还可以在植物的叶、枝、茎等排列中发现。例如,在树木的枝干上选一片叶子,记其为数0,然后依序点数叶子(假定没有折损),直到到达与那些叶子正对的位置,则其间的叶子数多半是斐波那契数。叶子从一个位置到达下一个正对的位置称为一个循回。叶子在一个循回中旋转的圈数也是斐波那契数。在一个循回中叶子数与叶子旋转圈数的比称为叶序(源自希腊词,意即叶子的排列)比。多数的叶序比呈现为斐波那契数的比。
|
|