算法设计与分析：递归与分治法

1、应用数学 学院信息安全 专业班 学号姓名实验题日递归与分治法综合实验评分表指导教师评分标准序 号评分项目评分标准满分打分1完成度按要求独立完成实验准备、程序调试、实验报告撰 写。202实验内容（1）完成功能需求分析、存储结构设计；（2）程序功能完善、可正常运行；（3）测试数据正确，分析正确，结论正确。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个整数中进行查找 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;elsecout endl n ”不在上述的整数中” 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请输入需要排序的整数个数：n)for(int i=0;in;i+)cout请输入整数：arri;mergeSort(n);cout排序结果为：endl;for(int i=0;in;i+)coutarri;coutendlendl;cout请输入需要排序的整数个数：endl;return 0;C :Win d owssyste m 3 2cm d. exe请输入需要排序的整数个数:请输入整数：请输入整数：请输入整数：请输入整数：62请输入整数：请输入整数：却序结果

8、为：4 12 13 32 45 62请输入需要排序的整数个数:搜狗拼音输入法全：三、问题与讨论问题：分治法能解决的问题一般具有什么特征？解答：任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。 问题的规模越小越容易直接求解，解题所需的计算时间也越少。分治法的设计思 想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各 个击破，分而治之。分治法所能解决的问题一般具有以下几个特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若十个规模较小的相同问题，即该问题具有最优子 结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）

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