算法设计与分析实验指导书(080200050).pdf

算法设计与分析

实验指导书

东北大学软件学院

2014年

目录

算法设计与分析1

实验指导书1

前言

实验要求.

实验1分治法的应用（2学时）.

1.实验目的

2.实验类型

3.预习要求

4.实验基本要求

5.实验基本步骤

实验2动态规划（2学时）

1.实验目的

2.实验类型

3.预习要求

4.实验基本要求

5.实验基本步骤

实验3回溯法（4学时）

1.实验目的

2.实验类型

3.预习要求

4.实验基本要求

5.实验基本步骤

东北大学软件学院信息安全专业－算法设计与分析实验

前言

《算法设计与分析》

是一门面向设计，处于计算机科学与技术学科核心地位的教育课程。通过对计算

机算法系统的学习，使学生理解和掌握计算机算法的通用设计方法，培养对算法的计算复杂性正确分析的

能力，为独立设计算法和对算法进行复杂性分析奠定基础。

要求掌握算法复杂度分析、分治法、动态规划法、贪心法、回溯法、分支限界法等算法的设计方法及

其分析方法。能将这些方法灵活的应用到相应的问题中，并且能够用C++实现所涉及的算法，并尽量做到

低复杂度，高效率。

通过本课程的实验，使学生加深对课程内容的理解，培养学生严密的思维能力，运用所学知识结合具

体问题设计适用的算法的能力；培养学生良好的设计风格，激励学生创造新算法和改进旧算法的愿望和热

情。希望同学们能够充分利用实验条件，认真完成实验，从实验中得到应有的锻炼和培养。

希望同学们在使用本实验指导书及进行实验的过程中，能够帮助我们不断地发现问题，并提出建

议，使《算法设计与分析》课程成为对大家有益的课程。

第3页共13页

东北大学软件学院信息安全专业－算法设计与分析实验

实验要求

《算法设计与分析》课程实验的目的是为了使学生在课堂学习的同时，通过一系列的实验，使学生

加深理解和更好地掌握《算法设计与分析》课程教学大纲要求的内容。

在《算法设计与分析》的课程实验过程中，要求学生做到：

（1）仔细观察调试程序过程中出现的各种问题，记录主要问题，做出必要说明和分析。

（2）认真书写实验报告。实验报告模板见附录1。

（3）遵守机房纪律，服从辅导教师指挥，爱护实验设备。

（4）实验课程不迟到。如有事不能出席，所缺实验一般不补。

（5）本实验采用的开发环境为MicrosoftVisualC++6.0，同学在做实验之前要求熟悉该软件

的使用方法。

（6）实验成绩主要从以下几方面考核：实验过程态度，实验结果及报告书写。

第4页共13页

东北大学软件学院信息安全专业－算法设计与分析实验

实验1分治法的应用（2学时）

1.实验目的

（1）理解分治法的思想。

（2）掌握用分治法解决问题

2.实验类型

设计型

3.预习要求

熟悉VisualC++6.0上机编程调试的基本方法。掌握教材上分治法的思想，掌握各种排序方法及二分

有哪些信誉好的足球投注网站的思想。

4.实验基本要求

（1）仔细阅读备选实验的题目，选择一个（可选多个）作为此次实验题目，设计的程序要满足正确性，

代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用C＋＋的模板，设计的程序通用

性好，适合各种合理输入，并能对不合理输入做出正确的提示。

（2）可供选择的题目有以下3个：

中位数问题

问题描述

设