废都物语狼女:斐波那契数列
来源:百度文库 编辑:偶看新闻 时间:2024/05/08 03:56:37
斐波那契数列
斐波纳契数列(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年代起出版了《斐波纳契数列》季刊,专门刊载这方面的研究成果。
编辑本段定义
斐波那契数列的发明者,是意大利数学家列昂纳多·斐波那契(Leonardo Fibonacci,生于公元1170年,卒于1240年,籍贯大概是比萨)。他被人称作“比萨的列昂纳多”。1202年,他撰写了《珠算原理》(Liber Abacci)一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事,派驻地点相当于今日的阿尔及利亚地区,列昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯研究数学。 斐波那契数列指的是这样一个数列:1、1、2、3、5、8、13、21、…… 这个数列从第三项开始,每一项都等于前两项之和。斐波那契数列通项公式
通项公式
(见图)(又叫“比内公式”,是用无理数表示有理数的一个范例。) 注:此时a1=1,a2=1,an=a(n-1)+a(n-2)(n>=3,n∈N*)通项公式的推导
斐波那契数列:1、1、2、3、5、8、13、21、…… 如果设F(n)为该数列的第n项(n∈N+)。那么这句话可以写成如下形式: F(0) = 0,F(1)=1,F(n)=F(n-1)+F(n-2) (n≥2), 显然这是一个线性递推数列。 方法一:利用特征方程(线性代数解法) 线性递推数列的特征方程为: X^2=X+1 解得 X1=(1+√5)/2,,X2=(1-√5)/2。 则F(n)=C1*X1^n + C2*X2^n。 ∵F(1)=F(2)=1。 ∴C1*X1 + C2*X2。 C1*X1^2 + C2*X2^2。 解得C1=√5/5,C2=-√5/5。 ∴F(n)=(√5/5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}(√5表示根号5)。 方法二:待定系数法构造等比数列1(初等代数解法) 设常数r,s。 使得F(n)-r*F(n-1)=s*[F(n-1)-r*F(n-2)]。 则r+s=1, -rs=1。 n≥3时,有。 F(n)-r*F(n-1)=s*[F(n-1)-r*F(n-2)]。 F(n-1)-r*F(n-2)=s*[F(n-2)-r*F(n-3)]。 F(n-2)-r*F(n-3)=s*[F(n-3)-r*F(n-4)]。 …… F(3)-r*F(2)=s*[F(2)-r*F(1)]。 联立以上n-2个式子,得: F(n)-r*F(n-1)=[s^(n-2)]*[F(2)-r*F(1)]。 ∵s=1-r,F(1)=F(2)=1。 上式可化简得: F(n)=s^(n-1)+r*F(n-1) 。 那么: F(n)=s^(n-1)+r*F(n-1)。 = s^(n-1) + r*s^(n-2) + r^2*F(n-2)。 = s^(n-1) + r*s^(n-2) + r^2*s^(n-3) + r^3*F(n-3)。 …… = s^(n-1) + r*s^(n-2) + r^2*s^(n-3) +……+ r^(n-2)*s + r^(n-1)*F(1)。 = s^(n-1) + r*s^(n-2) + r^2*s^(n-3) +……+ r^(n-2)*s + r^(n-1)。 (这是一个以s^(n-1)为首项、以r^(n-1)为末项、r/s为公比的等比数列的各项的和)。 =[s^(n-1)-r^(n-1)*r/s]/(1-r/s)。 =(s^n - r^n)/(s-r)。 r+s=1, -rs=1的一解为 s=(1+√5)/2,r=(1-√5)/2。 则F(n)=(√5/5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}。 方法三:待定系数法构造等比数列2(初等代数解法) 已知a1=1,a2=1,an=a(n-1)+a(n-2)(n>=3),求数列{an}的通项公式。 解 :设an-αa(n-1)=β(a(n-1)-αa(n-2))。 得α+β=1。 αβ=-1。 构造方程x^2-x-1=0,解得α=(1-√5)/2,β=(1+√5)/2或α=(1+√5)/2,β=(1-√5)/2。 所以。 an-(1-√5)/2*a(n-1)=(1+√5)/2*(a(n-1)-(1-√5)/2*a(n-2))=[(1+√5)/2]^(n-2)*(a2-(1-√5)/2*a1)`````````1。 an-(1+√5)/2*a(n-1)=(1-√5)/2*(a(n-1)-(1+√5)/2*a(n-2))=[(1-√5)/2]^(n-2)*(a2-(1+√5)/2*a1)`````````2。 由式1,式2,可得。 an=[(1+√5)/2]^(n-2)*(a2-(1-√5)/2*a1)``````````````3。 an=[(1-√5)/2]^(n-2)*(a2-(1+√5)/2*a1)``````````````4。 将式3*(1+√5)/2-式4*(1-√5)/2,化简得an=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}。与黄金分割的关系
有趣的是:这样一个完全是自然数的数列,通项公式却是用无理数来表达的。而且当n趋向于无穷大时,后一项与前一项的比值的小数部分越来越逼近黄金分割0.618. 1÷1=1,2÷1=2,3÷2=1.5,5÷3=1.666...,8÷5=1.6,…………,89÷55=1.6181818…,…………233÷144=1.618055…75025÷46368=1.6180339889…。.. 越到后面,这些比值越接近黄金比. 证明: a[n+2]=a[n+1]+a[n]。 两边同时除以a[n+1]得到: a[n+2]/a[n+1]=1+a[n]/a[n+1]。 若a[n+1]/a[n]的极限存在,设其极限为x, 则lim[n->∞](a[n+2]/a[n+1])=lim[n->∞](a[n+1]/a[n])=x。 所以x=1+1/x。 即x²=x+1。 所以极限是黄金分割比 。.编辑本段奇妙的属性
斐波那契数列中的斐波那契数会经常出现在我们的眼前——比如松果、凤梨、树叶的排列、某些花朵的花瓣数、黄金矩形、黄金分割、等角螺线等,有时也可能是我们对斐波那契额数过于热衷,把原来只是巧合的东西强行划分为斐波那契数。比如钢琴上白键的8,黑键上的5都是斐波那契数,应该把它看做巧合还是规律呢? 随着数列项数的增加,前一项与后一项之比越来越逼近黄金分割的数值0.6180339887…… 从第二项开始,每个奇数项的平方都比前后两项之积多1,每个偶数项的平方都比前后两项之积少1。(注:奇数项和偶数项是指项数的奇偶,而并不是指数列的数字本身的奇偶,比如第四项3是奇数,但它是偶数项,第五项5是奇数,它是奇数项,如果认为数字3和5都是奇数项,那就误解题意,怎么都说不通)多了的一在哪?
如果你看到有这样一个题目: 某人把一个8*8的方格切成四块,拼成一个5*13的长方形,故 作惊讶地问你:为什么64=65?其实就是利用了斐波那契数列的这个性质:5、8、13正是数列中相邻的三项,事实上前后两块的面积 确实差1,只不过后面那个图中有一条细长的狭缝,一般人不容易注意到。 斐波那契数列的第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)的程序。 怎样实现呢?伪代码描述一下? 7.[f(n)]^2=(-1)^(n-1)+f(n-1)·f(n+1)。 8.f(2n-1)=[f(n)]^2-[f(n-2)]^2。 9.3f(n)=f(n+2)+f(n-2)。 10.f(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m) [ n〉m≥-1,且n≥1]斐波那契数列
11.f(2n+1)=[f(n)]^2+[f(n+1)]^2.在杨辉三角中隐藏着斐波那契数列
将杨辉三角依次下降,成如图所示排列,将同一行的数加起来,即得一数列1、1、2、3、5、8、…… 公式表示如下: f(1)=C(0,0)=1 。 f(2)=C(1,0)=1 。 f(3)=C(2,0)+C(1,1)=1+1=2 。 f(4)=C(3,0)+C(2,1)=1+2=3 。 f(5)=C(4,0)+C(3,1)+C(2,2)=1+3+1=5 。 f(6)=C(5,0)+C(4,1)+C(3,2)=1+4+3=8 。 F(7)=C(6,0)+C(5,1)+C(4,2)+C(3,3)=1+5+6+1=13 。 …… F(n)=C(n-1,0)+C(n-2,1)+…+C(n-1-m,m) (m<=n-1-m)
斐波那契数列的整除性与素数生成性
每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,然后依序点数叶子(假定没有折损),直到到达与那些叶子正对的位置,则其间的叶子数多半是斐波那契数。叶子从一个位置到达下一个正对的位置称为一个循回。叶子在一个循回中旋转的圈数也是斐波那契数。在一个循回中叶子数与叶子旋转圈数的比称为叶序(源自希腊词,意即叶子的排列)比。多数的叶序比呈现为斐波那契数的比。
编辑本段斐波那契—卢卡斯数列与广义斐波那契数列
斐波那契—卢卡斯数列
卢卡斯数列1、3、4、7、11、18…,也具有斐波那契数列同样的性质。(我们可称之为斐波那契—卢卡斯递推:从第三项开始,每一项都等于前两项之和f(n) = f(n-1)+ f(n-2))。 这两个数列还有一种特殊的联系(如下表所示),F(n)*L(n)=F(2n),及L(n)=F(n-1)+F(n+1) n12345678910…斐波那契数列F(n)11235813213455…卢卡斯数列L(n)13471118294776123…F(n)*L(n)138215514437798725846765… 类似的数列还有无限多个,我们称之为斐波那契—卢卡斯数列。 如1,4,5,9,14,23…,因为1,4开头,可记作F[1,4],斐波那契数列就是F[1,1],卢卡斯数列就是F[1,3],斐波那契—卢卡斯数列就是F[a,b]。斐波那契—卢卡斯数列之间的广泛联系
①任意两个或两个以上斐波那契—卢卡斯数列之和或差仍然是斐波那契—卢卡斯数列。 如:F[1,4]n+F[1,3]n=F[2,7]n,F[1,4]n-F[1,3]n=F[0,1]n=F[1,1](n-1), n12345678910…F[1,4]n14591423376097157…F[1,3]n13471118294776123…F[1,4]n-F[1,3]n0112358132134…F[1,4]n+F[1,3]n27916254166107173280… ②任何一个斐波那契—卢卡斯数列都可以由斐波那契数列的有限项之和获得,如 n12345678910…F[1,1](n)11235813213455…F[1,1](n-1)0112358132134…F[1,1](n-1)0112358132134…F[1,3]n13471118294776123…黄金特征与孪生斐波那契—卢卡斯数列
斐波那契—卢卡斯数列的另一个共同性质:中间项的平方数与前后两项之积的差的绝对值是一个恒值, 斐波那契数列:|1*1-1*2|=|2*2-1*3|=|3*3-2*5|=|5*5-3*8|=|8*8-5*13|=…=1 卢卡斯数列:|3*3-1*4|=|4*4-3*7|=…=5 F[1,4]数列:|4*4-1*5|=11 F[2,5]数列:|5*5-2*7|=11 F[2,7]数列:|7*7-2*9|=31 斐波那契数列这个值是1最小,也就是前后项之比接近黄金比例最快,我们称为黄金特征,黄金特征1的数列只有斐波那契数列,是独生数列。卢卡斯数列的黄金特征是5,也是独生数列。前两项互质的独生数列只有斐波那契数列和卢卡斯数列这两个数列。 而F[1,4]与F[2,5]的黄金特征都是11,是孪生数列。F[2,7]也有孪生数列:F[3,8]。其他前两项互质的斐波那契—卢卡斯数列都是孪生数列,称为孪生斐波那契—卢卡斯数列。广义斐波那契数列
斐波那契数列的黄金特征1,还让我们联想到佩儿数列:1,2,5,12,29,…,也有|2*2-1*5|=|5*5-2*12|=…=1(该类数列的这种特征值称为勾股特征)。 佩尔数列Pn的递推规则:P1=1,P2=2,Pn=P(n-2)+2P(n-1). 据此类推到所有根据前两项导出第三项的通用规则:f(n) = f(n-1) * p + f(n-2) * q,称为广义斐波那契数列。 当p=1,q=1时,我们得到斐波那契—卢卡斯数列。 当p=1,q=2时,我们得到佩尔—勾股弦数(跟边长为整数的直角三角形有关的数列集合)。 当p=-1,q=2时,我们得到等差数列。其中f1=1,f2=2时,我们得到自然数列1,2,3,4…。自然数列的特征就是每个数的平方与前后两数之积的差为1(等差数列的这种差值称为自然特征)。 具有类似黄金特征、勾股特征、自然特征的广义斐波那契数列p=±1。 当f1=1,f2=2,p=2,q=1时,我们得到等比数列1,2,4,8,16……编辑本段相关的数学问题
1.排列组合
有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法? 这就是一个斐波那契数列:登上第一级台阶有一种登法;登上两级台阶,有两种登法;登上三级台阶,有三种登法;登上四级台阶,有五种登法…… 1,2,3,5,8,13……所以,登上十级,有89种走法。 类似的,一枚均匀的硬币掷10次,问不连续出现正面的可能情形有多少种? 答案是(1/√5)*{[(1+√5)/2]^(10+2) - [(1-√5)/2]^(10+2)}=144种。2.数列中相邻两项的前项比后项的极限
当n趋于无穷大时,F(n)/F(n+1)的极限是多少? 这个可由它的通项公式直接得到,极限是(-1+√5)/2,这个就是黄金分割的数值,也是代表大自然的和谐的一个数字。 3.求递推数列a(1)=1,a(n+1)=1+1/a(n)的通项公式 由数学归纳法可以得到:a(n)=F(n+1)/F(n),将斐波那契数列的通项式代入,化简就得结果。3.兔子繁殖问题(关于斐波那契数列的别名)
斐波那契数列又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”。 一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有兔都不死,那么一年以后可以繁殖多少对兔子? 我们不妨拿新出生的一对小兔子分析一下: 第一个月小兔子没有繁殖能力,所以还是一对 两个月后,生下一对小兔民数共有两对 三个月以后,老兔子又生下一对,因为小兔子还没有繁殖能力,所以一共是三对 ------ 依次类推可以列出下表: 经过月数0123456789101112幼仔对数001123581321345589成兔对数01123581321345589144总体对数1123581321345589144233 幼仔对数=前月成兔对数 成兔对数=前月成兔对数+前月幼仔对数 总体对数=本月成兔对数+本月幼仔对数 可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点,那是:前面相邻两项之和,构成了后一项。 这个数列是意大利中世纪数学家斐波那契在<算盘全书>中提出的,这个级数的通项公式,除了具有a(n+2)=an+a(n+1)的性质外,还可以证明通项公式为:an=(1/√5)*{[(1+√5)/2]^n-[(1-√5)/2]^n}(n=1,2,3.....) `````编辑本段编程中的斐波那契数列
PB语言程序
int li_a,li_b,li_c,i string ls_print = '~n' li_b = 1 for i = 1 to 20 li_c = li_a + li_b li_a = li_b li_b = li_c ls_print += "~n" + string(li_c) next messagebox("斐波那契数列","前20:"+ls_print)C语言程序
//利用循环输出前40项 #includeC#语言程序
public class Fibonacci { //NormRen static void Main(string[] args) { int x = 0, y = 1; for (int j = 1; j < 10; j++, y = x + y, x = y - x) Console.Write(y + " "); } }Java语言程序
/* 快速计算第n个Java程序,一秒计算第10万个数字。 Intel Core2 Duo CPU P8600 2.4GHz 计算第100000个斐波那契数列的数所花时间(毫秒): 第100000:967.8 981.1 988.8 966.3 994.4 */ public class Fib { //n为第n个斐波那契数列的数 public static BigInteger compute2(int n) { if (n == 1 || n == 2) { return BigInteger.ONE; } BigInteger num1 = BigInteger.ONE; BigInteger num2 = BigInteger.ONE; BigInteger result = BigInteger.ZERO; for (int i = 2; i < n; i++) { result = num1 .add(num2); num2 = num1; num1 = result; } return result; } } public class Fibonacci { public static void main(String[] args) { int x=1,y=1; System.out.println(x+" "); for(int i=1;i<=20;i++) { System.out.println(y+" "); y=x+y;x=y-x; } } } Java语言程序(高精度,约一秒钟计算第20000个数值) import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner s=new Scanner(标准输入); int n=s.nextInt(); do{ cul(n); n=s.nextInt(); }while(n>0);//当n<=0时终止 } private static void cul(int n) { BigIntT b=new BigIntT(); BigIntT a=new BigIntT(); b.formatBigInt("1"); a.formatBigInt("2"); if(n==1 || n==2) { System.out.println(1); return; } int i=3; for(;i<=n;i++){ if(i%2>0) b.add(a); else a.add(b); } BigIntT t=null; if(i%2>0) t=b; else t=a; for(int j=t.getPos();j<100000;j++) System.out.print(t.getBase(j)); System.out.println(); } } class BigIntT{ int max=100000; private byte[] base=new byte[max]; private int pos=max; public void formatBigInt(String arr){ int l=arr.length(); if(l==0) return; int tmp=l-1; for(int i=max-1;i>=max-l;i--){ base[i]=(byte) (arr.charAt(tmp--)-'0'); pos--; } } public void add(BigIntT right) { int bigger=this.getPos()>right.getPos()?right.getPos():this.getPos(); pos=bigger; for(int i=max-1;i>=pos-2;i--){ int t=this.base[i]+right.getBase(i); if(t>=10){ this.base[i]=(byte) (t%10); this.base[i-1]+=t/10; if(i-1Pascal语言程序
递推: var b: array[1..40]of longint; i: integer; begin b[1] := 1; b[2] := 1; for i:=3 to 40 do b[i ] := b[i-1] + b[i-2]; for i:=1 to 40 do write(b[i],' '); end. 递归: function fib(n:integer):longint; begin if (n=1) then exit(0); if (n=2) then exit(1); fib:=fib(n-2)+fib(n-1); end; 高精度: program fzu1060; type arr=array[0..1001]of integer; var a,b,c:arr; i,j,k,n:integer; procedure add(var a,b,c:arr); begin fillchar(c,sizeof(c),0); c[0]:=b[0]; for i:=1 to c[0] do c[i]:=a[i]+b[i]; for i:=1 to c[0] do begin c[i+1]:=c[i+1]+(c[i] div 10); c[i]:=c[i] mod 10; end; if c[c[0]+1]>0 then begin inc(c[0]); inc(c[c[0]+1],c[c[0]] div 10); c[c[0]]:=c[c[0]] mod 10; end; a:=b; b:=c; end; begin assign(input,'d:\input.txt'); assign(output,'d:\output.txt'); reset(input); rewrite(output); while not eof do begin readln(n); fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); a[0]:=1; a[1]:=1; b[0]:=1; b[1]:=1; if n=1 then write(1) else if n=2 then write(1) else begin for k:=3 to n do add(a,b,c); for k:=c[0] downto 1 do write(c[k]); end; writeln; end; close(input); close(output); end. 以上程序为 FZU 1060 的标程。PL/SQL程序
declare i number :=0; j number :=1; x number :=1; begin while x<1000 loop dbms_output.put_line(x); x:=i+j; i:=j; j:=x; end loop; end;Python程序
# 方法一 def fibonacci(num): if num <= 2: f = 1 else: f=fibonacci(num-1) + fibonacci(num - 2) return f #方法二 import math def fibonacci1(num): f = (((math.sqrt(5) + 1)/2) ** num - ((math.sqrt(5) - 1)/2) ** num)/math.sqrt(5) f = round(f, 1) if f - int(f) > 0: f = int(f) + 1 else : f = int (f) return f Matlab程序 function f=fibonacci(n) p = (1-sqrt(5))/2 ; q = (1+sqrt(5))/2 ; n=1:n; f =q.^(n-2)*(1-p).*(1-(p/q).^(n-1))./(1-p/q)+p.^(n-1);数列与矩阵
对于斐波那契数列1、1、2、3、5、8、13、……。有如下定义 F(n)=f(n-1)+f(n-2) F(1)=1 F(2)=1 对于以下矩阵乘法 F(n+1) = 11 F(n) F(n) 10 F(n-1) 它的运算就是右边的矩阵 11乘以矩阵 F(n) 得到: 10 F(n-1) F(n+1)=F(n)+F(n-1) F(n)=F(n) 可见该矩阵的乘法完全符合斐波那契数列的定义 设矩阵A=1 1 迭代n次可以的到:F(n+1) =A^(n) * F(1)= A^(n)*1 1 0 F(n) F(0) 0 这就是斐波那契数列的矩阵乘法定义。 另矩阵乘法的一个运算法则A¬^n(n为偶数)=A^(n/2)* A^(n/2),这样我们通过二分的思想,可以实现对数复杂度的矩阵相乘。 因此可以用递归的方法求得答案。 时间效率:O(logn),比模拟法O(n)远远高效。 代码(PASCAL) {变量matrix是二阶方阵,matrix是矩阵的英文} program fibonacci; type matrix=array[1..2,1..2] of qword; var c,cc:matrix; n:integer; function multiply(x,y:matrix):matrix; var temp:matrix; begin temp[1,1]:=x[1,1]*y[1,1]+x[1,2]*y[2,1]; temp[1,2]:=x[1,1]*y[1,2]+x[1,2]*y[2,2]; temp[2,1]:=x[2,1]*y[1,1]+x[2,2]*y[2,1]; temp[2,2]:=x[2,1]*y[1,2]+x[2,2]*y[2,2]; exit(temp); end; function getcc(n:integer):matrix; var temp:matrix; t:integer; begin if n=1 then exit(c); t:=n div 2; temp:=getcc(t); temp:=multiply(temp,temp); if odd(n) then exit(multiply(temp,c)) else exit(temp); end; procedure init; begin readln(n); c[1,1]:=1; c[1,2]:=1; c[2,1]:=1; c[2,2]:=0; if n=1 then begin writeln(1); halt; end; if n=2 then begin writeln(1); halt; end; cc:=getcc(n-2); end; procedure work; begin writeln(cc[1,1]+cc[1,2]); end; begin init; work; end. 数列值的另一种求法: F(n) = [ (( sqrt ( 5 ) + 1 ) / 2) ^ n ] 其中[ x ]表示取距离 x 最近的整数。前若干项
(1)1 (2)1 (3)2(1+1) (4)3(1+2) (5)5(2+3) (6)8(3+5) (7)13(5+8) (8)21(8+13) (9)34(13+21) (10)55(21+34) (11)89(34+55) (12)144(55+89) (13)233(89+144) (14)377(144+233) (15)610(233+377) (16)987(377+610) (17)1597(610+987) (18)2584(987+1597) (19)4181(1597+2584) (20)6765(2584+4181) (21)10946(4181+6765) (22)17711(6765+10946) (23)28657(10946+17711) (24)46368(17711+28657)(46368÷28657=1.61803398820......) ......斐波那契弧线
斐波那契弧线,第一,此趋势线以二个端点为准而画出,例如,最低点反向到最高点线上的两个点。三条弧线均以第二个点为中心画出,并在趋势线的斐波纳契水平:38.2%, 50%和61.8%交叉。 斐波纳契弧线,是潜在的支持点和阻力点水平价格。斐波纳契弧线和斐波纳契扇形线常常在图表里同时绘画出。支持点和阻力点就是由这些线的交汇点得出。 要注意的是弧线的交叉点和价格曲线会根据图表数值范围而改变因为弧线是圆周的一部分,它的形成总是一样的。 斐波那契扇形线 斐波那契扇形线,例如,以最低点反向到最高点线上的两个端点画出的趋势线。然后通过第二点画出一条“无形的(看不见的)”垂直线。然后,从第一个点画出第三条趋势线:38.2%, 50%和61.8%的无形垂直线交叉。编辑本段应用
数学游戏
一位魔术师拿着一块边长为8英尺的正方形地毯,对他的地毯匠朋友说:“请您把这块地毯分成四小块,再把它们缝成一块长13英尺,宽5英尺的长方形地毯。”这位匠师对魔术师算术之差深感惊异,因为两者之间面积相差达一平方英尺呢!可是魔术师竟让匠师用图2和图3的办法达到了他的目的! 这真是不可思议的事!亲爱的读者,你猜得到那神奇的一平方英尺究竟跑到哪儿去呢? 实际上后来缝成的地毯有条细缝,面积刚好就是一平方英尺。
自然界中的巧合
斐波那契数列在自然科学的其他分支,也有许多应用。例如,树木的生长,由于新生的枝条,往往需要一段“休息”时间,供自身生长,而后才能萌发新枝。所以,一株树苗在一段间隔,例如一年,以后长出一条新枝;第二年新枝“休息”,老枝依旧萌发;此后,老枝与“休息”过一年的枝同时萌发,当年生的新枝则次年“休息”。这样,一株树木各个年份的枝桠数,便构成斐波那契数列。这个规律,就是生物学上著名的“鲁德维格定律”。 另外,观察延龄草、野玫瑰、南美血根草、大波斯菊、金凤花、耧斗菜、百合花、蝴蝶花的花瓣,可以发现它们花瓣数目具有斐波那契数:3、5、8、13、21、……斐波那契螺旋:具有13条顺时针旋转和21条逆时针旋转的螺旋的蓟的头部 这些植物懂得斐波那契数列吗?应该并非如此,它们只是按照自然的规律才进化成这样。这似乎是植物排列种子的“优化方式”,它能使所有种子具有差不多的大小却又疏密得当,不至于在圆心处挤了太多的种子而在圆周处却又稀稀拉拉。叶子的生长方式也是如此,对于许多植物来说,每片叶子从中轴附近生长出来,为了在生长的过程中一直都能最佳地利用空间(要考虑到叶子是一片一片逐渐地生长出来,而不是一下子同时出现的),每片叶子和前一片叶子之间的角度应该是222.5度,这个角度称为“黄金角度”,因为它和整个圆周360度之比是黄金分割数0.618033989……的倒数,而这种生长方式就决定了斐波那契螺旋的产生。向日葵的种子排列形成的斐波那契螺旋有时能达到89,甚至144条。
数字谜题
三角形的三边关系定理和斐波那契数列的一个联系: 现有长为144cm的铁丝,要截成n小段(n>2),每段的长度不小于1cm,如果其中任意三小段都不能拼成三角形,则n的最大值为多少? 分析:由于形成三角形的充要条件是任何两边之和大于第三边,因此不构成三角形的条件就是任意两边之和不超过最大边。截成的铁丝最小为1,因此可以放2个1,第三条线段就是2(为了使得n最大,因此要使剩下来的铁丝尽可能长,因此每一条线段总是前面的相邻2段之和),依次为:1、1、2、3、5、8、13、21、34、55,以上各数之和为143,与144相差1,因此可以取最后一段为56,这时n达到最大为10。 我们看到,“每段的长度不小于1”这个条件起了控制全局的作用,正是这个最小数1产生了斐波那契数列,如果把1换成其他数,递推关系保留了,但这个数列消失了。这里,三角形的三边关系定理和斐波那契数列发生了一个联系。 在这个问题中,144>143,这个143是斐波那契数列的前n项和,我们是把144超出143的部分加到最后的一个数上去,如果加到其他数上,就有3条线段可以构成三角形了。影视作品中的斐波那契数列
斐波那契数列在欧美可谓是尽人皆知,于是在电影这种通俗艺术中也时常出现,比如在风靡一时的《达芬奇密码》里它就作为一个重要的符号和情节线索出现,在《魔法玩具城》里又是在店主招聘会计时随口问的问题。可见此数列就像黄金分割一样流行。可是虽说叫得上名,多数人也就背过前几个数,并没有深入理解研究。在电视剧中也出现斐波那契数列,比如:日剧《考试之神》第五回,义嗣做全国模拟考试题中的最后一道数学题~编辑本段社会文明中的斐波那契数列
艾略特波浪理论
1946年,艾略特完成了关于波浪理论的集大成之作,《自然法则——宇宙的秘密》。艾略特坚信,他的波浪理论是制约人类一切活动的普遍自然法则的一部分。波浪理论的优点是,对即将出现的顶部或底部能提前发出警示信号,而传统的技术分析方法只有事后才能验证。艾略特波浪理论对市场运作具备了全方位的透视能力,从而有助于解释特定的形态为什么要出现,在何处出现,以及它们为什么具备如此这般的预测意义等等问题。另外,它也有助于我们判明当前的市场在其总体周期结构中所处的地位。波浪理论的数学基础,就是在13世纪发现的费氏数列。波浪理论数学结构8浪循环图 ·8浪循环图说明 ·波浪理论的推动浪,浪数为5(1、2、3、4、5),调整浪的浪数为3(a\b\c),合起来为8。 ·8浪循环中,前5段波浪构成一段明显的上升浪,其中包括3个向上的冲击波及两个下降的调整波。在3个冲击波之后,是由3个波浪组成的一段下跌的趋势,是对前一段5浪升势的总调整。这是艾略特对波浪理论的基本描述。而在这8个波浪中,上升的浪与下跌的浪各占4个,可以理解为艾略特对于股价走势对称性的隐喻。 ·在波浪理论中,最困难的地方是:波浪等级的划分。如果要在特定的周期中正确地指认某一段波浪的特定属性,不仅需要形态上的支持,而且需要对波浪运行的时间作出正确的判断。 ·换句话说,波浪理论易学难精,易在形态上的归纳、总结,难在价位及时间周期的判定。 波浪理论的数字基础:斐波那契数列 波浪理论数学结构—— 斐波那契数列与黄金分割率 ·这个数列就是斐波那契数列。它满足如下特性:每两个相连数字相加等于其后第一个数字;前一个数字大约是后一个数字的0.618倍;前一个数字约是其后第二个数字的0.382倍;后一个数字约是前一个数字的1.618倍;后一个数字约是前面第二个数字的2.618倍; ·由此计算出常见的黄金分割率为(0.5和1.5外): 0.191、0.236、0.382、0.618、0.809、 1.236、1.382、1.618、1.764、1.809 ·黄金分割比率对于股票市场运行的时间周期和价格幅度模型具有重要启示及应用价值。 黄金分割比率在时间周期模型上的应用 ·未来市场转折点=已知时间周期×分割比率 ·已知时间周期有两种: (1)循环周期:最近两个顶之间的运行时间或两个底之间的运行时间 (2)趋势周期:最近一段升势的运行时间或一段跌势的运行时间 ·一般来讲,用循环周期可以计算出下一个反向趋势的终点,即用底部循环计算下一个升势的顶,或用顶部循环计算下一个跌势的底。而用趋势周期可以计算下一个同方向趋势的终点或是下一个反方向趋势的终点。 时间循环周期模型预测图 时间趋势周期模型预测图 时间周期与波浪数浪的数学关系 ·一个完整的趋势(推动浪3波或调整浪3波),运行时间最短为第一波(1浪或A浪)的1.618倍,最长为第一波的5.236倍。如果第一波太过短促,则以第一个循环计算(A浪与B浪或1浪与2浪)。 ·1.382及1.764的周期一旦成立,则出现的行情大多属次级趋势,但行情发展迅速。 ·同级次两波反向趋势组成的循环,运行时间至少为第一波运行时间的1.236倍。 ·一个很长的跌势(或升势)结束后,其右底(或右顶)通常在前趋势的1.236或1.309倍时间出现。 黄金分割比率在价格幅度模型上的应用 ·如果推动浪中的一个子浪成为延伸浪的话,则其他两个推动浪不管其运行的幅度还是运行的时间,都将会趋向于一致。也就是说,当推动浪中的浪3在走势中成为延伸浪时,则浪1与浪5的升幅和运行时间将会大致趋同。假如并非完全相等,则极有可能以0.618的关系相互维系。 ·浪5最终目标,可以根据浪1浪底至浪2浪顶距离来进行预估,他们之间的关系,通常亦包含有神奇数字组合比率的关系。 ·对于ABC调整浪来说,浪C的最终目标值可能根据浪A的幅度来预估。浪C的长度会经常是浪A的1.618倍。当然我们也可以用下列公式预测浪C的下跌目标:浪A浪底减浪A乘0.618。 ·在对称三角形内,每个浪的升跌幅度与其他浪的比率,通常以0.618的神奇比例互相维系。 黄金分割比率在价格幅度模型上的应用 ·0.382:浪4常见的回吐比率、部份浪2的回吐比率、浪B的回吐比率。 ·0.618:大部份浪2的调整幅度、浪5的预期目标、浪B的调整比率、三角形内浪浪之间比率。 ·0.5:常见是浪B的调整幅度。 ·0.236:浪3或浪4的回吐比率,但不多见。 ·1.236与1.382: ·1.618:浪3与浪1、浪C与浪A的比率关系。 推动浪形态 ·推动浪有五浪构成。第一浪通常只是由一小部分交易者参与的微弱的波动。一旦浪1结束,交易者们将在浪2卖出。浪2的卖出是十分凶恶的,最后浪2在不创新低的情况下,市场开始转向启动下一浪波动。浪3波动的初始阶段是缓慢的,并且它将到达前一次波动的顶部 (浪1的顶部)。 推动浪浪5未能创新高(低),市场将会出现大逆转 推动浪的变异形态——倾斜三角形 ·倾斜三角形为推动浪中的一种特殊型态(比较少见),主要出现在第5浪的位置。艾略特指出,在股市中,一旦出现一段走势呈现快速上升或赶底的状况,其后经常会出现倾斜三角形型态 调整浪形态 ·调整是十分难以掌握的,许多艾略特交易者在推动模式阶段上赚钱而在调整阶段再输钱。一个推动阶段包括五浪。调整阶段由三浪组成,但有一个三角形的例外。一个推动经常伴随着一个调整的模式。 ·调整模式可以被分成两类: ·简单的调整:之字型调整(N字型调整) ·复杂的调整:平坦型、不规则型、三角形型 调整浪的简单与复杂调整的交替准则 调整浪的变异形态:强势三角形 调整浪的变异形态:前置三角形 各段波浪的特性 ·在8浪循环中,每段波浪都有不同的特点,熟知这些特点,对波浪属性的判断极有帮助, ·第1浪:大部分第1浪属于营造底部形态的一部份,相当于形态分析中头肩底的底部或双底的右底,对这种类型的第1浪的调整(第2浪)幅度通常较大,理论上可以回到第1浪的起点。 小部份第1浪在大型调整形态之后出现,形态上呈V形反转,这类第1浪升幅较为可观。在K线图上,经常出现带长下影线的大阳线。 从波浪的划分来说,在5-3-5的调整浪当中,第1浪也可以向下运行,通常第1浪在分时图上应该显示明确的5浪形态。 ·第2浪:在强势调整的第2浪中,其回调幅度可能达到第1浪幅度的0.382或0.618,在更多的情况下,第2浪的回调幅度会达到100%,形态上经常表现为头肩底的右底,使人误以为跌势尚未结束。 在第2浪回调结束时,指标系统经常出现超卖、背离等现象。 第2浪成交量逐渐缩小,波幅较细,这是卖力衰竭的表现。 出现传统系统的转向信号,如头肩底、双底等。 ·第3浪:如果运行时间较短,则升速通常较快。在一般情况下为第1浪升幅的1.618倍。如果第3浪升幅与第1浪等长,则第5浪通常出现扩延的情况。 在第3浪当中,唯一的操作原则是顺势而为。因为第3浪的升幅及时间经常会超出分析者的预测。 通常第3浪运行幅度及时间最长。属于最具爆发性的一浪。大部分第3浪成为扩延浪。第3浪成交量最大。 出现传统图表的突破信号,如跳空缺口等。 ·第4浪:如果第4浪以平坦型或N字型出现,a小浪与c小浪的长度将会相同。第4浪与第2浪经常是交替形态的关系,即单复式交替或平坦型、曲折型或三角形的交替。 第4浪的低点经常是其后更大级数调整浪中A浪的低点。 经常以较为复杂的形态出现,尤其以三角形较为多见。通常在第3浪中所衍生出来的较低一级的第4浪底部范围内结束。 第4浪的底不会低于第1浪的顶。 ·第5浪:除非发生扩延的情况,第5浪的成交量及升幅均小于第3浪。 第5浪的上升经常是在指标出现顶背离或钝化的过程中完成。 在第5浪出现衰竭性上升的情况下,经常出现上升楔形形态。这时,成交量与升幅也会出现背离的情况。 如果第1、3浪等长,则第5浪经常出现扩延。如果第3浪出现扩延浪,则第5浪幅度与第1浪大致等长。 市场处于狂热状态。 ·第6浪A浪:A浪可以为3波或者5波的形态。在A浪以3波调整时,在A浪结束时,市场经常会认为整个调整已经结束。在多数情况下,A浪可以分割为5小浪。 市场人士多认为市场并未逆转,只视为一个较短暂的调整。 图表上,阴线出现的频率增大。 ·第7浪B浪:在A浪以3波形态出现的时候,B浪的走势通常很强,甚至可以超越A浪的起点,形态上出现平坦型或三角形的概率很大。而A浪以5波运行的时候,B浪通常回调至A浪幅度的0.5至0.618。 升势较为情绪化,维持时间较短。 成交量较小。 ·第8浪C浪:除三角形之外,在多数情况下,C浪的幅度至少与A浪等长。 杀伤力最强。 与第3浪特性相似,以5浪下跌。 股价全线下挫。