《算法设计与分析》
实验报告
班级 姓名 学号
年 月 日
目录
实验一 二分查找程序实现…………………………………………………………………03页
实验二 棋盘覆盖问题（分治法）.…………………………………………………………08页
实验三 0-1背包问题的动态规划算法设计……………………………………………….11页
实验四 背包问题的贪心算法………………………………………………………………14页
实验五 最小重量机器设计问题（回溯法）………………………………………………17页
实验六 最小重量机器设计问题（分支限界法）…………………………………………20页
1
指导教师对实验报告的评语
成绩：
指导教师签字：
年 月 日
2
实验一：二分查找程序实现
一、实验时间：2013年10月8日，星期二，第一、二节地点：J13#328
二、实验目的及要求 目的：
建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。 要求：
1、用c/c++语言实现二分搜索算法。
2、通过随机产生有序表的方法，测出在平均意义下算法比较次数随问题规模的变化曲线，并作图。
三、实验环境
平台：Win7 32位操作系统 开发工具：Codeblocks10.05
四、实验内容
对已经排好序的n个元素a[0：n-1]，现在要在这n个元素中找出一特定元素x。
五、算法描述及实验步骤
算法描述：
折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果xa[n/2]，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解。 确定算法复杂度基本步骤： 1、首先设定问题规模n； 2、随即产生递增数列；
3、在n个有序数中随机取一个作为待查找量，搜索之；
4、记录查找过程中的比较次数，再次生成新的有序表并查找，记录查找次数，每个数组重复10次；
5、改变问题规模n重复上述步骤2~4，n取100、200……1000； 6、依实验数据作图，并与理论图作比较； 7、二分搜索算法平均查找次数： 问题规模为n时，平均查找次数为： A(n)=Int(logn) + 1/2 // Int() 函数为向下取整
3
即二分搜索算法对于含有n个数据的有序表L平均作了约Int(logn)+1/2次的查找操作。
实验步骤：
1.初始化生成递增随机数列： for ( int j=100; j <=1000; j+=100 ) { array[0]=10+rand(); for(int i=1; i array[i]=array[i-1]+1+rand()%3+rand(); } } 2. 定义二分查找算法： int BinarySearch( const int b[], int searchKey, int low, int high ); 其中，返回值为int类型，数组b[]为待查递增序列，searchKey为所查数据，low为数组b[]左下标，hight为数组b[]右下标。 该算法实现过程为： 将数组b[]的n个元素分成个数大致相同的两半，取b[n/2]与searchKey作比较。如果searchKey=b[n/2]，则找到searchKey，算法终止；如果searchKey 3.实现主函数并完成所有代码。 4.算法复杂性分析： 容易看出，没执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O（logn）次。循环体内运算需要O（1）时间，因此整个算法在最坏情况下的计算时间复杂性为O（logn）。 六、调试过程及实验结果 输出结果为： 4