【剑指Offer】斐波那契数列

问题描述

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。

算法分析

这个比较基础,懂斐波那契数列的意思就能写得出来了,不多说。需要注意的是,在牛客网上刷这题的时候不能用递归,递归会超时。

代码实现

class Solution10 {
public:
	int Fibonacci(int n) {
		if (n == 0){
			return 0;
		}
		if (n == 1){
			return 1;
		}
		int r = 0;
		int r1 = 0,r2=1;
		for (int i = 1; i < n; i++){
			r = r1 + r2;
			r1 = r2;
			r2 = r;
		}
		return r;
	}
};