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

应用数学学院信息安全专业班学号姓名实验题目递归与分治法综合实验评分表指导教师评分标准序号评分项目评分标准满分打分1完成度按要求独立完成实验准备、程序调试、实验报告撰写。202实验内容（1）完成功能需求分析、存储结构设计；（2）程序功能完善、可正常运行；（3）测试数据正确，分析正确，结论正确。303实验报告内容齐全，符合要求，文理通顺，排版美观。404总结对实验过程遇到的问题能初步独立分析，解决后能总结问题原因及解决方法，有心得体会。10实验报告一、实验目的与要求1.掌握递归算法的设计思想2.掌握分治法设计算法的一般过程3.理解并掌握算法渐近时间复杂度的分析方法二、实验内容1、折半查找的递归算法（1）源程序代码#includeStdAfx.h#includeiostreamusingnamespacestd;intbin_search(intkey[],intlow,inthigh,intk){intmid;if(lowhigh)return-1;else{mid=(low+high)/2;if(key[mid]==k)returnmid;if(kkey[mid])returnbin_search(key,mid+1,high,k);elsereturnbin_search(key,low,mid-1,k);}}intmain(){intn,i,addr;intA[10]={2,3,5,7,8,10,12,15,19,21};cout在下面的10个整数中进行查找endl;for(i=0;i10;i++){coutA[i];}coutendlendl请输入一个要查找的整数endl;cinn;addr=bin_search(A,0,9,n);if(-1!=addr)coutendln是上述整数中的第addr个数endl;elsecoutendln不在上述的整数中endlendl;getchar();return0;}（2）运行界面①查找成功②查找失败2、用分治法求x的n次方，要求时间复杂度为O(lgn)（1）源程序代码#includeStdAfx.h#includeiostreamusingnamespacestd;intPow(intx,intn){if(n==1)returnx;elseif(n1){ints;intm=n/2;s=Pow(x,m);if(n%2==0)return(s*s);elsereturn(s*s*x);}}intmain(){intx,n;cout你将进行x的n次方计算endlendl;cout请输入x：endl;cinx;cout请输入n：endl;cinn;coutendl计算结果：Pow(x,n)endlendl;return0;}（2）运行界面3、自然合并排序算法（1）源程序代码#includeStdAfx.h#includeiostreamusingnamespacestd;constintSIZE=100;intarr[SIZE];intrec[SIZE];voidmerge(intfir,intend,intmid);intpass(intn);voidmergeSort(intn);voidmergeSort(intn){intnum=pass(n);while(num!=2){for(inti=0;inum;i+=2)merge(rec[i],rec[i+2]-1,rec[i+1]-1);num=pass(n);}}voidmerge(intfir,intend,intmid){inttempArr[SIZE];intfir1=fir,fir2=mid+1;for(inti=fir;i=end;i++){if(fir1mid)tempArr[i]=arr[fir2++];elseif(fir2end)tempArr[i]=arr[fir1++];elseif(arr[fir1]arr[fir2])tempArr[i]=arr[fir2++];elsetempArr[i]=arr[fir1++];}for(inti=fir;i=end;i++)arr[i]=tempArr[i];}intpass(intn){intnum=0;intbiger=arr[0];rec[num++]=0;for(inti=1;in;i++){if(arr[i]=biger)biger=arr[i];else{rec[num++]=i;biger=arr[i];}}rec[num++]=n;returnnum;}intmain(){intn;cout请输入需要排序的整数个数：endl;while(cinn){for(inti=0;in;i++){cout请输入整数：endl;cinarr[i];}mergeSort(n);cout排序结果为：endl;for(inti=0;in;i++){coutarr[i];}coutendlendl;cout请输入需要排序的整数个数：endl;}return0;}（2）运行界面三、问题与讨论问题：分治法能解决的问题一般具有什么特征？解答：任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小越容易直接求解，解题所需的计算时间也越少。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治法所能解决的问题一般具有以下几个特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。四、总结这次实验的内容都很有代表性，通过上机操作实践与对问题的思考，让我更深层地领悟到了分治法的效率。分治法的基本思路并不难理解，就是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，在计算机的处理当中，问题的规模越小就越容易直接求解，解题所需的计算时间也越少，所以分治法在合适的问题中是能大大提高效率的。我非常喜欢上机课，因为课上听的理论内容也许觉得懂了，但课后没有一些实践，于是对一些难点实际上掌握得并不好。刚看到课题的实验内容，其实基本思路和条理还是会有的，因为会有一定的知识基础，能够想到一些相关的解决思路，但有思路不一定就能够解决问题，真正动手去做的时候才发现会出现更多的实际问题。解决遇到的问题就是我们学习的过程，同时也能让我注意到一些以前不曾在意的问题。像我是使用C++来写代码的，其中我这次实验时我就发现，“#include“StdAfx.h””一定要放在首行，不然就会出错；调试程序时如果出现“CannotfindoropenthePDBfile”的提示而导致程序不能正常运行时，按Ctrl+F5来直接执行就能正常运行了，因为这跟系统环境有关系；等等。每次的实践都能有一些发现，不管是大是小，积累多了就成了自己丰富的经验。所以我还是挺喜欢实验课的，能进行一些实用性很强的实践，更深层地领悟到书本的理论知识，同时还能享受把bug逐个解决的快感。