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

《算法设计与分析：递归与分治法-实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、找的递归算法（1）源程序代码#include#includeusingnamespacestd;intbin_search(intkey[],intlow,inthigh,intk){intmid;if(low>high)return-1;else{mid=(low+high)/2;if(key[mid]==k)returnmid;if(k>key[mid])returnbin_search(key,mid+1,high,k);elsereturnbin_search(key,low,mid-1,k);}}intmain(){intn,i,a

3、ddr;intA[10]={2,3,5,7,8,10,12,15,19,21};cout<<"在下面的10个整数中进行查找"<>n;addr=bin_search(A,0,9,n);if(-1!=addr)cout<

4、行界面①查找成功②查找失败2、用分治法求x的n次方，要求时间复杂度为O(lgn)（1）源程序代码#include#includeusingnamespacestd;intPow(intx,intn){if(n==1)returnx;elseif(n>1){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次方计算"<>x;cou

5、t<<"请输入n："<>n;cout<usingnamespacestd;constintSIZE=100;intarr[SIZE];intrec[SIZE];voidmerge(intfir,intend,intmid);intpass(intn);voidmergeSort(intn);voidmergeSort(intn){intnum=pass

6、(n);while(num!=2){for(inti=0;imid)tempArr[i]=arr[fir2++];elseif(fir2>end)tempArr[i]=arr[fir1++];elseif(arr[fir1]>arr[fir2])tempAr

7、r[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;i=biger)biger=arr[i];else{rec[num++]=i;biger=arr[i];}}rec[num++]=n;