算法分析与设计实验报告

1、算法分析与设计实验报告专业班级：姓 名:学 号:指导老师:实验一递归算法的设计与实现?计算整数的非负整数次幕(1) 设计思路对于34按步骤可以分析3 4=3 2*323 2=3 1*313 1=3 1*1对于33按步骤可以分析3 3=3 2*3 13 2=3 1*33 1=3 1*1分析可以得到：当xn中n为奇数时，Xn=X*(X n/2 )2当xn中n为偶数的，xn= (xn/2)2当 n/2=0;return 1；部乘以x一步步进行递归返回计算 ，如果n位奇数，在进行否则返回运算结果(2) 源程序代码#in clude<iostream>using n amespace std

2、;int power(i nt x,i nt n)int y;if(n=0)y=i;elsey=power(x ,n/2); y=y*y;if(n %2=1)y=y*x;return y;void mai n()cout<<"请输入一个底数X:"int x;cin> >x;cout<<"请输入一个指数 Y:"int y;cin»y;if(y<o)cout<<" 你的输入有误：请重新输入:"<<endl; cin»y;int c;c=power(x,y

3、);cout<<x<<" 的"<<y<<"次幕的结果是"<<c<<endl;(3) 代码运行结果(4) 时间复杂度令 n=2 k,则可以得到:f(n)=g(k)=k+1=logn+1= O(logn)2.基于递归算法的插入排序(1) 设计思路通过主函数传来一个数组的首地址和数组的长度，然后利用递归的原理，当n=0 ;程序返回，执行入栈的递归程序，依次比较2个数的大小，3个数的大小等，根据比较的结 果将第n个数插入适当的位置。(2) 源程序代码#in clude<iostream

4、> using n amespace std;void in sert (int a,i nt n)int k;int b;n=n _1;if(n >0)in sert(a ,n);b=a n;k=n-1;while(k>=0)&&(ak>b)ak+1=ak;k=k-1;ak+1=b;void mai n()int a100;int n;n(1< n< 100):"cout<<"请输入数组A的元素个数cin»n;cout<<"请输入数组 A的元素："；for(i nt

5、i=0;i <n ;i+)cin> >ai;in sert(a ,n);for(i nt j=O;j <n ;j+)cout<<aj<<""cout<<e ndl;(3) 代码运行结果(4) 时间复杂度f(n )=f( n-1)+n-1=f(n-2)+n-1+( n+2)=n*(n-1)/2;算法用于递归栈的工作单元数与n为同一数量级，即时间复杂度为 O(n)实验二递归算法的实现?自然归并算法的设计与实现?设计思路首先讲待排序的n个元素分成大致相同的子集合 ，然后分别对这两个子集进行排序最后将排好序的子集合归并成所

6、要求的排好序的集合?源程序代码#i nclude <stdio.h>#in elude <iostream> using n amespace std;#defi ne max 10 void Merger_Sort(i nt a,i nt low,i nt high) int tempmax;if(low<high)int mid=(low+high)/2;int i=low;int j=mid+1;int l=low;Merger_Sort(a,low,mid);Merger_Sort(a,mid+1,high); while(i<=mid&&a

7、mp;j<=high)if(ai<aj)templ+=ai+;elsetempl+=aj+;while(i<=mid)templ+=ai+;while(j<=high)templ+=aj+;for(i=low;i<=high;i+)ai=tempi;void mai n()int amax;n:"个元素："int n;cout<<"请输入元素个数cin»n;cout<<"请输入"<<n<<" for(i nt i=0;i <n ;i+)cin

8、> >ai;Merger_Sort(a,0, n-1);for(i nt j=O;j <n ;j+)cout<<aj<<""cout<<e ndl;(3)代码运行结果(4)时间复杂度自然规定排序算法的时间复杂度为：0(n).?快速排序算法的设计与实现?设计思路基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行，以此达到整个数据变成有序序列?源程序代码#in clude<iostream>

9、;using n amespace std;int Partiti on (i nt a,i nt p ,int r)int i = p,j=r+1,sub;int x = ap;while(true)while(a+i<x&&j<r);while(a-j>x);if(i>=j) break;sub = ai;ai = aj;aj =sub;ap = aj;aj =x;return j;void QuickSort(int a,int p,int r)if(P<r)int q = Partiti on (a,p,r);QuickSort(a,p,q

10、-1);对左半段排序QuickSort(a,q+1,r);对右半段排序int mai n()int a100;int n;cout<<"请输入数组元素个数 n(0< n <100):"cin»n;cout<<"请输入数组元素："；for(i nt i=0;i <n ;i+)cin> >ai;QuickSort(a,0, n-1);for(i nt j=0;j <n ;j+)cout<<aj<<""cout<<e ndl;(3)代码

11、运行结果(4)时间复杂度快速排序算法在最坏的情况下的运行时间是0(n2)。如果选取数组中的中值元素作为划分元素，那么快速排序算法的时间复杂度应为0(nlogn)。此时快速排序算法的递归深度接近于logn。因此，快速排序算法的的空间复杂度应为为O(logn)实验三贪心算法的实现1. 背包问题的设计与实现(1) 设计思路将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略(放或不放)，那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为 前i-1件物品放入容量为v的背包中”，价值为fi-1v；如果放第i件物品，那么问题就转化为前i-1件物品放入剩下

12、的容量为 v-wi的背包中”，此时能获得的最大价值就是f i-1v-wi再加上通过放入第i件物品获得的价值 vi。注意fv有意义当且仅当存在一个前i件物品的子集，其费用总和为fv。所以按照这个方程递推完毕后，最终的答案并不一定是fN V，而是fN0.V的最大值(2) 源程序代码#in elude <iostream>using n amespace std;#defi ne n 3struct thi ngfloat p;float w;float v;；void quick (th ing a,i nt b)int i;for(i=0;i< n;i+)ai.v=ai.p/a

13、i.w;for(i=0;i< n;i+)for(i nt j=i+1;j <n ;j+)if(ai.v<aj.v)thi ng b;b.v=ai.v;b.p=ai.p;b.w=ai.w;ai.p=aj.p;ai.v=aj.v; ai.w=aj.w; aj.p=b.p;aj.v=b.v;aj.w=b.w;float greedy(float M,thing a,float x,int b)float m,p=0;for(i nt i=0;i <n ;i+)ai.v=ai.p/ai.w;xi=0;quick(a ,n);m=M;for(i=0;i< n;i+)if(a

14、i.w<=m)xi=1;m=m-ai.w;P=P+ai.p；elsexi=m/ai.w;p=p+xi*ai.p;break;return p;void mai n()int i;cout<<"输入三种物品的价格 ："<<endl;thi ng an;for(i=0;i< n;i+)cin> >ai.p;cout<<"输入三种物品的重量 ："<<endl;for(i=0;i< n;i+)cin> >ai.w;float m=20;float xn;float p=gr

15、eedy(m,a,x ,n);cout<<"最佳解"<<p<<endl;?代码运行结果(4)时间复杂度背包问题算法的时间复杂度为0(n)2. 单源点最短路径问题的设计与实现(1) 设计思路将图G中所有的顶点 V分成两个顶点集合 S和T。以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点 v,T则是尚未确定到源点 v最短路径的顶点集合。 然后每次从T集合中选择S集合点中到T路径最短的那个点，并加入到集合S中，并把这 个点从集合T删除。直到T集合为空为止(2) 源程序代码#in clude<iostream>usin

16、g n amespace std;typedef struct adj_listint v_num;float le n;struct adj_list *n ext;NODE;#defi ne MAX_FLOAT_NUM 3.14e38f#defi ne N 50void dijkstra(NODE node, int n, int u, float d, int p)float temp;int i,j,t;bool *s = new bool n;NODE *pn ode;for( i=0; i<n; i+)di = MAX_FLOAT_NUM;si = false;pi = -1

17、;if(!(p node = no deu. next)return;while(p no de)dp no de->v_ num = pno de->le n;pp no de->v_ num = u;pnode = pno de->n ext;du = 0;su = true;for( i=1; i<n; i+)temp = MAX_FLOAT_NUM;t = u;for( j=0; j< n; j+)if(!sj&&dj<temp)t = j;temp = dj;if(t=u)/break;st = true;pnode = no

18、 det. next;while(p no de)if(!sp no de->v_ num && dp no de->v_ num > dt + pno de->le n )dp no de->v_ num = dt + pno de->le n;pp no de->v_ num = t;pnode = pno de->n ext;delete s;void printWay(int i, int p)if(pi=_1)return;prin tWay(pi, p);cout<<"->"<

19、;<char(i+65);void prin tl n()"<<endl;cout<<"int mai n()NODE nodeN;float dN;int pN;int n;int u;int i,v;NODE *pn ode;cout<<"请输入顶点个数cin»n;cout<<"请输入源顶点 u编号(0<u<="<<*<")："cin»u;u-;cout<<" 请输入各个点到其他点的距离（输入顶点

20、编号距离，编号输入0表示结束)："<<endl;for( i=0; i<n; i+)cout<<" 顶点"<<char(65+i)<<"nodei = *( new NODE); /创建新结点no dei.v_ num = i;no dei.le n = 0;nodei. next = NULL;while(ci n»v&&v>0) pnode = new NODE; pno de->v_ num = v-1;cin> >(p no de->le n);pno de->n ext = no dei. next;no dei. next = pno de;dijkstra( no de, n, u, d, p);println();for( i=0; i<n; i+)if(u=i|di=MAX_FLOAT_NUM)co nti nue; /cout<<char(u+65)<<"距离"<<char(i