算法实验报告

《算法设计与分析》

实验报告 班级 姓名 学号 年 月 日 目录

实验一 二分查找程序实现 03

页

实验二 棋盘覆盖问题（分治法）. 08

页

实验三 0-1背包问题的动态规划算法设

计 .11页 实验四 背包问题的贪心算法 14

页

实验五 最小重量机器设计问题（回溯法） 17

页

实验六 最小重量机器设计问题（分支限界法） 20

页 指导教师对实验报告的评语 成绩： 指导教师签字：

年 月 日 实验一：二分查找程序实现

一、实验时间：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，算法终止。如果x<a[n/2]，

则我们只要在数组a的左半部继续搜索（x这里假设数组元素呈升序排列）。如果x>a[n/2]，

则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于

理解。 确定算法复杂度基本步骤： 1、首先设定问题规模n； 2、随即产生递增数列；

3、在n个有序数中随机取一个作为待查找量，搜索之；

4、记录查找过程中的比较次数，再次生成新的有序表并查找，记录查找次数，每个数组

重复10次；