算法设计与分析,王晓东,实验报告

为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划算法设计与分析,王晓东,实验报告习题2-1求下列函数的渐进表达式：3n2+10n;n2/10+2n;21+1/n;logn3;10log3n。解答：3n2+10n=O(n2),n2/10+2n=O(2n),21+1/n=O(1),logn3=O(logn),10log3n=O(n).习题2-3照渐进阶从低到高的顺序排列以下表达式：n!，4n2,logn,3n,20n,2,n2/3。解答：照渐进阶从高到低的顺序为：n!、3n、4n2、20n、n2/3、logn、2习题2-4(1)假设某算法在输入规模为n时的计算时间为T(n)=3*2n。在某台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？(2)若上述算法的计算时间改进为T(n)=n2，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？(3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？解答：(1)设能解输入规模为n1的问题，则t=3*2n=3*2n/64,解得n1=n+6(2)n12=64n2得到n1=8n(3)由于T，并简述理由。解答：f(n)=logn2;g(n)=logn+5.logn2=(2)f(n)=logn2;g(n)=根号n.logn2=O(根号n)(3)f(n)=n;g(n)=(logn)2.n=(2)(4)f(n)=nlogn+n;g(n)=logn.nlogn+n=(5)f(n)=10;g(n)=log10.10=(log10)(6)f(n)=(logn)2;g(n)=logn.(logn)2=(7)f(n)=2n;g(n)=100n2.2n=(8)f(n)=2n;g(n)=3n.2n=O(3n)习题2-7证明：如果一个算法在平均情况下的计算时间复杂性为，则该算法在最坏情况下所需的计算时间为。证明：Tavg(N)=IeDnP(I)T(N,I)IeDnP(I)IeDnmaxT(N,I')=T(N,I*)IeDnP(I)=T(N,I*)=Tmax(N)因此，Tmax(N)=习题2-8求解下列递归方程：So=0;Sn=2Sn-1+2n-1.解答：1应用零化子化为齐次方程，2解此齐次方程的特征方程，3由特征根构造一般解，4再由初始条件确定待定系数，得到解为：Sn=(n-1)2n+1习题2-9求解下列递归方程Ho=2;H1=8;Hn=4Hn-1-4Hn-2.解：Hn=2(n+1)(n+1)第三章递归与分治策略习题3-1下面的7个算法都是解决二分搜索问题的算法。请判断这7个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算法的正确性证明。publicstaticintbinarySearch1(inta,intx,intn)intleft=0;intright=n-1;while(leftamiddle)left=middle;elseright=middle;return-1;publicstaticintbinarySearch2(inta,intx,intn)intleft=0;intright=n-1;while(left=amiddle)left=middle;elseright=middle;if(x=aleft)returnleft;elsereturn-1;publicstaticintbinarySearch4(inta,intx,intn)if(n>0&&x>=a0)intleft=0;intright=n-1;while(left0&&x>=a0)intleft=0;intright=n-1;while(left0&&x>=a0)intleft=0;intright=n-1;while(left0&&x>=a0)intleft=0;intright=n-1;while(leftamiddle)left=middle+1;elseright=middle-1;ind0=right;ind1=left;returnfalse;返回的ind1是小于x的最大元素位置，ind0是大于x的最小元素的位置。习题3-3设a0:n-1是有n个元素的数组，是非负整数。试设计一个算法讲子数组与换位。要求算法在最坏情况下耗时为，且只用到的辅助空间。分析与解答：算法：三次求反法Algorithmexchange(a,k,n);BeginInverse(n,0,k-1);inverse(n,k,n-1)；inverseEnd.Algorithminverse(a,i,j);Beginh=(j-i+1)/2;Fork=0toh-1doBeginx=ai+k;ai+k=aj-k;aj-k=xend;end习题3-4如果在合并排序算法的分割步中，讲数组a0;n-1划分为根号2】个子数组，每个子数组中有个元素。然后递归地对分割后的子数组进行排序，最后将所得到的个排好序的子数组合并成所要求的排好序的数组。设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性。分析与解答：实现上述策略的合并排序算法如下：publicstaticvoidmergesort(inta,intleft,intright)if(left1)for(inti=0;i#includeifstreamfin("");ofstreamfout("");usingnamespacestd;inti,n,m;intpage;/page是书的总页数intnumber10=0;voidmain()fin>>page;for(intj=1;j#includeifstreamfin("");ofstreamfout("");usingnamespacestd;voidmain()inta,b,i,j,max;fin>>a>>b;intnumber100=0;/约数个数for(i=a;inumberi+1)max=numberi;elsemax=numberi+1;foutusingnamespacestd;intq(intm,intn)if(n>m>>n;cout#includeifstreamfin("");ofstreamfout("");usingnamespacestd;intcount=0;intcheck(charlist,intk,intm)/判断是否互异，重复返回0if(m>k)for(inti=k;i>number;/number数组为待排元素while(numberi!='0')算法分析与设计实验指导书一、实验目的算法设计与分析是一门面向设计，处于计算机科学与技术学科核心地位的教育课程。通过对计算机算法系统的学习，使学生理解和掌握计算机算法的通用设计方法，培养对算法的计算复杂性正确分析的能力，为独立设计算法和对算法进行复杂性分析奠定基础。要求掌握算法复杂度分析、分治法、动态规划法、贪心法、回溯法、分支限界法等算法的设计方法及其分析方法。能将这些方法灵活的应用到相应的问题中，并且能够用C+实现所涉及的算法，并尽量做到低复杂度，高效率。通过本课程的实验，使学生加深对课程内容的理解，培养学生严密的思维能力，运用所学知识结合具体问题设计适用的算法的能力；培养学生良好的设计风格，激励学生创造新算法和改进旧算法的愿望和热情。希望同学们能够充分利用实验条件，认真完成实验，从实验中得到应有的锻炼和培养。希望同学们在使用本实验指导书及进行实验的过程中，能够帮助我们不断地发现问题，并提出建议，使算法设计与分析课程成为对大家有益的课程。二、实验要求算法设计与分析课程实验的目的是为了使学生在课堂学习的同时，通过一系列的实验，使学生加深理解和更好地掌握算法设计与分析实验课程教学大纲要求的内容。在算法设计与分析实验课程实验过程中，要求学生做到：仔细观察调试程序过程中出现的各种问题，记录主要问题，做出必要说明和分析。认真书写实验报告。遵守机房纪律，服从辅导教师指挥，爱护实验设备。实验课程不迟到。如有事不能出席，所缺实验一般不补。本实验采用的开发环境为MicrosoftVisualC+，同学在做实验之前要求熟悉该软件的使用方法。实验成绩主要从以下几方面考核：实验过程态度，实验结果及实验报告书写。上机准备和上机调试上机准备包括以下几个方面：(1)注意同一高级语言文本之间的差别。(2)熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。(3)掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。应该能够熟练运用高级语言的程序调试器DBBUG调试程序。(4)上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行，自底向上，即先调试低层函数。在调试过程中可以不断借助DEBUG的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，此时应动手确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。总结和整理实验报告实验结束后，要整理实验结果并认真分析和总结，根据教师要求写出实验报告。实验报告一般包括如下内容：1实验内容2实验目的3程序清单4调试步骤5运行结果：原始数据，相应的运行结果和必要的说明。6分析与思考调试过程及调试中遇到的问题及解决办法;调试程序的心得与体会;其他算法的存在与实践等。若最终未完成调试，要认真找出错误并分析原因等。实验一、利用分治算法，编程实现循环赛日程表安排问题【实验学时】4学时【实验目的】1深刻理解并掌握“分治算法”的设计思想；2提高应用“分治算法”设计技能；3理解这样一个观点：用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计