斐波那契数列实例讲解以及C++实现

斐波那契数列,又称黄金分割数列,指的是这样一个数列:0、1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。

斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368

特别指出:第0项是0,第1项是第一个1。

兔子繁殖问题

斐波那契数列又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”。

一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有兔子都不死,那么一年以后可以繁殖多少对兔子?

我们不妨拿新出生的一对小兔子分析一下:

第一个月小兔子没有繁殖能力,所以还是一对

两个月后,生下一对小兔对数共有两对

三个月以后,老兔子又生下一对,因为小兔子还没有繁殖能力,所以一共是三对

------

依次类推可以列出下表:


经过月数

0

1

2

3

4

5

6

7

8

9

10

11

12

幼仔对数

1

0

1

1

2

3

5

8

13

21

34

55

89

成兔对数

0

1

1

2

3

5

8

13

21

34

55

89

144

总体对数

1

1

2

3

5

8

13

21

34

55

89

144

233

幼仔对数=前月成兔对数

成兔对数=前月成兔对数+前月幼仔对数

总体对数=本月成兔对数+本月幼仔对数

可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点,那是:前面相邻两项之和,构成了后一项。

设月数为n;则有

F(0)=1;

F(1)=1;

F(n)=F(n-1)+F(n-2);

黄金分割

随着数列项数的增加,前一项与后一项之比越来越逼近黄金分割的数值0.6180339887..…

看4

杨辉三角

杨辉三角左对齐,成如图所示排列,将同一斜行的数加起来,即得一数列1、1、2、3、5、8、……

公式表示如下:

f⑴=C(0,0)=1。

f⑵=C(1,0)=1。

f⑶=C(2,0)+C(1,1)=1+1=2。

f⑷=C(3,0)+C(2,1)=1+2=3。

f⑸=C(4,0)+C(3,1)+C(2,2)=1+3+1=5。

f⑹=C(5,0)+C(4,1)+C(3,2)=1+4+3=8。

F⑺=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位不是)

数字谜题

三角形的三边关系定理和斐波那契数列的一个联系:

现有长为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条线段可以构成三角形了。

影视作品中的斐波那契数列

斐波那契数列在欧美可谓是尽人皆知,于是在电影这种通俗艺术中也时常出现,比如在风靡一时的《达芬奇密码》里它就作为一个重要的符号和情节线索出现,在《魔法玩具城》里又是在店主招聘会计时随口问的问题。可见此数列就像黄金分割一样流行。可是虽说叫得上名,多数人也就背过前几个数,并没有深入理解研究。在电视剧中也出现斐波那契数列,比如:日剧《考试之神》第五回,义嗣做全国模拟考试题中的最后一道数学题~在FOX热播美剧《Fringe》中更是无数次引用,甚至作为全剧宣传海报的设计元素之一。

排列组合

一、一枚均匀的硬币掷10次,问不连续出现正面的可能情形有多少种?

答案是144种。

利用标准斐波那契数列(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144),答案为F(10+2)。一枚均匀的硬币掷n次,不连续出现正面的可能情形有F(n+2)种。

二、有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?

这就是一个斐波那契数列:登上第一级台阶有一种登法;登上两级台阶,有两种登法;登上三级台阶,有三种登法;登上四级台阶,有五种登法……

1,2,3,5,8,13……所以,登上十级,有89种走法。这不是一个标准的斐波那契数列,初始化F(0)=0,F(1)=1,F(2)=2.

同leetcode上有一道题:

You are climbing a stair case. It takes n steps
to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

可用递归实现如下:

int stairs_climbing1(int n)
{
	if (n==0||n==1||n==2) return n;
	return stairs_climbing1(n-1)+stairs_climbing1(n-2);
}

但这种方法,每计算一次F(n)之前从F(0)到F(n-1)以及F(n-2)的过程都要重复执行一次,计算时间复杂度大,无法在规定时间内完成工作。改进算法,记录F(0)~F(n)的值,代码如下:

int stairs_climbing(int n)
{
	if (n==0||n==1||n==2) return n;
	vector<int >mem(n+1);
	mem[0]=0;
	mem[1]=1;
	mem[2]=2;
	int res;
	for (int i=3;i<n+1;i++)
	{
		mem[i]=mem[i-1]+mem[i-2];
	}
	return mem[n];
}

扩展

由上例可以看出,当初始值不一样时,F(n)=F(n-1)+F(n-2)就可能会有不一样的结果。

斐波那契—卢卡斯数列

卢卡斯数列1、3、4、7、11、18…,也具有斐波那契数列同样的性质。(我们可称之为斐波那契—卢卡斯递推:从第三项开始,每一项都等于前两项之和f(n)
= f(n-1)+ f(n-2)。

佩尔数列

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=2,q=-1时,我们得到等差数列。其中f1=1,f2=2时,我们得到自然数列1,2,3,4…。自然数列的特征就是每个数的平方与前后两数之积的差为1(等差数列的这种差值称为自然特征)。

具有类似黄金特征、勾股特征、自然特征的广义——斐波那契数列p=±1。

当f1=1,f2=2,p=2,q=0时,我们得到等比数列1,2,4,8,16……

本文参考:

http://baike.baidu.com/link?url=uYAPJgZmzQDU8wuN0H4QjB1nBUqRPtNeNz5yAzDGpcUWhBqT6KNGvvC-9iroF6TxScwngt_jM4-6XGQDppiKEK

我们不妨拿新出生的一对小兔子分析一下:

第一个月小兔子没有繁殖能力,所以还是一对

两个月后,生下一对小兔对数共有两对

三个月以后,老兔子又生下一对,因为小兔子还没有繁殖能力,所以一共是三对

------

依次类推可以列出下表:


经过月数

0

1

2

3

4

5

6

7

8

9

10

11

12

幼仔对数

1

0

1

1

2

3

5

8

13

21

34

55

89

成兔对数

0

1

1

2

3

5

8

13

21

34

55

89

144

总体对数

1

1

2

3

5

8

13

21

34

55

89

144

233

幼仔对数=前月成兔对数

成兔对数=前月成兔对数+前月幼仔对数

总体对数=本月成兔对数+本月幼仔对数

可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点,那是:前面相邻两项之和,构成了后一项。

设月数为n;则有

F(0)=1;

F(1)=1;

F(n)=F(n-1)+F(n-2);

黄金分割

随着数列项数的增加,前一项与后一项之比越来越逼近黄金分割的数值0.6180339887..…

看4

杨辉三角

时间: 04-19

斐波那契数列实例讲解以及C++实现的相关文章

一起talk C栗子吧(第四回:C语言实例--斐波那契数列)

各位看官们,大家好,从今天开始,我们讲大型章回体科技小说 :C栗子,也就是C语言实例.闲话休提, 言归正转.让我们一起talk C语言实例吧! 看官们,上一回中咱们说的是求阶乘的例子,这一回咱们说的例子是:斐波那契数列. 看官们,斐波那契数列是以数学家斐波那契数列的姓来命名的.斐波那契数列的定义:数列的第0项和第1项 为1,第n项为第n-1项和第n-2项的和.用数学公式表示出来就是:f(n)=f(n-1)+f(n-2),其中(n>1),f(n)=1;(n=0,1). 看官们,我在程序中使用了递归

【Python】【demo实验10】【练习实例】【打印斐波那契数列】

斐波那契数列介绍: 斐波那契数列(Fibonacci sequence),又称黄金分割数列.因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1.1.2.3.5.8.13.21.34.……在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)在现代物理.准晶体结构.化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963

【Python】【demo实验14】【练习实例】【斐波那契数列】【经典兔子生小兔子问题】

古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? 每个月的兔子数量 1:22:23:4 2+24:6 2+2+25:10 2+2+2+2+26:16 6+6+47:26 10+10+6 第一个月和第二个月兔子不繁殖 第三个月,两个兔子繁殖两个兔子,共四个 第四个月,两个兔子继续繁殖两个兔子,小兔子不繁殖:共6个 以此类推 2,2,4,6,10,16,26 这个数量刚好是斐波那契数列 的两倍 源代码: #

bzoj 3657 斐波那契数列(fib.cpp/pas/c/in/out)

空间 512M  时限2s [题目描述] 有n个大于1的正整数a1,a2,…,an,我们知道斐波那契数列的递推式是f(i)=f(i-1)+f(i-2),现在我们修改这个递推式变为f(i)=f(i-1)+f(i-2)+r(i-1),其中r(x)为a1,a2,…,an中为x的约数的个数.现在要求f(m) mod 19940417的值.注:初值f(1)=1,f(2)=1 输入格式: 第一行两个数n,m. 接下来一行n个正整数a1,a2,…,an. 输出格式: 输出一行仅一个数,f(m) mod 199

ACdreamOJ 1116 斐波那契数列+hash计算后缀

http://acdream.info/problem?pid=1116 Problem Description give you a string, please output the result of the following function mod 1000000007 n is the length of the string f() is the function of fibonacci, f(0) = 0, f(1) = 1... a[i] is the total numb

【剑指offer】斐波那契数列

题目1描述: 写一个函数,输入n,求斐波那契数列的第n项.斐波那契数列的定义如下: f(n) = 0 (n = 0);  f(n) = 1 (n = 1);  f(n) = f(n-1)+f(n-2) (n > 1); 分析描述: 在大多数的C语言教科书中,一般会用递归求斐波那契数列.代码如下: long long Fibonacci(unsigned int n) { if(n <= 0) return 0; if(n <= 1) return 1; return Fibonacci(

Python递归及斐波那契数列

递归函数 在函数内部,可以调用其他函数.如果一个函数在内部调用自身本身,这个函数就是递归函数.举个例子,我们来计算阶乘 n! = 1 * 2 * 3 * ... * n,用函数 fact(n)表示,可以看出:fact(n) = n! = 1 * 2 * 3 * ... * (n-1) * n = (n-1)! * n = fact(n-1) * n所以,fact(n)可以表示为 n * fact(n-1),只有n=1时需要特殊处理.于是,fact(n)用递归的方式写出来就是: def fact(

斐波那契数列——母牛的故事

斐波那契数列 先普及一下基础知识 1.定义 斐波那契数列,又称黄金数列,指的是这样一个数列:0.1.1.2.3.5.8.13.21.--在数学上,斐波纳契数列以如下被以递归的方法:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*). 2.通项公式 斐波那契数列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 如果设F(n)为该数列的第n项(n∈N*),那么这句话可以写成如下形式:显然这是一个线性递推数列.通项公式(如上,

斐波那契数列算法分析

背景: 假定你有一雄一雌一对刚出生的兔子,它们在长到一个月大小时开始交配,在第二月结束时,雌兔子产下另一对兔子,过了一个月后它们也开始繁殖,如此这般持续下去.每只雌兔在开始繁殖时每月都产下一对兔子,假定没有兔子死亡,在一年后总共会有多少对兔子? 在一月底,最初的一对兔子交配,但是还只有1对兔子:在二月底,雌兔产下一对兔子,共有2对兔子:在三月底,最老的雌兔产下第二对兔子,共有3对兔子:在四月底,最老的雌兔产下第三对兔子,两个月前生的雌兔产下一对兔子,共有5对兔子:……如此这般计算下去,兔子对数分