算法设计与分析：递归与分治法-实验报告

1、精选优质文档-倾情为你奉上 应用数学 学院 信息安全 专业 班 学号 姓名 实验题目 递归与分治法 综合实验评分表指导教师评分标准序号评分项目评分标准满分打分1完成度按要求独立完成实验准备、程序调试、实验报告撰写。202实验内容（1） 完成功能需求分析、存储结构设计；（2） 程序功能完善、可正常运行；（3） 测试数据正确，分析正确，结论正确。303实验报告内容齐全，符合要求，文理通顺，排版美观。404总结对实验过程遇到的问题能初步独立分析，解决后能总结问题原因及解决方法，有心得体会。10实验报告一、 实验目的与要求1. 掌握递归算法的设计思想 2. 掌握分治法设计算法的一般过程 3. 理解并掌

2、握算法渐近时间复杂度的分析方法二、 实验内容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个整数中进行查找" << endl;for(i=0;i<10;i+) cout << Ai << " " ; cout << endl << endl << "请输入一个要查找的整数" << en

4、dl;cin >> n; addr = bin_search(A,0,9,n); if(-1 != addr) cout << endl << n << "是上述整数中的第" << addr << "个数" << endl;else cout << endl << n << "不在上述的整数中" << 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 << "计算结果：" << 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<<"请输入需要排序的整数个数："<<endl; while(cin>>n) for(int i=0;i<n;i+)cout<<"请输入

10、整数："<<endl;cin>>arri; mergeSort(n); cout<<"排序结果为："<<endl;for(int i=0;i<n;i+)cout<<arri<<" " cout<<endl<<endl; cout<<"请输入需要排序的整数个数："<<endl; return 0;（2）运行界面三、问题与讨论问题：分治法能解决的问题一般具有什么特征？解答：任何一个可以用计算机求解的问题所

11、需的计算时间都与其规模有关。问题的规模越小越容易直接求解，解题所需的计算时间也越少。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治法所能解决的问题一般具有以下几个特征： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。四、总结这次实验的内容都很有代表性，通过上机操作实践与对问题的思考，让我更深层地领悟到了分治法的效率。

12、分治法的基本思路并不难理解，就是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，在计算机的处理当中，问题的规模越小就越容易直接求解，解题所需的计算时间也越少，所以分治法在合适的问题中是能大大提高效率的。我非常喜欢上机课，因为课上听的理论内容也许觉得懂了，但课后没有一些实践，于是对一些难点实际上掌握得并不好。刚看到课题的实验内容，其实基本思路和条理还是会有的，因为会有一定的知识基础，能够想到一些相关的解决思路，但有思路不一定就能够解决问题，真正动手去做的时候才发现会出现更多的实际问题。解决遇到的问题就是我们学习的过程，同时也能让我注意到一些以前不曾在意的问题。像我是使用C+来写代码的，其中我这次实验时我就发现，“#include “StdAfx.h”一定要放在首行，不然就会出错；调试程序时如