（C++）求解斐波那契数列.(递归与非递归)

斐波那契额数列：1、1、2、3、5、8、13、21、34… 首先很容易想到递推关系式：F(n）= F(n-1) + F(n - 2).(n>=3)。

方法1：

int fib1(int n) { if (n <= 2) { return 1; } return fib1(n - 1) + fib1(n-2); }

---

方法二：

int fib2(int n) { if (n <= 2) { return 1; } int * array = new int[n + 1]; memset(array, 0, sizeof(int)*(n + 1)); array[1] = array[2] = 1; return fib2(array, n); } //函数重载 int fib2(int * array, int n) { if (array[n] == 0) { array[n] = fib2(array, n - 1) + fib2(array,n - 2); } return array[n]; }

---

方法三：非递归

int fib3(int n) { if (n <= 2) { return 1; } int *array = new int[n + 1]; memset(array, 0, sizeof(int)*(n + 1)); array[1] = array[2] = 1; for (int i = 3; i <= n; i++) { array[i] = array[i - 1] + array[i - 2]; } return array[n]; }

---

方法四：非递归

//滚动数组 int fib4(int n) { if (n <= 2) { return 1; } int *array = new int[2]; memset(array, 0, sizeof(int)*2); array[0] = array[1] = 1; for (int i = 3; i <= n; i++) { array[i % 2] = array[(i - 1) % 2] + array[(i - 2) % 2]; } return array[n % 2]; }

---

方法五：滚动数组

//滚动数组.模运算的处理 int fib4(int n) { if (n <= 2) { return 1; } int *array = new int[2]; memset(array, 0, sizeof(int) * 2); array[0] = array[1] = 1; for (int i = 3; i <= n; i++) { array[i & 1] = array[(i - 1) & 1] + array[(i - 2) & 1]; } return array[n & 1]; }

---

最近在学习算法，开始填坑啦。后期开始加分析进去。