算法分析与设计实验大纲

《算法分析设计》课程实验教学大纲

【编    写】 朱少林        【审    核】

【课程类别】 专业选修      【课程学时】 34

【开课学期】               【实验学时】 16 - 34

【授课专业】 电子商务/信息管理/计算机科学与技术 

一、实验教学任务和目的　　

无论是在计算机科学与技术的研究中，还是在计算机应用（包括管理信息系统和电子商务系统开发）中，都涉及大量的程序设计问题，而且随着研究和应用的深入，所遇到的问题越来复杂，对处理问题的效率要求也越来越高，了解和掌握求解问题的方法（算法）、设计出好的算法也就成为解决这些问题的关键，甚至成为其决定因素。

《算法分析与设计》课程的主要内容是讲授在计算机科学研究和应用中经常用到的一些算法，包括分枝法、贪心法、动态规划法、回溯法等，介绍这些算法设计的思路和算法的一般框架，并针对多个具体的应用问题设计出了相应算法。其目的就是让学过该课程的学生掌握算法设计的基本思想和技巧，掌握几个基本和常用的算法。

《算法分析与设计》是一门实践性很强的课程，课程教学过程中，需要与课程实验相结合。算法分析与设计实验的主要任务是针对给定的问题，设计出一个合适的算法或几个可供选择的算法，然后将算法用合适的程序设计语言实现并上机调试，并用合适的数据验证运行。

只有通过实验，通过让学生进行算法设计和编程实践并上机验证，才能让学生理解算法的思想，掌握算法设计的方法和掌握算法的精髓。同时，通过算法实验，让学生掌握调试程序、改进算法的方法，学会通过对比选择最适合问题求解算法的方法；使学生将以前所学如《C语言程序设计》、《数据结构》等课程知识能有机结合并融会贯通；进一步培养学生的分析问题、解决问题的能力，提高学生素质，使其能更好地适应社会，满足社会对人才的需求。

二、实验教学基本要求

1．程序设计语言与实验要求

算法实验需要将算法转换成程序并上机验证，实验的主要工作是验证算法的正确性并测试算法的时空复杂度。学生可以根据自己的喜好或对程序设计语言的掌握程度选择一个程序设计语言，如C/C++、PASSCAL等支持递归程序设计的语言，实验硬件环境要求是支持学生选定程序设计语言的计算机系统，（包含打印机更佳），学生应能熟练掌握计算机系统的使用，并具备熟练编写、输入和调试程序的能力。

2．实验方案设计与选择

如果简单地认为算法实验就是将算法转换成程序并上机通过，那就错了。算法实验与程序设计实验有许多不同，程序设计实验的重点是编写程序，并上机通过，验证程序的正确性，从而掌握程序设计语言和程序设计方法。算法实验虽然也需要将算法转换成程序并上机验证，但其重点是在针对需要解决的问题编写多个不同解方案的算法（或程序），分析、比较并上机验证算法执行结果，从而选择出一个对所求解问题最有效的算法。

为了达到此目的，一般实验之前应进行有针对性的实验方案设计。首先应准备相应数据，这些数据用于调试程序和检验程序的执行效率，它们应有一定的规模（即数量）和代表性，即反映算法所处理数据的一般特征，应包括最好、最坏、一般及各种边界数据。其次应设计多种求解该问题的算法。最后也是最重的一点是要设计能在计算机上实现的比较和评价这些算法优劣的方法。

例如，在实验项目一中，为了统计算法的执行时间，我们应选择在算法开始前和算法结束时读取计算机时钟、计算时间差求得的算法计算时间的实验方案，为了消除计算机时钟误差的影响，应让此算法重复执行多次，但怎么重复？我们可以设计二个实验方案，一种是让求解百钱买百鸡问题的算法作为子程序，写一个主程序重复调用该算法多次；另一种是直接在求解百钱买百鸡问题的算法中加入循环控制语句，让算法主体重复执行多次。显然前者由于子程序调用会增加时间开销，对算法的时间统计产生影响，所以后一个实验方案较好，它是应选择的实验方案。

3．实验步骤设计

算法分析与设计的实验都应遵循一定的规律，要按一定的次序和步骤进行。设计或计划这个步骤是实验前的一个重要环节，也是落实方案的一个重要措施。应根据具体问题有针对性地设计相应的操作步骤，一步一步完成实验。

通常，算法分析与设计的实验分为实验前和实验中及实验后三个阶段。实验前，学生应用根据本次实验的题目和要求，设计出相应算法，并将算法转换成某个语言的程序，同时准备好实验中需要用到的数据。这里需要强调的是，一是不要忽略算法设计，许多同学跳过算法设计这个步骤而直接编写程序，这样就达不到算法设计和分析的目的，同时，编写出的程序的质量较差；二是不要轻视数据准备，一般算法实验中要准备好足够量的数据（或者生成足够量数据的方法），特别是要准备最好情况、最坏情况、一般情况及临界情况的数据，以检验算法在各种数据集上运行的情况，从而了解或比较算法的优劣。

实验中主要有这样几个阶段：输入程序、编译连接运行、输入数据、查看结果。在每个阶段，需要按实验前准备的步骤进行，按程序要求的形式输入数据。但可能在实验过程中发现问题，这就需要及时对实验方案进行修改和调整。如在运行中发现程序出现错误或者运行结果与预期不符，此时就可能需要修改算法，重新设计程序。实验中的这几个阶段可能有多次反复的过程。

实验后还应对实验结果作分析和总结，必要时要对多个结果列表或作图比较分析。

4．实验中的问题分析与处理

在实验过程中，不可避免地会出现许多问题，出现这些问题的原因可能是多方面的，有计算机系统的问题、有程序设计语言自身的问题，有程序语法的问题，有程序逻辑的问题，也可能有算法的问题。实验过程中，应对所出现的问题加以仔细分析，找出问题的原因并加以修正和改进，从而完善算法或程序。进一步地，通过对问题的分析和处理，增强对算法的理解和设计算法的能力，提高分析问题、解决问题的能力。

5．实验报告要求

实验结束后学生还应将实验过程、实验后的分析结果及对实验体会写成实验报告。实验报告应包括实验目的、实验内容、实验步骤、实验结果及其分析等内容。报告中应详细记录实验过程、实验步骤及每步所做的工作，特别是实验出现的异常情况如算法（程序）错误、输出结果与预期不符、程序（算法）修改的位置和过程等。实验结果及其分析应报告程序运行的结果，以及根据结果对算法所作的分析结论。还应该有学生在此次实验中的收获和体会。

三、实验教学内容　　

实验项目一：算法效率与时空复杂度检验

1．预习要求：

预习教材“第一章 导引与基本数据结构”及《程序设计》、《数据结构》内容，掌握算法的基本概念和程序设计语言及基本的程序设计方法，掌握基本的数据结构及其运算。

2．实验目的

a)掌握一门程序设计语言

b)掌握算法及程序设计的一般策略与方法

c)掌握算法实验的一般步骤

d)掌握算法分析与设计、算法比较的一般方法

e)掌握算法实验中的时空复杂度的分析方法

f)掌握算法实验方案的设计方法

3．实验内容与要求

a)选择一个合适的程序设计语言（如C、C++、PASCAL等）

b)根据问题设计算法。问题如下

（百钱买百鸡问题）假设公鸡5元钱一只，母鸡3元钱一只，小鸡一元钱3只。要用100块钱刚好买100只鸡，问有多少种买法，每种买法中公鸡、母鸡、小鸡的数量各为多少？设计一个实验方案，验证求解此问题的算法的正确性，比较并分析各算法的优劣。

c)设计实验方案。方案中应包括

i.多种问题求解算法

ii.算法执行时间获取方法

iii.抗时间“噪声”方法

iv.时间结果分析对比方法

d)根据算法和实验方案设计实验程序

e)设计求解此问题的多种算法，并将它们转换成相应程序。

f)分析各算法（程序）的特点，比较它们的优劣。

g)安装程序设计语言系统。

h)输入各个程序，验证它们的正确性。

i)设计并运行能统计各程序执行时间并能抗“噪声”的程序，统计各算法的时间开销，并与之前所做的理论分析比较，看是否一致。

4．实验时间：4学时

5．附加实验与思考

自选一个问题，设计多种算法和程序并重复上述实验。

实验项目二：分治法算法设计

1．预习要求

预习教材第二章，掌握分治法的基本思想和一般方法，理解运用分治思想设计算法的基本方法及所设计出的几个常用算法。

2．实验目的

a)掌握分治法算法设计的一般思想和方法。

b)理解并掌握二分查找、归并分类、快速分类算法。

c)能熟练运用分治法求解问题。

d)实验中所准备的数据是有代表性的。

3．实验内容与要求

a)写一个顺序查找算法，将其与二分查找算法一起转换成程序，上机验证。

b)选择不同规模的数据集运行上二程序，统计它们的时间开销并比较。

c)归并分类、快速分类算法转换成程序并验证之。

d)选择不同规模的数据集运行上二程序，统计它们的时间开销并比较。

e)准备一定规模的数据集用于实验。此数据集越大越有得于验证算法，可以考虑最终的数据个数超过10000个。

f)编写归并分类、快速分类程序，将上数据集中的数据分类。可以使用较少的数据调试程序时。

g)用规模从小到大的数据集运行上述程序，统计它们的运行时间，并作对比分析。

h)编写顺序查找、二分查找程序。

i)将查找程序与分类程序结合起来，用不同规模的数据集运行，统计程序运行时间。

4．实验时间：4学时

5．附加实验与思考

任选一个可以用分治法求解的问题并用分治思想设计算法求解，将所设计算法转换成程序上机验证。

实验项目三：贪心方法算法设计

1．预习要求

预习教材第三章，掌握贪心法的基本思想和一般方法，理解运用贪心法思想设计算法的基本方法及所设计出的几个常用算法。

2．实验目的

a)掌握贪心法算法设计的一般思想和方法。

b)掌握背包问题、最小生成树、单源点最短路径算法设计。

c)掌握贪心法设计算法求解一般问题。

3．实验内容与要求

a)背包问题的贪心法算法设计和程序验证。

b)最小生成树算法设计和程序验证。

c)单源点最短路径算法设计和程序验证。

d)准备实验数据。对背包问题、最小生成树、最短路径问题按要求准备相应模拟数据，最好多准备几组。

e)背包问题的贪心法算法设计与验证。

f)最小生成树算法设计与验证。

g)单源点最短路径算法设计与验证。

4．实验时间：4 - 8学时

5．附加实验与思考

a)将教材中的作业排序算法转换成程序，用模拟数据运行，分析并比较算法效率。

b)修改最短路径算法，使得它在获得最短路径长度的同时还得到这些最短路径。

实验项目四：动态规划算法设计

1．预习要求

预习教材第四章，理解和掌握动态规划法的基本原理和一般方法，掌握运用动态规划法设计算法的基本方法及所设计出的几个常用算法。

2．实验目的

a)掌握动态规划法算法设计的一般原理和方法。

b)理解动态规划向前处理和向后处理的思想，掌握递推公式的求解方法。

c)掌握多段图、每对结点之间最短路径的计算算法。

d)能用动态规划法设计算法求解一般问题。

3．实验内容与要求

a)设计求解多段图问题的动态规划程序，上机调试通过。

b)设计求解每对结点之间最短路径问题的动态规划程序，上机调试通过。

c)准备几个多段图和几个道路交通图的数据。

d)输入求解多段图问题的动态规划程序，并用准备的数据调试通过。

e)输入每对结点之间最短路径问题的动态规划程序，并用准备的数据调试通过。

4．实验时间：4 - 8学时

5．附加实验与思考

a)如何用求单源点最短路径算法求解每对结点之间最短路径问题。

b)如何在求得每对结点之间最短路径长度的同时求得每对结点之间的最短路径。

实验项目五：基本检索与周游方法算法设计

1．预习要求

预习教材第五章，掌握基本检索和周游方法，理解运用基本检索和周游方法所设计出的几个常用算法。

2．实验目的

a)掌握基本检索与周游方法算法设计的一般思想。

b)掌握二元树、图的周游和检索算法。

c)理解树、与或树、对策树周游与检索的思想和方法。

3．实验内容与要求

a)二元树周游

b)图的周游

c)准备模拟二元树和模拟图的数据。

d)用递归方法设计二元树周游和检索程序，调试通过。周游和检索的次序可以是先序、中序和后序。

e)用非递归方法设计二元树周游和检索程序，调试通过。周游和检索的次序可以是先序、中序和后序。

f)用递归方法设计图的周游程序，调试通过。周游的次序可以是深度优先，也可以是宽度优先。

g)用非递归方法设计图的周游程序，调试通过。周游的次序可以是深度优先，也可以是宽度优先。

4．实验时间：4 - 8学时

5．附加实验与思考

设计一个图的D-Search检索和周游算法，上机调试通过，检验其结果。

实验项目六：回溯法算法设计

1．预习要求

预习教材第六章，掌握回溯法的基本思想和一般方法，理解运用回溯法设计算法的基本方法及所设计出的几个常用算法。

2．实验目的

a)掌握回溯法算法设计的一般思想和方法。

b)掌握8-皇后问题背包问题等算法的设计。

c)理解回溯法的用途，能用回溯法求解其它类似问题。

3．实验内容与要求

a)8-皇后问题的回溯算法。

b)背包问题的回溯算法。

c)为背包问题准备数据。

d)输入并调试8-皇后问题的回溯算法程序。

e)输入并调试背包问题的回溯算法程序。

4．实验时间：4 – 8 学时

5．附加实验与思考

a)传教士与生番问题。三个传教士和三个生番同在河的右岸准备渡河，只有一条船，每次最多乘2人。在穿梭运载的过程中，无论右岸或左岸或者船上，只要生番人数多于传教士的人数，则传教士就会被吃掉，除非传教士的人数为0。设计一个算法列出所有可能的渡河方案，保证传教士不会被生番吃掉。

b)分酒问题。有一个酒瓶装有8斤酒，没有量器，只有两个分别装5斤和3斤的空酒瓶。试设计一算法将8斤酒对分成两个4斤，给出分酒的步骤。

四、实验项目与学时分配 　　

本课程实验及实验报告成绩计入课程总成绩，占总成绩的比例为20%。

六、实验教材及参考书　　

1、教材

（1）、余祥宣、崔国华、邹海明  《计算机算法基础》 华中科技大学出版社 2000.1

2、参考书

（1）、卢开澄  《计算机算法导引——设计与分析》 清华大学出版社 1996.11

（2）、王晓东  《计算机算法设计与分析》 电子工业出版社 2001.1

附录一  实验报告样式

《算法分析与设计》实验报告

实验X   XXXXXX

姓名 学号 班级  xxxx班

时间 地点

同 组 人

指导教师

实验目的  

 1、

 2、

 3、

实验内容 

 1、

 2、

 3、

实验环境   

硬件： 

软件：

实验前准备

1、算法设计

2、程序设计

实验步骤

  1、

2、

……….

实验结果及其分析