斐波那契数列C++实现

发布于 / Code / 0 条评论

简介

斐波那契数列,又称黄金分割数列,指的是这样一个数列: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

排列组合

一、一枚均匀的硬币掷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;
vectormem(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];
}
转载原创文章请注明,转载自: 风过不留痕 » 斐波那契数列C++实现
Not Comment Found