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

算法分析与设计实验报告专业班级： 姓 名： 学 号： 指导老师： 实验一 递归算法的设计与实现 计算整数的非负整数次幂(1)设计思路对于34按步骤可以分析： 34=32*32 32=31*31 31=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;return 1；一步步进行递归返回计算，如果n位奇数，在进行一部乘以x否则返回运算结果(2)源程序代码#includeusing namespace std;int power(int x,int n)int y;if(n=0)y=1;elsey=power(x,n/2);y=y*y; if(n%2=1)y=y*x;return y;void main() coutx; couty; if(y0) cout你的输入有误：请重新输入:y; int c; c=power(x,y); coutx的y次幂的结果是cendl;(3)代码运行结果 (4)时间复杂度 令n=2k，则可以得到：f(n)=g(k)=k+1=logn+1=O(logn)2.基于递归算法的插入排序(1)设计思路通过主函数传来一个数组的首地址和数组的长度，然后利用递归的原理，当n=0；程序返回，执行入栈的递归程序，依次比较2个数的大小，3个数的大小等，根据比较的结果将第n个数插入适当的位置。(2)源程序代码#includeusing namespace std;void insert (int a,int n)int k;int b;n=n-1;if(n0)insert(a,n);b=an;k=n-1;while(k=0)&(akb)ak+1=ak;k=k-1;ak+1=b;void main()int a100;int n;cout请输入数组A的元素个数n(1nn;cout请输入数组A的元素: ;for(int i=0;iai;insert(a,n);for(int j=0;jn;j+)coutaj ;coutendl;(3)代码运行结果 (4)时间复杂度f(n)=f(n-1)+n-1=f(n-2)+n-1+(n+2)=n*(n-1)/2;算法用于递归栈的工作单元数与n为同一数量级，即时间复杂度为O(n)实验二 递归算法的实现 自然归并算法的设计与实现 设计思路首先讲待排序的n个元素分成大致相同的子集合，然后分别对这两个子集进行排序最后将排好序的子集合归并成所要求的排好序的集合 源程序代码#include #include using namespace std;#define max 10void Merger_Sort(int a,int low,int high)int tempmax;if(lowhigh)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&j=high)if(aiaj)templ+=ai+;else templ+=aj+;while(i=mid)templ+=ai+;while(j=high)templ+=aj+;for(i=low;i=high;i+)ai=tempi; void main()int amax;int n;coutn;cout请输入n个元素: ;for(int i=0;iai;Merger_Sort(a,0,n-1);for(int j=0;jn;j+)coutaj ;coutendl;(3)代码运行结果(4)时间复杂度自然规定排序算法的时间复杂度为：O(n). 快速排序算法的设计与实现 设计思路基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列 源程序代码#includeusing namespace std;int Partition(int a,int p ,int r)int i = p,j=r+1,sub;int x = ap;while(true)while(a+ix&jx);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(pr)int q = Partition(a,p,r);QuickSort(a,p,q-1);/对左半段排序QuickSort(a,q+1,r);/对右半段排序 int main()int a100;int n;cout请输入数组元素个数n(0nn;cout请输入数组元素: ;for(int i=0;iai;QuickSort(a,0,n-1);for(int j=0;jn;j+)coutaj ;coutendl;(3)代码运行结果(4)时间复杂度快速排序算法在最坏的情况下的运行时间是O(n2)。如果选取数组中的中值元素作为划分元素，那么快速排序算法的时间复杂度应为O(nlogn)。此时快速排序算法的递归深度接近于logn。因此，快速排序算法的的空间复杂度应为为O(logn) 实验三 贪心算法的实现1.背包问题的设计与实现(1)设计思路将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为fi-1v；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-wi的背包中”，此时能获得的最大价值就是f i-1v-wi再加上通过放入第i件物品获得的价值vi。注意fv有意义当且仅当存在一个前i件物品的子集，其费用总和为fv。所以按照这个方程递推完毕后，最终的答案并不一定是fN V，而是fN0.V的最大值(2)源程序代码#include using namespace std;#define n 3struct thingfloat p;float w;float v;void quick (thing a,int b)int i;for(i=0;in;i+)ai.v=ai.p/ai.w;for(i=0;in;i+)for(int j=i+1;jn;j+)if(ai.vaj.v)thing 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(int i=0;in;i+)ai.v=ai.p/ai.w;xi=0;quick(a,n);m=M;for(i=0;in;i+)if(ai.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 main()int i;cout输入三种物品的价格：endl;thing an;for(i=0;iai.p;cout输入三种物品的重量：endl;for(i=0;iai.w;float m=20;float xn;float p=greedy(m,a,x,n);cout最佳解pendl; 代码运行结果(4)时间复杂度背包问题算法的时间复杂度为O(n)2.单源点最短路径问题的设计与实现(1)设计思路将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合。然后每次从T集合中选择S集合点中到T路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。直到T集合为空为止(2)源程序代码#include using namespace std; typedef struct adj_list int v_num; float len; struct adj_list *next; NODE; #define MAX_FLOAT_NUM 3.14e38f #define N 50 void dijkstra(NODE node, int n, int u, float d, int p) float temp; int i,j,t; bool *s = new booln; NODE *pnode; for( i=0; iv_num = pnode-len; ppnode-v_num = u; pnode = pnode-next; du = 0; su = true; for( i=1; in; i+) temp = MAX_FLOAT_NUM; t = u; for( j=0; jn; j+) if(!sj&djv_num & dpnode-v_num dt + pnode-len ) dpnode-v_num = dt + pnode-len; ppnode-v_num = t; pnode = pnode-next; delete s; void printWay(int i, int p) if(pi=-1)return; printWay(pi, p); coutchar(i+65); void println() cout-endl; int main() NODE nodeN; float dN; int pN; int n; int u; int i,v; NODE *pnode; coutn; cout请输入源顶点u编号（0u=nu; u-; cout请输入各个点到其他点的距离（输入顶点编号 距离，编号输入0表示结束）：endl; for( i=0; in; i+) cout顶点char(65+i)v&v0) pnode = new NODE; pnode-v_num = v-1; cin(pnode-len); pnode-next = nodei.next; nodei.next = pnode; dijkstra(node, n, u, d, p); println(); for( i=0; in; i+) if(u=i|di=MAX_FLOAT_NUM)continue; / coutchar(u+65)距离char(i+65)结点最短距离：diendl; cout路径：char(u+65); printWay(i, p); coutendl; println(); return 0; (3)代码运行结果(4)时间复杂度算法的时间主要消耗在将各种物品按照单位重量的价值从大到小的排序，因此，其时间复杂性为O(nlog2n)实验心得在计算机专业中，算法分析与设计是一门很重要的课