算法分析与设计实验报告

组员学号姓名实验名称算法实验整体框架的构建实验室实验目的或要求1.实验题目算法实验主菜单的设计。2．实验目的⑴熟悉实验环境VC＋＋6.0；⑵复习C、C++语言以及数据结构课程的相关知识，实现课程间的平滑过度；3.实验要求1）设计的主菜单可以是图形模式的，也可以是控制台模式的。以控制台为例，主菜单大致如下： －－－－－－－－－－－－－－－－－－－－－－－－－ 《算法设计与分析》实验 －－－－－－－－－－－－－－－－－－－－－－－－－算法分析基础——Fibonacci序列问题分治法在数值问题中的应用——最近点对问题减治法在组合问题中的应用——8枚硬币问题变治法在排序问题中的应用——堆排序问题动态规划法在图问题中的应用——全源最短路径问题 99. 退出本实验 －－－－－－－－－－－－－－－－－－－－－－－－－请输入您所要执行的操作（1，2，3，4，5，99）：2）点击操作后进入相应的实验项目或是相应项目的下一级菜单；3）可以反复执行，直到退出实验。程序代码voidshow(){printf("\n");printf("|－－－－－－－－－－－－－－－－－－－－－－－－－－|\n");printf("||\n");printf("|《算法设计与分析》实验|\n");printf("||\n");printf("|－－－－－－－－－－－－－－－－－－－－－－－－－－|\n");printf("|1.算法分析基础——Fibonacci序列问题|\n");printf("||\n");printf("|2.分治法在数值问题中的应用——最近点对问题|\n");printf("||\n");printf("|3.减治法在组合问题中的应用——8枚硬币问题|\n");printf("||\n");printf("|4.变治法在排序问题中的应用——堆排序问题|\n");printf("||\n");printf("||\n");printf("|99.退出本实验|\n");printf("|－－－－－－－－－－－－－－－－－－－－－－－－－－|\n");printf("\n");printf("*请输入您所要执行的操作（1，2，3，4，5，99）：\n");printf("\n");}实验结果及分析实验名称算法分析基础——Fibonacci序列问题实验室实验目的或要求实验题目给定一个非负整数n，计算第n个Fibonacci数实验目的1）理解递归算法和迭代算法的设计思想以及递归程序的调式技术2）掌握并应用递归算法和迭代算法效率的理论分析(前验分析)和实际分析(后验分析)方法；3）理解这样一个观点：不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同；实验要求1）使用教材2.5节中介绍的迭代算法Fib(n),找出最大的n,使得第n个Fibonacci数不超过计算机所能表示的最大整数，并给出具体的执行时间；2）对于要求1),使用教材2.5节中介绍的递归算法F(n)进行计算,同样给出具体的执行时间，并同1)的执行时间进行比较；3）对于输入同样的非负整数n，比较上述两种算法基本操作的执行次数；4）对1)中的迭代算法进行改进，使得改进后的迭代算法其空间复杂度为Θ(1)；5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。实验原理（算法基本思想）F(n)//根据定义，递归计算第n个斐波那契数//输入：一个非负数n//输出：第几个斐波那契数ifn≤1returnnelsereturnF(n-1)+F(n-2)程序代码intFib1(intn){ints[48],i;s[0]=0;s[1]=1;for(i=2;i<=n;i++)s[i]=s[i-1]+s[i-2],time1++;returns[n];}intFib2(intn){longintf;if(n>1){f=Fib2(n-1)+Fib2(n-2),time2++;returnf;}if(n<2){time3++; returnn;}time3=time3+time2;}实验结果及分析实验名称分治法在数值问题中的应用——最近点对问题实验室实验目的或要求实验题目设p1=(x1,y1),p2=(x1,y2),……,pn=(xn,yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。实验目的1）提高应用蛮力法设计算法的技能；2）深刻理解并掌握分治法的设计思想；3）理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对其进行改进，以提高算法的效率。实验要求1）设计并实现用BF方法求解最近点对问题的算法；2）设计并实现用DAC方法求解最近点对问题的算法；3）以上两种算法的输入既可以手动输入，也可以自动生成；4）算法不仅要输出最近点对的距离，还要输出最近点对的两个点；5）对上述两个算法进行时间复杂性分析，并设计实验程序验证分析结果；6）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。实验原理（算法基本思想）程序代码voiddian(){time_tc_start1,c_end1;c_start1=clock();ints[100],f[100],i,j,t,a,b,c,d,n;printf("蛮力法求最近点问题");printf("\n请输入坐标数:");scanf("%d",&n);for(t=0;t<n;t++){ scanf("%d",&s[t]); scanf("%d",&f[t]);}doublel,k;k=sqrt((s[1]-s[0])*(s[1]-s[0])+(f[1]-f[0])*(f[1]-f[0]));a=s[1];b=f[1];c=s[0];d=f[0];for(i=0;i<n;i++){ for(j=i+1;j<=n;j++){l=sqrt((s[j]-s[i])*(s[j]-s[i])+(f[j]-f[i])*(f[j]-f[i]));if(k>l) {k=l;a=s[j];b=f[j];c=s[i];d=f[i]; } }} c_end1=clock(); printf("\n最近的距离为：%f\n",k);printf("\n他们的坐标分别为：(%d,%d),(%d,%d)\n",a,b,c,d);printf("\n此方法所花时间为:%f",difftime(c_end1,c_start1)/18.2);}typedefstruct{doublex;doubley;}pttype;longarr[maxsize];longarr1;pttypept[maxsize];intsortcmp(constvoid*a,constvoid*b){if(((pttype*)a)->x<((pttype*)b)->x)return-1;elsereturn1;}intarrcmp(constvoid*a,constvoid*b){if(((pttype*)a)->y<((pttype*)b)->y)return-1;elsereturn1;}doubledis(pttypea,pttypeb){returnsqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}doublegetMin(doublea,doubleb){if(a<b)returna;elsereturnb;}doubleshortest(longleft,longright){if(right-left==1)//两个点returndis(pt[left],pt[right]);if(right-left==2)//三个点returngetMin(getMin(dis(pt[left],pt[left+1]),dis(pt[left],pt[right])),dis(pt[left+1],pt[right]));/*枚举个点和个点的情况，当边界使用*///大于用分治法longi,j,mid=(left+right)/2;doublecurmin=getMin(shortest(left,mid),shortest(mid+1,right));arr1=0;for(i=mid;i>=left&&pt[mid+1].x-pt[i].x<=curmin;i--)arr[arr1++]=i;//确定左边-d内的点for(i=mid+1;i<=right&&pt[i].x-pt[mid].x<=curmin;i++)arr[arr1++]=i;//确定右边+d内的点qsort(arr,arr1,sizeof(arr[0]),arrcmp);//按y排序for(i=0;i<arr1;i++)for(j=i+1;j<arr1&&pt[arr[j]].y-pt[arr[i]].y<=curmin;j++)curmin=getMin(curmin,dis(pt[arr[i]],pt[arr[j]]));returncurmin;}实验结果及分析实验名称减治法在组合问题中的应用——8枚硬币问题实验室实验目的或要求实验题目在8枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测这枚假币。实验目的1）深刻理解并掌握减治法的设计思想并理解它与分治法的区别；2）提高应用减治法设计算法的技能。3）理解这样一个观点：建立正角的模型对于问题的求解是非常重要的。实验要求1）设计减治算法实现8枚硬币问题；2）设计实验程序，考察用减治技术设计的算法是否高效；3）扩展算法，使之能处理n枚硬币中有一枚假币的问题。实验原理（算法基本思想）程序代码intjiabi(ints[],intn,inti){intl[1000];intr=0,t,k,y,x,a,b,c=0,f,e;k=n+i;f=i;if(n>=3){if(n%2==0){ t=n/2;for(e=i;e<i+t;e++)y+=s[e];for(e=i+t;e<n+i;e++)x+=s[e];if(y>x){for(e=i;e<i+t;e++)l[e]=s[e];returnjiabi(l,t,f);}c=0;if(x>y){for(e=i+t;e<n+i;e++)l[e]=s[e];returnjiabi(l,t,f+t);} if(y==x) printf("没有假币！！！");}if(n%2==1){a=(n-1)/2;for(e=i;e<i+a;e++)y+=s[e];for(e=a+i;e<i+n-1;e++) x+=s[e];b=s[k-1];if(y>x){for(e=i;e<i+a;e++)l[e]=s[e];returnjiabi(l,a,f);}if(x>y){for(e=a+i;e<i+n-1;e++)l[e]=s[e];returnjiabi(l,a,f+a);}if(x==y)printf("第%d个是假币",k);}}if(n==2){if(s[i]>s[i+n-1]) printf("第%d个是假币",i+1); if(s[i]<s[i+n-1]) printf("第%d个是假币",n+i);}if(n==1)printf("第%d个是假币",i+1);}实验结果及分析实验名称变治法在排序问题中的应用——堆排序问题实验室实验目的或要求实验题目用基于变治法