算法設計與分析：遞歸與分治法

1、應用數(shù)學 學院信息安全 專業(yè)班 學號姓名實驗題日遞歸與分治法綜合實驗評分表指導教師評分標準序 號評分項目評分標準滿分打分1完成度按要求獨立完成實驗準備、程序調試、實驗報告撰 寫。202實驗內容（1）完成功能需求分析、存儲結構設計；（2）程序功能完善、可正常運行；（3）測試數(shù)據(jù)正確，分析正確，結論正確。303實驗報告內容芥全，符合要求，文理通順，排版美觀。404總結對實驗過程遇到的問題能初步獨立分析，解決后能 總結問題原因及解決方法，有心得體會。10實驗報告、實驗目的與要求掌握遞歸算法的設計思想掌握分治法設計算法的一般過程理解并掌握算法漸近時間復雜度的分析方法、實驗內容1、折半查找的遞歸算法(1

2、)源程序代碼#include #include using namespace std;int bin_search(int key,int low, int high,int k)int mid;if(lowhigh)return -1;elsemid = (low+high) / 2;if(keymid=k)return mid;if(kkeymid)return bin_search(key,mid+1,high,k);elsereturn bin_search(key,low,mid-1,k);int main()int n , i , addr;int A10 = 2,3,5,7,8

3、,10,12,15,19,21;cout ”在下面的10個整數(shù)中進行查找 endl;for(i=0;i10;i+)cout Ai ;cout endl endl 請輸入一個要查找的整數(shù) n;addr = bin_search(A,0,9,n);if(-1 != addr)cout endl n 是上述整數(shù)中的第 addr 個數(shù) endl;elsecout endl n ”不在上述的整數(shù)中” endl endl;getchar();return 0;(2)運行界面查找成功查找失敗2、用分治法求x的n次方，要求時間復雜度為O(lgn)源程序代碼#include #include using nam

4、espace std;int Pow(int x, int n)if (n = 1)return x;else if (n 1)int s;int m = n / 2;s = Pow (x, m);if (n % 2 = 0)return (s * s);elsereturn (s * s * x);int main()int x, n;cout ”你將進行x的n次方計算 endl endl;cout ”請輸入 x： x;cout ”請輸入 n： n;cout endl 計算結果： Pow(x, n) endl endl; return 0;3、自然合并排序算法(1)源程序代碼#include

5、 StdAfx.h”#include using namespace std;const int SIZE = 100;int arrSIZE;int recSIZE;void merge(int fir,int end,int mid);int pass(int n);void mergeSort(int n);void mergeSort(int n)int num=pass(n);while(num!=2)for(int i=0;inum;i+=2)merge(reci,reci+2-1,reci+1-1);num=pass(n);void merge(int fir,int end,i

6、nt mid)int tempArrSIZE;int fir1=fir,fir2=mid+1;for(int i=fir;imid)tempArri=arrfir2+;else if(fir2end)tempArri=arrfir1+;else if(arrfir1arrfir2)tempArri=arrfir2+;elsetempArri=arrfir1+;for(int i=fir;i=end;i+)arri=tempArri;int pass(int n)int num=0;int biger=arr0;recnum+=0;for(int i=1;i=biger)biger=arri;e

7、lse recnum+=i;biger=arri;recnum+=n;return num;int main()int n;cout請輸入需要排序的整數(shù)個數(shù)：n)for(int i=0;in;i+)cout請輸入整數(shù)：arri;mergeSort(n);cout排序結果為：endl;for(int i=0;in;i+)coutarri;coutendlendl;cout請輸入需要排序的整數(shù)個數(shù)：endl;return 0;C :Win d owssyste m 3 2cm d. exe請輸入需要排序的整數(shù)個數(shù):請輸入整數(shù)：請輸入整數(shù)：請輸入整數(shù)：請輸入整數(shù)：62請輸入整數(shù)：請輸入整數(shù)：卻序結果

8、為：4 12 13 32 45 62請輸入需要排序的整數(shù)個數(shù):搜狗拼音輸入法全：三、問題與討論問題：分治法能解決的問題一般具有什么特征？解答：任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模有關。 問題的規(guī)模越小越容易直接求解，解題所需的計算時間也越少。分治法的設計思 想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各 個擊破，分而治之。分治法所能解決的問題一般具有以下幾個特征：（1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；（2）該問題可以分解為若十個規(guī)模較小的相同問題，即該問題具有最優(yōu)子 結構性質；（3）利用該問題分解出的子問題的解可以合并為該問題的解；（4）

9、該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公 共的子問題。四、總結這次實驗的內容都很有代表性，通過上機操作實踐與對問題的思考，讓我更 深層地領悟到了分治法的效率。分治法的基本思路并不難理解，就是將一個難以直接解決的大問題，分割成 一些規(guī)模較小的相同問題，在計算機的處理當中，問題的規(guī)模越小就越容易直接 求解，解題所需的計算時間也越少，所以分治法在合適的問題中是能大大提高效 率的。我非常喜歡上機課，因為課上聽的理論內容也許覺得懂了，但課后沒有一些 實踐，于是對一些難點實際上掌握得并不好。剛看到課題的實驗內容，其實基本 思路和條理還是會有的，因為會有一定的知識基礎，能夠想到一些相關的解決思 路，但有思路不一定就能夠解決問題，真正動手去做的時候才發(fā)現(xiàn)會出現(xiàn)更多的 實際問題。解決遇到的問題就是我們學習的過程，同時也能讓我注意到一些以前 不曾在意的問題。像我是使用C+來寫代碼的，其中我這次實驗時我就發(fā)現(xiàn)， “#include “StdAfX.h” 一定要放在首行，不然就會出錯；調試程序時如果出現(xiàn) “Cannot find or open the PDB fil