算法设计与分析实验报告

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

实验学时：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(\