1 问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶，求该青蛙跳上一个n级的台阶总共有多少种跳法？
2 分析
我们可以定位函数f(n),n为n级别的台阶，f(n)的值是青蛙有多少种跳法，我们知道当n为1的时候，f(1) = 1;
当n为2的时候，我们知道可以先跳一级再跳一级，或者直接跳2级，这里就有2种跳法，所以f(2) = 2;
当n为3的时候，我们可以这样理解，青蛙先跳一级，后面还有n-1级需要跳，所以这里的跳法为f(n - 1);
或者青蛙先跳两级，后面还有n-2级需要跳，所以这里的跳法为f(n - 2); 所以我们知道当n大于2时，f(n) = f(n - 1) + f(n - 2);
f(1) = 1; (n = 1) f(2) = 2; (n = 2) f(n) = f(n - 1) + f(n - 2); (n > 2)
3 代码实现
#include <stdio.h> long long fibonacciOne(unsigned int n) { if (n <= 0) return 0; if (n == 1) return 1; if (n == 2) return 2; return fibonacciOne(n - 1) + fibonacciOne(n - 2); } long long fibonacciTwo(unsigned int n) { if (n <= 0) return 0; if (n == 1) return 1; if (n == 2) return 2; long long first = 1; long long second = 2; long long sum = 0; for (int i = 3; i <=n ; ++i) { sum = first + second; first = second; second = sum; } return sum; } int main(void) { long long resultOne = fibonacciOne(4); long long resultTwo = fibonacciTwo(4); printf("resultOne is %lld\n", resultOne); printf("resultTwo is %lld\n", resultTwo); return 0; }
4 运行结果
resultOne is 5 resultTwo is 5
