1 问题
写一个函数，输入n,求斐波那契数列的第n项。斐波那契数列定义如下。
f(n) = 0; (n = 0) f(n) = 1; (n = 1) f(n) = f(n - 1) + f(n - 2); (n >= 2);
2 分析
1) 直接用递归
2) 我们用两个变量保持每次需要计算下一个值得前面2个数，从最前面开始迭代。
3 代码实现
#include <stdio.h> long long fibonacciOne(unsigned int n) { if (n <= 0) return 0; if (n == 1) return 1; return fibonacciOne(n - 1) + fibonacciOne(n - 2); } long long fibonacciTwo(unsigned int n) { if (n <= 0) return 0; if (n == 1) return 1; long long first = 0; long long second = 1; long long sum = 0; for (int i = 2; i <= n ; ++i) { sum = first + second; first = second; second = sum; } return sum; } int main(void) { long long resultOne = fibonacciOne(8); long long resultTwo = fibonacciTwo(8); printf("resultOne is %lld\n", resultOne); printf("resultTwo is %lld\n", resultTwo); return 0; }
4 运行结果
resultOne is 21 resultTwo is 21
