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

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

2、方法二、 实验内容1、折半查找的递归算法（1）源程序代码#include #include using namespace std;int bin_search(int key,int low, int high,int k) int mid; if(lowhigh) return -1; else mid = (low+high) / 2; if(keymid=k) return mid; if(kkeymid) return bin_search(key,mid+1,high,k); else return bin_search(key,low,mid-1,k); int main() i

3、nt n , i , addr; int A10 = 2,3,5,7,8,10,12,15,19,21; cout 在下面的10个整数中进行查找 endl;for(i=0;i10;i+) cout Ai ; cout endl endl 请输入一个要查找的整数 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）运行界面查找成功查找失败2、用分治法求x的n次方，要求时间复

4、杂度为O(lgn)（1）源程序代码#include #include 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 你将进行x的n次方计算 endl endl;cout 请输入x： x;cout 请输入n： n; cout endl 计算结果： Pow

5、(x, n) endl endl; return 0;（2）运行界面3、自然合并排序算法（1）源程序代码#include 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(r

6、eci,reci+2-1,reci+1-1); num=pass(n); void merge(int fir,int end,int 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+; else tempArri=arrfir1+; for(int i=fir;i=end;i+) arri=tempArri;int p

7、ass(int n) int num=0; int biger=arr0; recnum+=0; for(int i=1;i=biger)biger=arri; else recnum+=i; biger=arri; recnum+=n; return num;int main() int n;cout请输入需要排序的整数个数：n) for(int i=0;in;i+)cout请输入整数：arri; mergeSort(n); cout排序结果为：endl;for(int i=0;in;i+)coutarri ; coutendlendl; cout请输入需要排序的整数个数：endl; ret

8、urn 0;（2）运行界面三、问题与讨论问题：分治法能解决的问题一般具有什么特征？解答：任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小越容易直接求解，解题所需的计算时间也越少。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治法所能解决的问题一般具有以下几个特征： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不

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