斐波那契數(shù)列的實(shí)現(xiàn)（簡(jiǎn)單遞歸和動(dòng)態(tài)規(guī)劃）

一、簡(jiǎn)單遞歸的實(shí)現(xiàn)

1 #include "stdafx.h" 2 #include <string> 3 using namespace std; 4 int f(int n) 5 { 6 if (n == 0) 7 { 8 return 0; 9 } 10 if (n == 1) 11 { 12 return 1; 13 } 14 return f(n - 1) + f(n - 2); 15 } 16 int _tmain(int argc, _TCHAR* argv[]) 17 { 18 printf("%d", f(10)); 19 getchar(); 20 return 0; 21 }

　　求解斐波那契數(shù)列當(dāng)中的n=5時(shí)的值這個(gè)問(wèn)題的遞歸樹(shù)如下圖所示：

? ? ?可見(jiàn)遞歸算法由于會(huì)多次計(jì)算同樣的子問(wèn)題而出現(xiàn)效率低下的問(wèn)題，為了避免重復(fù)計(jì)算子問(wèn)題，提升算法的效率，可以使用動(dòng)態(tài)規(guī)劃的思維來(lái)改進(jìn)算法。

二、動(dòng)態(tài)規(guī)劃算法

1、具有備忘功能的自頂向下算法

? ? ?使用一個(gè)數(shù)組來(lái)記錄各個(gè)子問(wèn)題的解，當(dāng)再一次遇到這一問(wèn)題的時(shí)候直接查找數(shù)組來(lái)獲得解避免多次計(jì)算子問(wèn)題。

1 #include "stdafx.h" 2 #include <string> 3 using namespace std; 4 int f(int a[],int n) 5 { 6 if (n == 0) 7 { 8 a[0] = 0; 9 return 0; 10 } 11 if (n == 1) 12 { 13 a[1] = 1; 14 return 1; 15 } 16 if (a[n] >= 0) 17 { 18 return a[n]; 19 } 20 a[n] = f(a, n - 1) + f(a, n - 2); 21 return f(a, n - 1) + f(a, n - 2); 22 } 23 int _tmain(int argc, _TCHAR* argv[]) 24 { 25 int n = 10;//需要求解的數(shù) 26 int* a = (int*)malloc((n + 1)*sizeof(int)); 27 for (int i = 0; i < n + 1; i++) 28 { 29 a[i] = -1; 30 } 31 printf("%d\n子問(wèn)題的解", f(a, n)); 32 for (int i = 0; i < n + 1; i++) 33 { 34 printf("%d ", a[i]); 35 } 36 getchar(); 37 return 0; 38 }

?

?2、自底向上解決方案

　　先求解子問(wèn)題再根據(jù)子問(wèn)題的解來(lái)求解父問(wèn)題，斐波那契數(shù)列的子問(wèn)題圖如下：

1 #include "stdafx.h" 2 #include <string> 3 using namespace std; 4 int f(int a[],int n) 5 { 6 a[0] = 0; 7 a[1] = 1; 8 for (int i = 2; i <= n; i++) 9 { 10 a[i] = a[i - 1] + a[i - 2]; 11 } 12 return a[n]; 13 } 14 int _tmain(int argc, _TCHAR* argv[]) 15 { 16 int n = 10;//需要求解的數(shù) 17 int* a = (int*)malloc((n + 1)*sizeof(int)); 18 for (int i = 0; i < n + 1; i++) 19 { 20 a[i] = -1; 21 } 22 printf("%d\n子問(wèn)題的解", f(a, n)); 23 for (int i = 0; i < n + 1; i++) 24 { 25 printf("%d ", a[i]); 26 } 27 getchar(); 28 return 0; 29 }

　　自底向上的計(jì)算方法實(shí)現(xiàn)起來(lái)非常容易，分析算法，僅從形式上面分析算法可知，算法的時(shí)間主要消耗在計(jì)算數(shù)據(jù)規(guī)模為n的數(shù)組里面的數(shù)上面了，所以時(shí)間復(fù)雜度為O（n）。

轉(zhuǎn)載于:https://www.cnblogs.com/AlgrithmsRookie/p/5919164.html

總結(jié)

以上是生活随笔為你收集整理的斐波那契数列的实现（简单递归和动态规划）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。