算法分析与设计实验报告.doc

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

1、下载可编辑算法分析与设计实验报告专业班级：姓名：学号：指导老师：.专业.整理.下载可编辑实验一递归算法的设计与实现•计算整数的非负整数次幂(1)设计思路对于34按步骤可以分析：34=32*3232=31*3131=31*1对于33按步骤可以分析：33=32*31；32=31*31；31=31*1；分析可以得到：当xn中n为奇数时，xn=x*(xn/2)2当xn中n为偶数的，xn=（xn/2）2；当n/2=0;return1；一步步进行递归返回计算，如果n位奇数，在进行一部乘以x否则返回运算结果(2)源程序代码#include.专业.整理.下载可编辑using

2、namespacestd;intpower(intx,intn){inty;if(n==0){y=1;}else{y=power(x,n/2);y=y*y;if(n%2==1){y=y*x;}}returny;}voidmain().专业.整理.下载可编辑{cout<<"请输入一个底数X：";intx;cin>>x;cout<<"请输入一个指数Y:";inty;cin>>y;if(y<0){cout<<"你的输入有误：请重新输入:"<>y;}intc;c=power(x,y);cout<

3、理.下载可编辑(3)代码运行结果(4)时间复杂度令n=2k，则可以得到：f(n)=g(k)=k+1=logn+1=O(logn)2.基于递归算法的插入排序(1)设计思路通过主函数传来一个数组的首地址和数组的长度，然后利用递归的原理，当n=0；程序返回，执行入栈的递归程序，依次比较2个数的大小，3个数的大小等，根据比较的结果将第n个数插入适当的位置。.专业.整理.下载可编辑(2)源程序代码#includeusingnamespacestd;voidinsert(inta[],intn){intk;intb;n=n-1;if(n>0){insert(a,n);b

4、=a[n];k=n-1;while((k>=0)&&(a[k]>b)){a[k+1]=a[k];k=k-1;}a[k+1]=b;}}.专业.整理.下载可编辑voidmain(){inta[100];intn;cout<<"请输入数组A[]的元素个数n(1>n;cout<<"请输入数组A[]的元素:";for(inti=0;i>a[i];}insert(a,n);for(intj=0;j

5、n-1)+n-1=f(n-2)+n-1+(n+2)=n*(n-1)/2;算法用于递归栈的工作单元数与n为同一数量级，即时间复杂度为O(n)实验二递归算法的实现•自然归并算法的设计与实现•设计思路首先讲待排序的n个元素分成大致相同的子集合，然后分别对这两个子集进行排序最后将排好序的子集合归并成所要求的排好序的集合.专业.整理.下载可编辑•源程序代码#include#includeusingnamespacestd;#definemax10voidMerger_Sort(inta[],intlow,inthigh){inttemp[max];i

6、f(low

7、]=temp[i];}}}voidmain().专业.整理.下载可编辑{inta[max];intn;cout<<"请输入元素个数n:";cin>>n;cout<<"请输入"<>a[i];}Merger_Sort(a,0,n-1);for(intj=0;j