还剩20页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
学号姓名组员实验名称算法实验整体框架的构建实验室.实验题目1算法实验主菜单的设计实验目的
2.熟悉实验环境;1VC++
6.0复习语言以及数据结构课程的相关知识,实现课程间的平滑过度;2C.C++.实验要求3设计的主菜单可以是图形模式的,也可以是控制台模式的以控制台为例,主菜单大致如1下实验目的或要求《算法设计与分析》实验算法分析基础序列问题1---------------------------.Fibonacci分治法在数值问题中的应用——最近点对问题
2.减治法在组合问题中的应用——枚硬币问题
3.8变治法在排序问题中的应用——堆排序问题
4.动态规划法在图问题中的应用——全源最短路径问题
5.退出本实验
99.请输入您所要执行的操作1,2,3,4,5,99:点击操作后进入相应的实验项目或是相应项目的下一级菜单;2c*C:\Docuent sand Settings\Adinist rat or\^S\Debug\*H.exe.退出本实验99*请输入您所要执行的操作1,2,3,%5,99再输入你的选择2有两肝方甚求曩近点问题,工选择蛮力法,选择分治法裁力法求最近问题21E播输入坐标数4I0实R5验21港近的距离为们的坐标分别为」,卜匕方法所花时间为
1.414214k
2815.604396结果cl*C:\Docuent sand Set tings\Adini strator\桌面Debug■・exe及.退出本实验!99分*请输入您所要执行的操作1,2,3,4,5,99析请输入你的选择2有两种方法求最近点问题,选择蛮力法,选择分治法122分艳色率最返点问题请输川全标点教4局输入各个坐标的位置00£8b5最近点距离为
2.236068减治井在绢今间层页中的应用8%实验名称(/灰彳口1出口实验室堂乂IHJ1n J/22L/IJ4实验题目在枚外观相同的硬币中,有一枚是假币,并且已知假币与真币的重量不同,但不知道8假币与真币相比较轻还是较重可以通过一架天平来任意比较两组硬币,设计一个高效的算法实来检测这枚假币实验目的)深刻理解并掌握减治法的设计思想并理解它与分治法的区别;1验)提高应用减治法设计算法的技能2目的或)理解这样一个观点建立正角的模型对于问题的求解是非常重要的3实验要求要)设计减治算法实现枚硬币问题;18求)设计实验程序,考察用减治技术设计的算法是否高效;2)扩展算法,使之能处理枚硬币中有一枚假币的问题3n)扩展算法,使之能处理〃枚硬币中有一枚假币的问题3实验原理(算法基本想)int jiabiint s[],int n,int iint1E1000];int r=0,t,k,y,x,a,b,c=0,f,e;k=n+i;;f=iifn=3ifn%2=0t=n/2;for e=i;ei+t;e++y+=s[e];for e=i+t;en+i;e++x+=s[e];ifyxfor e=i;ei+t;e++l[e]=s[e];return jiabi1,t,f;c=0;ifxyfor e=i+t;en+i;e++l[e]=s[e];return jiabi1,t,f+t;}if y==x〃没有假币!!!〃;printfifn%2=la=n-l/2;for e=i;ei+a;e++y+=s[e];〈for e=a+i;e i+n-1;e++x+=s[e];b=s[k-l];ifyx〈for e=i;e i+a;e++l[e]=s[e];return jiabi1,a,f;if xyfore=a+i;ei+n-l;e++l[e]=s[e];return jiabi1,a,f+a;if x=y〃第个是假币〃,printf%d k;}if n==2if s[i]s[i+n-1]〃第个是假币〃,printf%d i+1;ifs[i]s[i+n-l]〃第%个是假币〃,printf dn+i;}if n==l〃第个是假币〃,printf%d i+1;分治法在数值问题中的应用一一最近点对问题
2.减治法在组合问题中的应用一一枚硬币问题实3,8变治法在排序问题中的应用一一堆排序问题4,验.退出本实验99结*请输入您所要执行的操作(,)12,3,4,5,99果请你的选硬币总及请你要求数:3露院B T54硬■--量分法E-与-p硬l um--mt5三--量h-h1请入雪p55硬.Q一9-m12I量析请请入入耳-r J5-r装硬由」.t lI■31J l=一t-h-m量11请入耳J5-、4n---h-量r J1-m请入耳^彳2硬.一-:L3t lh1I.c\*C:\Docuent sand Settings\Adinist rator\Debug\W-exe变治法在排序问题中的应用——堆排序实验名称实验室问题JA IJAI;----实验题目用基于变治法的堆排序算法对任意一组给定的数据进行排序实验目的)深刻理解并掌握变治法的设计思想;1)掌握堆的概念以及如何用变治法把任意给定的一组数据改变成堆;2实验目的)提高应用变治法设计算法的技能3或要求实验要求)设计与实现堆排序算法;1)待排序的数据可以手工输入(通常规模比较小,个数据左右),用以检测程序的正确性;也210可以计算机随机生成(通常规模比较大,个数据左右),用以检验(用计数法)堆1500—3000排序算法的时间效率实验原理(算法基本思想)void dui_sortint c[],int m〃排序前顺序:〃;{printffor intg=l;gm+l;g++〃printf%d,,c[g];}〃〃printf\n;int e=0;forint s=m;m0;m--{e++;dui c,m;程〃第次建堆后的顺序〃,printf%d e;for inth=l;hs+l;h++序printf%d,,c[h];代〃〃printf\n;码jiao_huan2c[l],c[m];〃求的当前最大值为%〃printf d:\n,c[m];〃排好序后的数组顺序为〃;printf〈for inth=l;h s+l;h++printf%d,,c[h];〃〃printf\n;c\C:\DocuMervts andSettingslAdBinistrator\桌面Debug■・exe*请输入您所要执行的操作(工,)实2,3,4,5,99云自青验____是数随机输入青一数歌圣21不青二且且结月一麻页非果及一一分・析♦-Bmf.x-E-BnfM-4;2:6:6-900-0■0288625♦06■86865292♦508655825♦9069,69,70,71,73,76,78,78,81,82,82,84,88,90,90,91,91,92,93,94,95,95,99,用的当前最大值为3第次建堆后的顺序工,」,,,,982,03,4,5,5,6,6/8,11,11,12/
6161818.2122,
23.23,
23.24,26「」「」」26,27-27,29,29,29,
29.31,33,34,3535,36,37-
37.3838,34040,41,41,41,41,42,4242,44,44,45,46,47,47,48,48,50,53,53,54,56,57,58,59,61,62,62,64,64,64,66,67,67,68,69,69,70,71,73,76,78,78,81,82,82,84,88,90,
90.91,91,92,93,94,95,95,99,国的当前最去值为2第次建堆后的顺序式「」」「「」「」,,9902,345,5-6,6-8-11,1121616,18/8,2122,2323,23一一「.一,,,242626-27-27,29,29,
2929.3133,34-35,35,
36.37-37,38,38,39,
404041.4141,41,42,42/42,44,44,45,46,47,47,48,48,50,53,53,54,56,57,58,59,61,62,62,64,64,64,66,67,67,68,69,69,70,71,73,76,78,78,81,82,82,84,88,90,90,91,91,92,93,94,95,95,99,果的当前最大酒为1第次建堆后的顺序「,1000,1,23455,6,6,81111,12,16,16,18,18,21,22,23,23,23,24,26,26,27,27,29,29,29,29,31,33,34,35,35,36,37,37,38,38,39,40,40,41,41,41,41,42,42,,42,44,44,45,46,47,4748,48,50,53,53,54,56,57,58,59,6T,62,62,64,64,64,66’6「67,68,69,69,70,71,73,76,78,78,81,82,82,84,88,90,90,91,91,92,93,94,95,95,99,求的当前最大值为0推好序后的数组顺序为「「」「」「「」01-
234.
556.6,
8.1111_1216_16_18-18_
21.-2223「」2323,24「;26,26,27,27,29,29,29,29,31,33,34,35,35,36,37,37,38,38,39,40,40,41,41,41,41,42,4242,44,44,45,46,
47.47,48,48,50,53,
53.
54.56,S
7.
58.
59.61,62,62,64,64,64,66,67,
67.68,69,69,70,71,73,76,78,78,81,82,82,84,88,90,90,91,91,92,93,94,95,95,99,心得体会成绩教师签名:评定可以反复执行,直到退出实验3可以反复执行,直到退出实验3void showprintfH\nn;printfn||\nH;printfn||\nH;printfn|《算法设计与分析》实验|\nn;printfH||\n”;printf*I|\nn;程printf.......L算法分析基础Fibonacci序歹U问....|\nH;printfH||\nn;序printf•……2・分治法在数值问题中的应用一一最近点对问…」\n”;printfH I|\nn;代pnntf……
3.减治法在组合问题中的应用8枚硬币问….M”;printfn||\nH;码printf……4・变治法在排序问题中的应用——堆排序问..…|\n”;printf*||\nn;printfH||\nn;printfn|
99.退出本实验|\nn;printfn||\nn;printfn\nn;printfn*请输入您所要执行的操作1,2,3,4,5,99:\nn;printfH\nn;}c*C:\Docuent sand$£七七111内\4(1M1111£t1廷士01\桌面\口£1)11名\,.8*/:《算法设计与分析》实验实算法分析基础-----------序列问题•
1.Fibonacci验分治法在数值问题中的应用一一最近点对问题:
2.结减治法在组合问题中的应用一一枚硬币问题
3.8果变治法在排序问题中的应用一一堆排序问题:
4..退出本实验及|:99*请输入您所要执行的操作分(1,2,3,4,5,99),输入你的选择:■析狗拼音半:______________________________________________________I算法分析基础------Fibonacci序列问实验名称实验室题实验题目实给定一个非负整数计算第个数n,n Fibonacci验目实验目的)理解递归算法和迭代算法的设计思想以及递归程序的调式技术1的)掌握并应用递归算法和迭代算法效率的理论分析(前验分析)和实际分析(后验分析)2或方法;要)理解这样一个观点不同的算法可以解决相同的问题,这些算法的解题思路不同,复3杂程度不同,效率也不同;求实验要求)使用教材节中介绍的迭代算法()找出最大的使得第个数不
12.5Fib n,n,n Fibonacci超过计算机所能表示的最大整数,并给出具体的执行时间;)对于要求)使用教材节中介绍的递归算法()进行计算,同样给出具体的执行21,
2.5F n时间,并同)的执行时间进行比较;1)对于输入同样的非负整数比较上述两种算法基本操作的执行次数;3n,)对)中的迭代算法进行改进,使得改进后的迭代算法其空间复杂度为()411;)设计可供用户选择算法的交互式菜单(放在相应的主菜单下)5实验()F n〃根据定义,递归计算第个斐波那契数n原〃输入一个非负数n理〃输出第几个斐波那契数(if nWl算return n法elsereturn Fn-l+Fn-2基思想)int Fiblint n{int s
[48],i;s
[0]=0;;s[l]=lfor i=2;i=n;i++s[i]=s[i-l]+s[i-2],timel++;程return s[n];}序int Fib2intn{代long intf;ifnl码f=Fib2n-l+Fib2n-2,time2++;return f;ifn2{time3++;return n;}time3=time3+time2;E MC:\Docuent sand58t七1118£\4(111115七工@±or\桌面\Debug\,.ex-实;《算法设计与分析》实验验算法分析基础----------------------------------------序列问题!
1.Fibonacci结分治法在数值问题中的应用一一最近点对问题!2,果减治法在组合问题中的应用一一枚硬币问题:
3.8及变治法在排序问题中的应用一一堆排序问题!
4.分;.退出本实验99析*请输入您所要执行的操作Q,2,3,4,5,99)请输入你的选择:■搜狗拼音半c\C:\DocuMents and$8七“1185\4111115七「8t0/\桌面\口81118\啊.62©・f3=2f4=3f5=5f6=8f=13f8=21f9=34f10=55F11=89f12=144f13=233f14=377f15=610F16=987f17=1597f18=2584f19=4181f20=6765f21=10946f22=17711f23=28657迭代方法所用的比较次数为.递归方法所用的比较次数为操作完电是否延190121392续〈Y/N.分治法在数值问题中的应用——最近点实验名称实验室对问题实验题目设()()()是平面上个点构成的集合设计pl-xl,yl,p2-xl,y2,,pn-xn,yn nS,算法找出集合中距离最近的点对S实实验目的验1)提高应用蛮力法设计算法的技能;)深刻理解并掌握分治法的设计思想;2目)理解这样一个观点用蛮力法设计的算法,一般来说,经过适度的努力后,都可以对3的其进行改进,以提高算法的效率或实验要求)设计并实现用方法求解最近点对问题的算法;1BF要)设计并实现用方法求解最近点对问题的算法;2DAC)以上两种算法的输入既可以手动输入,也可以自动生成;3求)算法不仅要输出最近点对的距离,还要输出最近点对的两个点;4)对上述两个算法进行时间复杂性分析,并设计实验程序验证分析结果;5)设计可供用户选择算法的交互式菜单(放在相应的主菜单下)6实验原理(算法基本思想)void dian{time_t c_startl,c_endl;c_startl=clock;ints[l00],f[lOO],i,j,t,a,b,c,d,n;蛮力法求最近点问题printfprintfn\n请输入坐标数:;scanfn%dM,n;fort=0;tn;t++scanfH%dn,s[t];scanfn%dn,f[t];double l,k;k=sqrts[l]-s[O]*s[l]-s[O]+f[l]-f[O]*f[l]-f[O];a=s[l];b=f
[1];c=s
[0];d=f[O];fori=0;in;i++forj=i+1;j=n;j++用]{l=sqrts[j]-s[i]*s[j]-s[i]+f[j]-ifkl程序k=l;a=s[j];b=f[j];c=s[i];d=f[i];代码c_endl=clock;printfn\n最近的距离为:%f\n\k;printfn\n他们的坐标分别为:%d,%d,%d,%d\n;a,b,c,d;printfn\n此方法所花时间为^f:difftimeS—endljstartD/lgZ;typedef structdoublex;double y;}pttype;long arr[maxsize];long arrl;pttype pt[maxsize];int sortcmpconst void*a,const void*bif pttype*a-xpttype*b-xelsereturn1;int arrcmpconstvoid*a,constvoid*b ifpttype*a-ypttype*b-yreturn-1;elsereturn1;double dispttypea,pttype breturnsqrta.x-b.x*a.x-b.x+a.y-b.y*a.y-b.y;double getMindoublea,double bifabreturna;elsereturn b;double shortestlongleft,long right〃两个点ifright-left==1return dispt[left],pt[right];〃三个点ifright-left==2return getMingetMindispt[left],pt[left+l],dispt[left],dispt[left+l],pt[right],pt[right];/*枚举个点和个点的情况,当边界使用*/〃大于用分治法二long ij,mid left+right/2;double curmin=getMinshortestleft,mid,shortestmid+1,right;arrl=0;for i=mid;i=leftpt[mid+l].x-pt[i].x=curmin;i—〃确定左边内的点arr[arrl4-+]=i;-dfor i=mid+1;i=rightpt[i].x-pt|mid|.x v=curmin;i++arr[arrl++]〃确定右边内的点=i;+d〃按排序qsortarr,arrl,sizeofarr
[0],arrcmp;yfor i=0;iarrl;i++for j=i+1;jarrlpt[arr[j]].y-pt[arr[i]].y=curmin;j++curmin二getMincurmin,dispt[arr[i]],pt|arr[j]];return curmin;}。