斐波那契额数列及青蛙跳台阶问题

题目:写一个函数,输入n,求斐波那契(Fibonacci)数列的第n项。

 斐波那契(Fibonacci)数列定义如下:

效率很低的解法:

long long Fibonacci_Solution1(unsigned int n)
{
    if(n <= 0)
        return 0;

    if(n == 1)
        return 1;

    return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);
}

改进的算法:从下往上计算。首先根据f(0)和f(1)算出f(2),再根据f(1)和f(2)算出f(3)。。。。。依此类推就可以算出第n项了。很容易理解,这种思路的时间复杂度是o(n)。实现代码如下:

long long Fibonacci(unsigned n)
{
	int result[2] = {0 , 1};
	if(n < 2)
		return result[n];

	long long fibMinusOne = 1;
	long long fibMinusTwo = 0;
	for(unsigned int i = 2 ; i <= n ; ++i)
	{
		fibN = fibMinusOne + fibMinusTwo;

		fibMinusTwo = fibMinusOne;
		fibMinusOne = fibN;
	}
	
	return fibN;
}

题目:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

可以把n级台阶时的跳法看成是n的函数,记为f(n)。当n>2时,第一次跳的时候就有两种不同的选择:一是第一次只跳1级,此时跳法数目等于后面剩下的n-1级台阶的跳法数目,即为f(n-1);另一种选择是第一次跳2级,此时跳法数目等于后面剩下n-2级台阶的跳法数目,即为f(n-2)。因此,n级台阶的不同跳法的总数f(n)=f(n-1)+f(n-2)。分析到这里,不难看出这实际上就是斐波那契数列了。

#include<iostream>
using namespace std;

 long Fibonacci_Solution1(unsigned int n)
{
    if(n <= 0)
        return 0;

    if(n == 1)
        return 1;

    return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);
}

int main()
{
    int n;
	cin>>n;
	cout<<Fibonacci_Solution1(n)<<endl;
   
   return 0;
}

 在青蛙跳台阶的问题中,如果把条件改成:一只青蛙一次可以跳上1级台阶,也可以跳上2级。。。。。它也可以跳上n级,此时该青蛙跳上一个n级的台阶总共有多少种跳法?

用数学归纳法可以证明f(n)=2n-1.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

邻接矩阵存储有向图(详解)

邻接矩阵存储有向图 【输入描述】   输入文件包含多组测试数据,每组测试数据描述了一个无权有向图。每组测试数据第一行为两个正整数n和m,1<=n<=100,1<...

2959
来自专栏趣学算法

数据结构 第17讲 沟通无限校园网——最小生成树(kruskal算法)

构造最小生成树还有一种算法,Kruskal算法:设G=(V,E)是无向连通带权图,V={1,2,…,n};设最小生成树T=(V,TE),该树的初始状态为只有n...

1732
来自专栏用户画像

5.2 图的存储及基本操作

图的存储必须要完整、准确地反映顶点集和边集的信息。根据不同图的结构和算法,可以用不同的存储方式,但不同的存储方式将对程序的效率产生很大的影响,因此,所选的存储结...

1003
来自专栏数据结构与算法

2039 骑马修栅栏

题目描述 Description Farmer John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。 John是一个与其他农民一样懒的人...

38111
来自专栏程序生活

Leetcode-Easy 70. Climbing Stairs

21. Merge Two Sorted Lists 描述: 有n阶楼梯,每步只能走1个或2个台阶,请问到达第n阶楼梯一共有多少走法? ? ...

3296
来自专栏数据结构与算法

洛谷P2678 跳石头

题目背景 一年一度的“跳石头”比赛又要开始了! 题目描述 这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终...

3435
来自专栏编程理解

数据结构(十二):最短路径(Dijkstra算法)

Dijkstra 算法使用贪心策略计算从起点到指定顶点的最短路径,通过不断选择距离起点最近的顶点,来逐渐扩大最短路径权值,直到覆盖图中所有顶点。

2972
来自专栏恰童鞋骚年

数据结构基础温故-5.图(中):最小生成树算法

图的“多对多”特性使得图在结构设计和算法实现上较为困难,这时就需要根据具体应用将图转换为不同的树来简化问题的求解。

1532
来自专栏机器学习算法工程师

Tarjan算法

tarjan算法 一个关于有向图的联通性的神奇算法。 基于DFS(迪法师)算法,深度优先搜索一张有向图。 名词的储备,有备无患 强连通(strongly con...

40210
来自专栏weixuqin 的专栏

数据结构学习笔记(图)

30410

扫码关注云+社区

领取腾讯云代金券