算法設計與分析：遞歸與分治法-實驗報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 應用數(shù)學 學院 信息安全 專業(yè) 班 學號 姓名 實驗題目 遞歸與分治法 綜合實驗評分表指導教師評分標準序號評分項目評分標準滿分打分1完成度按要求獨立完成實驗準備、程序調(diào)試、實驗報告撰寫。202實驗內(nèi)容（1） 完成功能需求分析、存儲結(jié)構(gòu)設計；（2） 程序功能完善、可正常運行；（3） 測試數(shù)據(jù)正確，分析正確，結(jié)論正確。303實驗報告內(nèi)容齊全，符合要求，文理通順，排版美觀。404總結(jié)對實驗過程遇到的問題能初步獨立分析，解決后能總結(jié)問題原因及解決方法，有心得體會。10實驗報告一、 實驗目的與要求1. 掌握遞歸算法的設計思想 2. 掌握分治法設計算法的一般過程 3. 理解并掌

2、握算法漸近時間復雜度的分析方法二、 實驗內(nèi)容1、折半查找的遞歸算法（1）源程序代碼#include <StdAfx.h>#include <iostream>using namespace std;int bin_search(int key,int low, int high,int k) int mid; if(low>high) return -1; else mid = (low+high) / 2; if(keymid=k) return mid; if(k>keymid) return bin_search(key,mid+1,high,k);

3、else return bin_search(key,low,mid-1,k); int main() int n , i , addr; int A10 = 2,3,5,7,8,10,12,15,19,21; cout << "在下面的10個整數(shù)中進行查找" << endl;for(i=0;i<10;i+) cout << Ai << " " ; cout << endl << endl << "請輸入一個要查找的整數(shù)" << en

4、dl;cin >> n; addr = bin_search(A,0,9,n); if(-1 != addr) cout << endl << n << "是上述整數(shù)中的第" << addr << "個數(shù)" << endl;else cout << endl << n << "不在上述的整數(shù)中" << endl << endl; getchar();return 0;（2）運行界面查找成功查找

5、失敗2、用分治法求x的n次方，要求時間復雜度為O(lgn)（1）源程序代碼#include <StdAfx.h>#include <iostream>using namespace 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); else return (s * s * x); int main() int x, n; cout << &q

6、uot;你將進行x的n次方計算" << endl << endl;cout << "請輸入x：" << endl;cin >> x;cout << "請輸入n：" << endl;cin >> n; cout << endl << "計算結(jié)果：" << Pow(x, n) << endl << endl; return 0;（2）運行界面3、自然合并排序算法（1）源程序代

7、碼#include "StdAfx.h"#include <iostream>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;i<num;i+=2) merge(reci,reci+2-1,reci+1

8、-1); num=pass(n); void merge(int fir,int end,int mid) int tempArrSIZE; int fir1=fir,fir2=mid+1; for(int i=fir;i<=end;i+) if(fir1>mid) tempArri=arrfir2+; else if(fir2>end) tempArri=arrfir1+; else if(arrfir1>arrfir2) tempArri=arrfir2+; else tempArri=arrfir1+; for(int i=fir;i<=end;i+) ar

9、ri=tempArri;int pass(int n) int num=0; int biger=arr0; recnum+=0; for(int i=1;i<n;i+) if(arri>=biger)biger=arri; else recnum+=i; biger=arri; recnum+=n; return num;int main() int n;cout<<"請輸入需要排序的整數(shù)個數(shù)："<<endl; while(cin>>n) for(int i=0;i<n;i+)cout<<"請輸入

10、整數(shù)："<<endl;cin>>arri; mergeSort(n); cout<<"排序結(jié)果為："<<endl;for(int i=0;i<n;i+)cout<<arri<<" " cout<<endl<<endl; cout<<"請輸入需要排序的整數(shù)個數(shù)："<<endl; return 0;（2）運行界面三、問題與討論問題：分治法能解決的問題一般具有什么特征？解答：任何一個可以用計算機求解的問題所

11、需的計算時間都與其規(guī)模有關。問題的規(guī)模越小越容易直接求解，解題所需的計算時間也越少。分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。分治法所能解決的問題一般具有以下幾個特征： （1）該問題的規(guī)?？s小到一定的程度就可以容易地解決； （2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)； （3）利用該問題分解出的子問題的解可以合并為該問題的解； （4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。四、總結(jié)這次實驗的內(nèi)容都很有代表性，通過上機操作實踐與對問題的思考，讓我更深層地領悟到了分治法的效率。

12、分治法的基本思路并不難理解，就是將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，在計算機的處理當中，問題的規(guī)模越小就越容易直接求解，解題所需的計算時間也越少，所以分治法在合適的問題中是能大大提高效率的。我非常喜歡上機課，因為課上聽的理論內(nèi)容也許覺得懂了，但課后沒有一些實踐，于是對一些難點實際上掌握得并不好。剛看到課題的實驗內(nèi)容，其實基本思路和條理還是會有的，因為會有一定的知識基礎，能夠想到一些相關的解決思路，但有思路不一定就能夠解決問題，真正動手去做的時候才發(fā)現(xiàn)會出現(xiàn)更多的實際問題。解決遇到的問題就是我們學習的過程，同時也能讓我注意到一些以前不曾在意的問題。像我是使用C+來寫代碼的，其中我這次實驗時我就發(fā)現(xiàn)，“#include “StdAfx.h”一定要放在首行，不然就會出錯；調(diào)試程序時如