《算法设计与分析》

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

实验一 二分查找程序实现…………………………………………………………………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次；

5、改变问题规模n重复上述步骤2~4，n取100、200……1000； 6、依实验数据作图，并与理论图作比较； 7、二分搜索算法平均查找次数： 问题规模为n时，平均查找次数为：

a(n)=int(logn) + 1/2 // int() 函数为向下取整 即二分搜索算法对于含有n个数据的有序表l平均作了约int(logn)+1/2次的查找操作。 实验步骤： 1.初始化生成递增随机数列： for ( int j=100; j <=1000; j+=100 )

{ array[0]=10+rand(); for(int i=1; i<j; 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<b[n/2]，则只要在数组b的左半部继续搜索searchkey；如果searchkey>b[n/2]，则只要在数组b的右半部继续搜索searchkey。

3.实现主函数并完成所有代码。 4.算法复杂性分析： 容易看出，没执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了o（logn）次。循环体内运算需要o（1）时间，因此整个算法在最坏情况下的计算时间复杂性为o（logn）。 六、调试过程及实验结果 输出结果为：篇二：算法实验报告 实 验 报

告 课程： 计算机算法分析与设计 系科： 计算机科学与技术 班级： 姓名： xxxxx 学号：xxxxxxxxxxxxxx 年

度： 2010-2011 学期： 上 计算机与信息科学学院 计算机科学实验教学中心 篇三：算法实验报告 重 庆 交 通 大 学 学 生 实 验 报 告 实验课程名称 算法设计与分析 开课实验室 数学实验室

学院 数学与统计学院 年级13 专业班 信息与计算科学2 学 生 姓 名 辜朕圆 学 号 631322020223 开 课 时 间 2015 至 2016 学年 第

1 学期 2015-2016学年 第一学期 实验报告题目 实验一 递归与分治策略 开课实验室：数学实验室 指导老师：韩逢庆 时间：2015.9 学院：

理学院 专业：信息与计算科学 班级：2013级2班 姓名： 辜朕圆 学号：631322020223 一、 实验目的

1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；

2．提高学生利用课堂所学知识解决实际问题的能力； 3．提高学生综合应用所学知识

解决实际问题的能力。 二、 实验内容 题目 ①设a[0:n-1]是已排好序的数组。请写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，

i和j相同，均为x在数组中的位置。 ②写出三分搜索法的程序。 三、 实验要求 （1）用分治法求解…问题； （2 ）再选择自己熟悉的其它方法求解本问题； （3）上机实现所设计的所有算法；

四、 实验过程设计（算法设计过程） 1、已知a[0:n-1]是一个已排好序的数组，可以采用折半查找（二分查找）算法。如果

搜索元素在数组中，则直接返回下表即可；否则比较 2015-2016学年 第一学期 搜索元素x与通过二分查找所得最终元素的大小，注意边界条件，从而计算出小于x的最大元素的位置i和大于x的最小元素位置j。 2、先判定输入的数x是否在数组的范围内，再将n个元素分成大致相同的三部分，取在数组a的左三分之一部分中继续搜索x。如果x>a[san2]，则只需在数组a的右三分之一部分中继续搜索x。上述两种情况不成立时，

则在数组中间的三分之一部分中继续搜索x。 五、 实验结果分析 (1)例子为数组a[1,2,3,4,5,6,7,8,9],n=9,x=9。 实验结果为

(2)例子为数组a[1,2,3,4,5],x=3,n=5。 实验结果为

时间复杂性：最好情况下，最坏情况下 二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为o(log n)。（n代表集合中元素的个数） 三分搜索法：o（3log3n） 空间复杂性分析：o（1）。 六、 实验体会

本次试验解决了二分查找和三分查找的问题，加深了对分治法的 2015-2016学年 第一学期 理解，收获很大，同时我也理解到学习算法是一个渐进的过程，算法可能一开始不是很好理解，但是只要多看几遍，再实践操作，毕竟实践是检验真理的唯一标准，只要动手就能感受自己写出算法的喜悦，从而良性循环越学越好。 七、 附录：（源代码） (1) public static int binarysearch(int a[],int x,int n) {

int left=0;int right=n-1;int i,j; while(left<=right) { int middle=(left+right)/2; if(x==a[middle]){i=j=middle;system.out.println(get it);return

if(x>a[middle])left=middle+1; else right=middle-1; } i=right;j=left; return 0; } 1;} (2)

public class sanfen {

public static int sansearch(int []a,int x,int n){ int left=0;int right=n-1; while(right>left){ if(x<a[left]||x>a[right]) { system.out.println(根本不在数组里); break; }

int san1=(left+right)/3; int san2=2*(left+right)/3; if(x==a[san1]) {

system.out.println(找到了); return san1; } else if(x<a[san1])right=san1-1; else if(x>a[san2])left=san1+1; 2015-2016学年 第一学期 else{left=san1;right=fan2;} } } }

public static void main(string []args) { } sanfen s=new sanfen(); int []b={1,2,3,4,5}; s.sansearch(b,3,5); return -1; 实验二 动态规划 一、实验目的 1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握； 2．提高学生利用课堂所学知识解决实际问题的能力； 3．提高学生综合应用所学知识解

决实际问题的能力。 二、实验内容 (1)设计一个o（n）时间的算法，找出由n个数组成的序列的最长单调递增子序列 (2)考虑下面的整数线性规划问题：maxi?1 2 ?cj n ii ,i?1 ?ax n ii

?b xi为非负整数，1<=i<=n 试设计一个解此问题的动态规划算法，并分 析算法的计算复杂性。 三、实验要求 （1）用动态规划思想求解最优问题； （2）再选择自己熟悉的程序设计语言实现所有算法； （3）分析所设计的算法的时间/空间复杂性。

2015-2016学年 第一学期篇四：算法实验报告 《算法分析与设计》上机实验报告 姓名：郑翔 学号：

班级：软件三班 120105031108 一、 上机实验题目

上机实验一 递归算法的设计与实现 1. 计算整数的非负整数次幂 2. 基于递归算法的插入排序 上机实验二 递归算法的实现 1. 自然归并算法的设计与实现 2. 快速排序算法的设计与实现 上机实验三 贪心算法的实现 1. 背包问题的设计与实现

2. 单源点最短路径问题的设计与实现 二、 算法设计思路

上机实验一 递归算法的设计与实现 1.计算整数的非负整数次幂 2.基于递归算法的插入排序 三、 源程序代码

上机实验一 递归算法的设计与实现 1.计算整数的非负整数次幂 #include <iostream> using namespace std; int power(int x,int n) {

int y; if(n==0) y=1; else{

y=power(x,n/2); y=y*y; if(n%2==1) y=y*x; }

return y; }

int main() {

int x,n; int sum=0;

cout<<请输入整数x,非负整数n：<<endl; cin>>x>>n; sum=power(x,n);

cout<<x的n次幂为：<<sum<<endl; return 0; } 时间复杂度○（logn）

2. 基于递归算法的插入排序 #include <iostream> #include <string> #include <fstream> using namespace std;

void insertionsort(int *a,int item,int size) { if(size==0) a[0]=item; else {

for(int i=size-1;i>=0;i--) { if(item<a[i]) a[i+1]=a[i]; else