//求斐波那契数列第n项的值
//1,1,2,3,5,8,13,21,34...

//1.递归:
//缺点:当n过大时,递归深度过深,速度降低
int fib1(int n){
	if (n == 1 || n == 2)
		return 1;
	return fib1(n - 1) + fib1(n - 2);
}

//2.非递归:  时间复杂度O(n)
int fib2(int n){
	if (n == 1 || n == 2)
		return 1;
	int fibN,fibOne,fibTwo;
	for (int i = 0;i <= n;i++){
		fibN = fibOne + fibTwo;
		fibOne = fibTwo;
		fibtwo = fibN;
	}
	return fibN;
}