篇一：实验报告算法思想
《算法设计与分析》
实验报告 班级姓名 学号年月 日 目录
实验一 二分查找程序实现…………………………………………………………………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()%15;for(int i=1; i<j; i++) {array[i]=array[i-1]+1+rand()%3+rand()%10;} }
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?12
?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
篇二：算法实验报告
重 庆 交 通 大 学 学 生 实 验 报 告
实验课程名称 算法设计与分析开课实验室 数学实验室
学院 数学与统计学院 年级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学年 第一学期
篇三：算法实验报告
华北电力大学
|
|
|
|
实 验 报 告实验名称课程名称
实验一 矩阵连乘 11
一、实验目的
熟悉动态规划算法设计思想和设计步骤，掌握基本的程序设计方法，培养学生用计算机解决实际问题的能力。
二、实验要求：
1、用动态规划算法解矩阵连乘问题
（1）问题的描述
给定n个矩阵{A1,A2,…,An}，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。要算出这n个矩阵的连乘积A1A2…An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。 例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：（A1（A2（A3A4））），（A1（（A2A3）A4）），（（A1A2）（A3A4）），（（A1（A2A3））A4），（（（A1A2）A3）A4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A是一个p×q矩阵，B是一个q×r矩阵，则计算其乘积C=AB的标准算法中，需要进行pqr次数乘。 为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A1,A2,A3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A1A2）A3），（A1（A2A3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵{A1,A2,…,An}（其中矩阵Ai的维数为pi-1×pi，i＝1,2,…,n），如何确定计算矩阵连乘积A1A2…An的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。 穷举搜索法的计算量太大，它不是一个有效的算法，本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。
（2）算法设计思想
动态规划算法的基本思想是将待求解问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，动态规划法经分解得到的
表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵…、直到n个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n个矩阵相乘的最小运算量；另
一张表存储最优断开位置。 2、输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback()完成。分三种情况： （1）只有一个矩阵，则只需打印出A1； （2）有两个矩阵，则需打印出（A1A2）； （3）对于矩阵数目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。
三、实验仪器及设备
visual studio2010。
四、程序设计
#include"stdafx.h"
#include<iostream>
using namespace std;
const int MAX = 100;
//p用来记录矩阵的行列，main函数中有说明
//m[i][j]用来记录第i个矩阵至第j个矩阵的最优解
//s[][]用来记录从哪里断开的才可得到该最优解
int p[MAX+1],m[MAX][MAX],s[MAX][MAX];
int n;//矩阵个数
int matrixChain()
{
for(int i=0;i<=n;i++)
m[i][i]=0;
for(int r=2;r<=n;r++)//对角线循环
for(int i=0;i<=n-r;i++)//行循环
{
int j = r+i-1;//列的控制
//找m[i][j]的最小值，先初始化一下，令k=i
m[i][j]=m[i+1][j]+p[i+1]*p[i]*p[j +1];
s[i][j]=i;
//k从i+1到j-1循环找m[i][j]的最小值
for(int k = i+1;k<j;k++)
{
int temp=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];
if(temp<m[i][j])
{
m[i][j]=temp;
//s[][]用来记录在子序列i-j段中，在k位置处
//断开能得到最优解
s[i][j]=k;
}
}
}
return m[0][n-1];
}
//根据s[][]记录的各个子段的最优解，将其输出
void traceback(int i,int j)
{
if(i==j)
{
cout<<'A'<<i;
return ;
}
if(i<s[i][j])
cout<<'(';
traceback(i,s[i][j]);
if(i<s[i][j])
cout<<')';
if(s[i][j]+1<j)
cout<<'(';
traceback(s[i][j]+1,j);
if(s[i][j]+1<j)
cout<<')';
}
void traceback(){
cout<<'(';
traceback(0,n-1);
cout<<')';
cout<<endl;
}
int main()
{
cout<<"请输入矩阵的个数："<<endl;
cin>>n;
cout<<"输入矩阵（形如a*b,中间用空格隔开）:"<<endl;
for(int i=0;i<=n;i++)
cin>>p[i];
//测试数据可以设为六个矩阵分别为
//A1[30*35],A2[35*15],A3[15*5],A4[5*10],A5[10*20],A6[20*25]
//则p[0-6]={30,35,15,5,10,20,25}
cout<<"输出结果如下："<<endl;
matrixChain();
traceback(0,n-1);
//最终解值为m[0][n-1];
cout<<endl;
return 0;
}
（4）数据输入和结果输出
六、实验总结：
本次实验基本达到了实验目的，用动态规划的思想解决了矩阵连乘的问题。在这次实验过程中，刚开时编程的时候疑惑了很长的时间，编程需要注意算法代码与实际语言的结合。在进行代码验证时不仅需要验证给定数据还要自编数据验证。