斐波那契数列
- 什么是斐波那契数列？
0，1，1，2，3，5......；数学函数：f(n) = f(n-1) + f(n-2)；
- 非递归实现
int fibonacci(int n) {
int result =0;
int a =1;
int b =1;
if(n ==0) {
return result;
}
if(n ==1||n ==2) {
result = a;
return result;
}
for(int i =3; i < n; i++) {
result = a + b;
a = b;
b = result;
}
return result;
}
- 递归实现
int recursiveFibonacci(int n) {
if(n ==0) {
return 0;
}
if(n ==1||n ==2) {
return 1;
}
return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
}
- 其他斐波那契数列问题
-
跳台阶问题：
- 一只青蛙一次可以跳上1级台阶，也可以跳上2级
求该青蛙跳上一个n级的台阶总共有多少种跳法。第n级台阶跳法等于第n-1级跳1步跟第n-2级跳2步，所以还是斐波那契数列f(n)=f(n-1)+f(n-2)。
-
变态跳台阶问题：
- 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
青蛙只跳1或2可以得出是一个斐波那契问题，即a[n]=a[n-1]+a[n-2],那么能跳1,2,3个台阶时a[n]=a[n-1]+a[n-2]+a[n-3],......依次类推，能推出a[n]=a[n-1]+a[n-2]+......+a[1];然后a[n-1]=a[n-2]+a[n-3]+......+a[1];那么两个公式相减a[n]-a[n-1]=a[n-1];所以a[n]=2a[n-1]。
int jumpFloorII(int number) {
if (number < 2)
return 1;
int a = 1;
int r = 0;
for (int i = 2; i <= number; i++) {
r = 2*a;
a = r;
}
return r;
}
