剑指Offer-斐波那契数列以及跳台阶问题

本文主要是介绍剑指Offer-斐波那契数列以及跳台阶问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

剑指Offer-斐波那契数列以及跳台阶问题

斐波那契数列：

1，1，2，3，5……
规律：f(n) = f(n-1) + f(n-2)
题目描述：
输入一个整数n，请你输出斐波那契数列的第n项。
n<=39

分析：题目很简答，递归也行非递归也行，代码如下：

#include<iostream>
#include<algorithm>using namespace std;/*int Fibonacci(int n) {     //递归方法if(n==0) return 0;if(n==1 || n==2) return 1;return Fibonacci(n-1)+Fibonacci(n-2);}
*/int Fibonacci(int n) {      //动规方法if(n==0) return 0;if(n==1 || n==2) return 1;int fn1 = 1;int fn2 = 1;while(n-- >2) {fn1 += fn2;fn2 = fn1-fn2;}return fn1;
}
int main()
{cout<<Fibonacci(6)<<endl;return 0;
}

跳台阶问题

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

分析：
类似斐波那契数列，青蛙最后一步跳到第n级，有两种可能，一种是从n-2直接跳上来，一种是从n-1跳上来，因此同样有规律f(n) = f(n-1) + f(n-2),其中f(1)=1,f(2)=2。代码如下：

#include<iostream>
#include<algorithm>using namespace std;/*int jumpFloor(int number) {  //递归版本if(number==1) return 1;if(number==2) return 2;return jumpFloor(number-1)+jumpFloor(number-2);}
*/int jumpFloor(int number) {    //非递归版本if(number==1) return 1;if(number==2) return 2;int fn1 = 2,fn2=1;while(number-- >2) {fn1 += fn2;fn2 = fn1-fn2;}return fn1;
}int main() {cout<<jumpFloor(5)<<endl;
}

变态跳台阶

题目描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析：
根据跳台阶问题，分析得到：
f(n)=f(n-1)+f(n-2)+…+f(1)
而f(n-1)=f(n-2)+f(n-3)+…f(1)
故f(n)=2*f(n-1)
得到规律：f(n)=2^(n-1)
代码如下：

#include<iostream>
#include<algorithm>
#include<cmath>using namespace std;int jumpFloorII(int number) {return pow(2,number-1);
}int main() {cout<<jumpFloorII(4)<<endl;
}