斐波那契数列的两种解法

斐波那契数列对于很多人来说可能并不陌生。笔者最近经常遇到这道题，这里针对这道题总结一下。

在目前的状态下，笔者已经探索出了两种不同的解决方案：首先，我们可以回顾一下之前设计的一种较为简陋的解决方案。这种方案的设计并不尽如人意，其占用的空间较大，而且在时间效率上也没有任何优势可言。现在我还掌握了一种新的解决方案，这种方式大大节约了空间。这种新的方法让我感到非常惊喜，好了，现在让我们开始正文。

这里还是先把问题再描述一遍吧

一个数列An,a0=0,a1=1,an=an-1+an-2,求这个数列的前n项

解法一

先简单介绍一下思路：

这里我使用数组来存储这个数列，所以需要定义一个很大空间的数组，在定义完数组后，我们需要保证输入的n在数组范围内。然后直接使用循环，根据递归数列，从a2一直算到an输出就可以了，下面将代码贴出：

#include

using namespace std;

int main() {

	long int n;

	long int i;

	long long int* a = new long long int[1000000];

	cin >> n;

	if (n 1000000)return -1;
	a[0] = 1; a[1] = 1;

	cout