算法设计与分析的实验报告

《算法设计与分析的实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验一递归与分治策略一、实验目的1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。二、实验内容1、①设a[0:n-1]是已排好序的数组。请写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。②写出三分搜索法的程序。三、实验要求（1）用分治法求解上面两个问题；（2）再选择自己熟悉的其

2、它方法求解本问题；（3）上机实现所设计的所有算法；四、实验过程设计（算法设计过程）1、已知a[0:n-1]是一个已排好序的数组，可以采用折半查找（二分查找）算法。如果搜索元素在数组中，则直接返回下表即可；否则比较搜索元素x与通过二分查找所得最终元素的大小，注意边界条件，从而计算出小于x的最大元素的位置i和大于x的最小元素位置j。2、将n个元素分成大致相同的三部分，取在数组a的左三分之一部分中继续搜索x。如果x>a[2(n-1)/3]，则只需在数组a的右三分之一部分中继续搜索x。上述两种情况不成立时，则

3、在数组中间的三分之一部分中继续搜索x。五、实验结果分析二分搜索法：三分搜索法：时间复杂性：二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为O(logn)。（n代表集合中元素的个数）三分搜索法：O（3log3n）空间复杂度：O（1）。六、实验体会本次试验解决了二分查找和三分查找的问题，加深了对分治法的理解，收获很大，同时我也理解到学习算法是一个渐进的过程，算法可能一开始不是很好理解，但是只要多看几遍，只看是不够的还要动手分析一下，这样才能学好算法。七、附录：（源代码）二分搜索法：#include

4、stream.h>#includeintbinarySearch(inta[],intx,intn){intleft=0;intright=n-1;inti,j;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle]){i=j=middle;return1;}if(x>a[middle])left=middle+1;elseright=middle-1;}i=right;j=left;return0;}intmain()

5、{inta[10]={0,1,2,3,4,5,6,7,8,9};intn=10;intx=9;if(binarySearch(a,x,n))cout<<"找到"<

6、个作业交给机器A处理时所需要的时间是a[i]，若由机器B来处理，则所需要的时间是b[i]。由于各作业的特点和机器的性能关系，很可能对于某些i，有a[i]>=b[i]，而对于某些就j，j!=i,有a[i]

7、(b[1],b[2],b[3],b[4],b[5],b[6])=(3,8,4,11,3,4)。2、长江游艇俱乐部在长江上设置了n个游艇出租站1，2……n。游客可在游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金r（i，j）1<=i

8、、对于给定的2台处理机A和B处理n个作业，找出一个最优调度方案，使2台机器处理完这n个作业的时间最短。2、对于给定的游艇出租站i到游艇出租站j之间的租金为r（i，j），1<=i