算法分析及设计实验报告.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)源程序代码#includeusingnamespacestd;intpower(

2、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、)=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=a[n];k=n-1;while((k>=0)&&(a[k]>b)){a[k+1]=a[k];

4、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、O(n)实验二递归算法的实现•自然归并算法的设计与实现•设计思路首先讲待排序的n个元素分成大致相同的子集合，然后分别对这两个子集进行排序最后将排好序的子集合归并成所要求的排好序的集合专业资料•源程序代码#include#includeusingnamespacestd;#definemax10voidMerger_Sort(inta[],intlow,inthigh){inttemp[max];if(low

6、,low,mid);Merger_Sort(a,mid+1,high);while(i<=mid&&j<=high){if(a[i]>n;cout<<"请输入"<

7、<"个元素:";for(inti=0;i>a[i];}Merger_Sort(a,0,n-1);for(intj=0;j