算法设计与分析实验报告

声明：此文档只作为学习参考，不得用作它途！ 《算法设计与分析》实验教学大纲

实验学时：32 实验个数：7 实验学分：1 课程性质： 适用专业：计算机科学与技术、软件工程 教材及参考书：

1. 《计算机算法设计与分析》，王晓东，北京：电子工业出版社，2012 2. 《算法与数据结构》，傅清祥等著，北京：电子工业出版社，2003

3. 《计算机算法导引—设计与分析》，卢开澄著，北京：清华大学出版社，2001 大纲执笔人：刘芳 大纲审定人： 郭涛 一、 实验课的性质与任务

算法的设计与分析是计算机科学的核心问题之一，也是计算机科学与技术专业本科 及研究生的一门重要的专业基础课，其内容是研究计算机领域及其有关领域中的一些非 数值计算的常用算法。课程将覆盖计算机软件实现中常用的、有代表性的算法，并具有 一定的深度和广度，通过实验，使学生理解并掌握算法设计的基本技术，让学生具有针 对所给的问题设计和实现高效算法的基本能力。 二、实验课程目的与要求 计算机科学的一个核心问题是算法理论，本课程介绍非数值算法设计的策略与技 术，同时介绍算法的复杂性的概念通过对一些代表性算法的使用达到了解掌握与运用的 目的。 通过完成课程实验，使学生达到如下要求：

1. 熟悉各种基本常用算法的基本思想、适用范围，初步掌握算法分析的基本技巧

以及如何根据实际问题设计一个有效的算法。 2. 能对给定问题分析出恰当的数学模型，并设计出解决方案，将算法用高级语言 （C，VC++等）编程实现。 三、实验项目及内容提要

算法设计与分析实验课程 序 实 实验名称 学 必 选 学 实验类型 内容提要 号 验 项 目 编 号

时 做 做 分 数 基 本 操 作 验 证 综 合 设 计 1 1

算法设计 基础 4 √ √

通过本次实验，程序 设计语言基础知识， 熟悉文件操作等 2 2

递归与分 治策略及 其应用 6 √ √ √

掌握递归算法的设 计思想，提高应用分 治法设计算法的技 能 3 3

动态规划 及其应用 6 √ √ √

掌握设计动态规划 算法的步骤，并编程 实现有关算法。 4 4

贪心算法 及其应用

6 √ √ √

通过本次实验，掌握 设计贪心算法的步 骤，并编程实现有关 问题的求解 54 5

回溯法及 其应用 6 √ √ √

通过本实验，理解回 溯法的深度搜索策 略，掌握用回溯法解 题的算法框架。 6 6

分支限界 法及其应 用 4 √ √ √

通过本实验，理解分 支限界法的剪枝搜 索策略，掌握用分支 限界法算法框架 7 7

线性规划 问题的求 解 4 √ √

理解线性规划的算 法模型，了解求解线 性规划的单纯形算 法，学会使用 Excel 求解线性规划问题。 三、实验内容安排： 实验一 算法设计基础 （验证型实验 4 学时） 1.实验目的

（1） 巩固程序设计语言基础知识，熟悉文件操作等。

（2） 对给定问题，能设计算法并编程实现问题的求解，并分析算法的时间复杂性。 2.实验要求

（1） 认真填写实验报告，附加源代码（主要代码）和运行记录；

（2） 对设计好的算法，测试运行实验数据，检查输出是否正确。并对算法的时间 和空间复杂度进行分析。 3.实验内容：

（1） 统计数字问题（P8） #include \ #include #include ifstream fin(\ ofstream fout(\ using namespace std; int i,n,m;

int page;//page 是书的总页数 int number[10]={0}; void main() {

fin>>page;

for (int j=1;j<=page;j++) { n=j; while(n) {

m=n; ++number[m]; n=n/10; } }

for ( i=0;i<=9;i++) {

fout<

fin.close();

fout.close(); return; }

（2） 字典序问题（P8） （3） 最多约数问题（P9） #include \ #include #include ifstream fin(\ ofstream fout(\ using namespace std; void main() {

int a,b,i,j,max; fin>>a>>b;

int number[100]={0};//约数个数 for ( i=a;i<=b;i++) {

for (j=1;j<=i;j++) {

if( i%j==0) number[i]++;//若能被整除则约数个数加 1 } }

for( i=a;i

if(number[i]>number[i+1]) max=number[i];

else max=number[i+1]; }

fout<

}

（4） 最大间隙问题（P10）

（5） 设计算法求解 fibonacci 数列的第 110 项的值。 （6） 设计算法求解尽可能多的完美数（完全数） 。 注：至少选择其中 2 题完成 实验二 递归与分治策略及其应用 （验证型、设计型实验 6 学时） 1.实验目的

（1） 进一步掌握递归算法的设计思想以及递归程序的调试技术。 （2） 提高应用分治法设计算法的技能

（3） 理解这样一个观点：分治和递归经常同时应用在算法设计中。 2.实验要求

（1） 认真填写实验报告，附加源代码（主要代码）和运行记录； （2） 对设计好的算法，要分析算法的时间和空间复杂度。 3.实验内容：

（1） 设计算法求解整数的划分问题，对给定的整数，输出划分数。 （P14）并思考 如何实现输出每个具体的划分。 #include \ #include using namespace std; int q(int m,int n) {

if ((n<1)||(m<1)) return 0; if ((n==1)||(m==1))return 1; if (m

if (m==n) return q(m,n-1)+1; return q(m,n-1)+q(m-n,n); }

void main() {

int n,m;

cout<<\分别输入 m 和 n 的值(m 为被划分数，n 为最大加数)\ cin>>m>>n;

cout<<\划分数为：\ cout<

（2） 设计算法求解 n 个互异元素的全排列的算法并编程实现（P13），并在此基础 上修改程序，使其能解决有重复元素的排列问题（P41算法实现题 2-5）。 #include \ #include #include ifstream fin(\ ofstream fout(\

using namespace std; int count=0;

int check(char list[],int k ,int m ) //判断是否互异，重复返回 0 {

if( m > k)

for(int i = k ; i< m ; i++) if( list[i] == list[m] ) return 0 ; return 1 ; }

inline void swap(char &a,char &b) {

char temp;

temp=a;a=b;b=temp; }

void perm(char list[],int k,int m) {//依次交换第一个元素进行排序 if(k==m) //只剩下一个元素 {

count++;

for(int i=0;i<=m;i++) fout<

else //还有多个元素，递归产生排列 for(int i=k;i<=m;i++) {

if(check(list,k,i)) {

swap(list[k],list[i]); perm(list,k+1,m); swap(list[k],list[i]); } }

return; }

void main() {

char number[100];

int i=0,n=0; //n 是总个数

fin>>number; //number 数组为待排元素 while(number[i] != '\\0') {

for(int i=1;i<=n;i++) E.x[i] = i+1; E.s = 0; E.cc = 0;

E.rcost = MinSum; Type bestc = NoEdge; //搜索排列空间树

while(E.s

if(E.s == n-2){//当前扩展结点是叶结点的父结点 //再加 2 条边构成回路

//所构成回路是否优于当前最优解 if(a[E.x[n-2]][E.x[n-1]] != NoEdge && a[E.x[n-1]][1] != NoEdge && (E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1]

bestc = E.cc + a[E.x[n-2]][E.x[n-1]]+ a[E.x[n-1]][1]; E.cc = bestc; E.lcost = bestc; E.s ++; H.Insert(E); }

else delete[]E.x; }//舍弃扩展结点 else{

for(int i= E.s+1;i

if(a[E.x[E.s]][E.x[i]] != NoEdge) {//可行儿子结点

Type cc = E.cc + a[E.x[E.s]][E.x[i]];

Type rcost = E.rcost - MinOut[E.x[E.s]]; Type b = cc+ rcost;//下界

if(b

MinHeapNodeN; N.x = new int[n]; for(int j = 0; j

N.rcost = rcost; H.Insert(N); }

delete[]E.x;}//完成结点扩展

try{H.DeleteMin(E)}//取下一扩展结点 catch(OutOfBounds) {break;}//堆已空 }

if(bestc == NoEdge)

return NoEdge;//无回路 //将最优解复制到 v[1:n] for(int i=0;i

{//释放最小堆中所有结点 delete[]E.x;

try{H.DeleteMin(E)}//取下一扩展结点 catch(OutOfBounds) {break;}//堆已空 }

return bestc; }

(3) 设计算法求解 n 皇后问题，并编程实现。 （P196，算法实现题 6-6） (4) 设计算法求解无优先级运算问题，并编程实现。（P197，算法实现题 6-9） (5) 设计算法求解 8 数码难题，并编程实现。

(6) 设计算法求解 15 迷问题，并编程实现。 注：至少选择其中 1 题完成。 3.主要仪器设备及软件 （1） PC 机

（2） TC、VC++、Java 等任一编程语言 实验七 线性规划问题的求解 （ 验证型实验 4 学时） 1.目的要求

（1） 理解线性规划的算法模型，了解求解线性规划的单纯形算法； （2） 学会使用 Excel 求解线性规划问题。 2.实验内容（对如下案例选择一种方式实现）

（1） 编程实现求解线性规划问题的单纯形算法； （2） 应用 Excel 规划求解工具求解线性规划问题。 3.实验题目：

案例 1：家具生产问题

王老板经营着一家具厂，生产两种家具：桌子和椅子。生产经营数据如下表，试确 定王老板的最优生产计划。

资源 家具 桌子 椅子 资源量 木工 4 3 120

油漆工 2 1 50 利润 50 30

桌子 椅子 资源量 资源使用 量

木工 4 3 120 120 油漆工 2 1 50 50 利润 50 30 1350 生产件数 15 20 案例 2：展厅保安监控问题——海湾艺术馆考虑安装一系列摄像安全系统以减少其保安 费用。下图是海湾艺术馆用于展览的 8 间展厅的示意图。各展厅之间的通道显示为 (1)~(13)。一家保安公司建议在一些通道安装双向摄像机。每架摄象机都可以很好地监 控通道两侧的展厅。例如：在通道⑷处安装摄象机，则展厅 1 和 4 就可以完全被监控 到，等等。管理层用最少数量的双向摄像机覆盖所有的 8 间展厅。 解答：建立数学模型 设 x1,x2……x13 为变量 min Z = x1+x2+x3+……+x13 x1+x4+x6 >=1 x6+x8+x12>=1 x1+x2+x3>=1 x3+x4+x5+x7>=1 x7+x8+x9+x10>=1 x10+x12+x13>=1 x2+x5+x9+x11>=1 x11+x13>=1 xi=0,1(i=1…13) 展厅1 展厅2

展厅3 展厅4 展厅5 展厅6 展厅7 展厅8 （1） （3） （4） （5） （6） （7） （8） （9） （10） （11） （13） （12） （2）

案例 3：某医院护士值班班次、每班工作时间及各班所需护士数量如下表。每班护士值 班开始时向病房报到，试决定：若护士上班后连续工作 8 小时，该医院最少需要多少名

护士，以满足轮班的需要？ 班次 工作时间 所需护士数 1 6：00——10：00 60 2 10：00——14：00 70 3 14：00——18：00 60 4 18：00——22：00 50 5 22：00——2：00 20 6 2：00——6：00 30

至少选择一个案例实现模型建立和求解。 解答：建立数学模型 设 x1,x2……x6 为变量 min Z = x1+x2 +……+x6 x1+x6>=60 x1+x2>=70 x2+x3>=60 x3+x4>=50 x4+x5>=20 x5+x6>=30

3.主要仪器设备及软件 （1） PC 机

（2） TC、VC++、Java 等任一编程语言 （3） Microsoft Excel 规划求解工具

本文来源：https://www.bwwdw.com/article/u3sx.html