《算法设计与分析》课程实验指导书作者：姜文君杨明李梦娴单位：信息科学与工程学院2015年4月一、实验教学目标《算法设计与分析》旨在教会学生处理各种问题的方法，而通过实验，使学生能够把所学的方法用于具体的问题，并对所用算法进行比较分析，从而提高学生分析问题、解决问题的能力。
只有通过实验，学生才能判定自己所拟算法是否正确，是否算得上一个较优算法。
通过该课程的实验，使学生对课堂中所讲述的内容有一个直观的认识，更好地掌握所学的知识。
同时培养学生的实际动手能力，加强学生创新思维能力的培养。
二、实验教学主要内容实验课外时间组织：实验课外消化理论课堂，老师对项目实验的讲解，并且做好相关的设计与实现。
实验课内时间组织：学生在学院机房集中上机，实验教师在机房采用辅导和自由讨论相结合的方式进行指导。
最终完成实验项目的检查。
三、实验要求《算法设计与分析》是计算机专业的专业核心课程，其先修课程有数据结构和至少一门高级语言。
算法设计与分析课程将覆盖计算机软件实现中的大部分算法，并具有一定的深度和广度，使学生对计算机常用算法有一个全盘的了解；通过此课的学习，学生应该具有针对所给的问题设计和实现高效算法的能力。
通过上机实验，将使学生熟悉、掌握课堂教学中所学的大部分算法。
同时，上机实验是对学生在软件设计方面的综合训练，包括问题分析、总体结构设计、用户界面设计（可选）、程序设计基本技能和技巧等，以培养良好的编程风格和科学作风。
通过理论联系实际，以最终提高学生动手操作的能力以及分析问题的能力。
为了顺利完成《算法设计与分析》课程实验，学生应做到：1、熟练掌握一种高级程序设计语言及相关开发工具。
2、认真学习教材以及老师课堂讲解的项目实验相关内容，提前做好分析设计和实现。
3、自行完成代码编写，不得超袭。
实验课上课时间做好项目陈述和检查的准备，也可以针对一些问题做相应的讨论。
4、遵守机房纪律，服从辅导教师指挥，爱护实验设备。
5、实验课上进行相关的程序检查和测试，结束后提交所有的文档和源程序。
四、评分细则实验总分值80+附加分（实现了额外的程序实验等）实验项目名称分值评分标准备注1.分治算法实验（用分治法查找数组元素的最大值和最小值）10考勤2分，设计4分，程序检查2分，文档2分2.分治算法实验(用分治法实现归并排序算法)10考勤2分，设计4分，程序检查2分，文档2分3.动态规划法求解背包问题10考勤2分，设计4分，程序检查2分，文档2分4.贪心算法实验（求解背包问题）10考勤2分，设计4分，程序检查2分，文档2分5.贪心法求最短路径10考勤2分，设计4分，程序检查2分，文档2分6.回溯法实验(八皇后问题)10考勤2分，设计4分，程序检查2分，文档2分7.分支限界法实验（单源最短路径）10考勤2分，设计4分，程序检查2分，文档2分8.随机算法实验（Sherwood线性时间选择算法）10考勤2分，设计4分，程序检查2分，文档2分五、实验项目实验一分治算法实验（用分治法查找数组元素的最大值和最小值）1.实验目的通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。
2.实验要求在满足分治法的条件下，根据不同的输入用例，能准确的输出用例中的最大值与最小值。
并计算出程序运行所需要的时间。
3.实验内容用分治法查找数组元素的最大值和最小值（1）问题描述给定任意几组数据，利用分治法的思想，找出数组中的最大值和最小值并输出。
（2）实验步骤①先解决小规模的问题，如数组中只有1个元素或者只有两个元素时候的情况。
②将问题分解，如果数组的元素大于等于3个，将数组分为两个小的数组。
③递归的解各子问题，将(中分解的两个小的数组再进行以上两个步骤((最后都化为小规模问题。
④将各子问题的解进行比较最终得到原问题的解。
4.实验环境VS2010、VS20125.实验预习要求算法设计与分析、C/C++6.评分标准考勤2分，设计4分，程序检查2分，文档2分7.实验报告体现设计和主要算法的描述，并附上关键源程序的分析思路。
8.附录计算程序运行时间的算法如下所示：#include<time.h>#include<iostream>#include<iomanip>using namespace std;void main(){int i,j=0;double k=0.0;clock_t start,end,over;start=clock();end=clock();over=end-start;start=clock();for(i=0;i<1000000000;i++)j=j+i;end=clock();printf("The time is%6.3f",(double)(end-start-over)/CLK_TCK);}实验二分治算法实验(用分治法实现归并排序算法)1.实验目的通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。
2.实验要求了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1<k≤n，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。
那末，对于这类问题分治法是十分有效的。
同时要求计算出程序运行所需要的时间。
3.实验内容（1）问题描述给定任意几组数据，利用分治法的思想，将数据进行排序并将排好的数据进行输出。
（2）实验步骤①先解决小规模的问题。
②将问题分解，将数组分为两个小的数组。
③递归的解各子问题，将 中分解的两个小的数组再进行以上两个步骤最后都化为小规模问题。
④将各子问题的解进行合并最终得到原问题的解。
4.实验环境VS2010、VS20125.实验预习要求算法设计与分析、C/C++6.评分标准考勤2分，设计4分，程序检查2分，文档2分7.实验报告体现设计和主要算法的描述，并附上关键源程序的分析思路。
8.附录计算程序运行时间的算法如下所示：#include<time.h>#include<iostream>#include<iomanip>using namespace std;void main(){int i,j=0;double k=0.0;clock_t start,end,over;start=clock();end=clock();over=end-start;start=clock();for(i=0;i<1000000000;i++)j=j+i;end=clock();printf("The time is%6.3f",(double)(end-start-over)/CLK_TCK);}实验三动态规划法求解背包问题1.实验目的通过上机实验，要求掌握动态规划算法的问题描述、算法设计思想、程序设计。
2.实验要求利用动态规划算法求解背包问题，并计算出程序运行所需要的时间。
3.实验内容（1）问题描述给定几组数据，利用动态规划算法的思想，把0-1背包装满并使得其价值最大。
（2）实验步骤①把问题分解成若干个子问题，如背包仅可以容纳1个物品且可以容纳的质量为一等。
②依次求出各个子问题的最优解。
③每个子问题的最优解又可以从它的子问题的最优解中得到。
④通过各个子问题的最优解得到原问题的最优解。
4.实验环境VS2010、VS20125.实验预习要求算法设计与分析、C/C++6.评分标准考勤2分，设计4分，程序检查2分，文档2分7.实验报告体现设计和主要算法的描述，并附上关键源程序的分析思路。
8.附录计算程序运行时间的算法如下所示：#include<time.h>#include<iostream>#include<iomanip>using namespace std;void main(){int i,j=0;double k=0.0;clock_t start,end,over;start=clock();end=clock();over=end-start;start=clock();for(i=0;i<1000000000;i++)j=j+i;end=clock();printf("The time is%6.3f",(double)(end-start-over)/CLK_TCK);}实验四贪心算法实验（求解背包问题）1.实验目的通过上机实验，要求掌握贪心算法的问题描述、算法设计思想、程序设计。
2.实验要求设计程序，利用贪心算法求解背包问题，输出相应结果，并计算出程序运行所需要的时间。
3.实验内容（1）问题描述给定几组数据，利用贪心算法的思想，将物品装入背包并使得其价值最大。
（2）实验步骤①计算每种物品单位重量的价值Vi/Wi.②依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。
③若将这种物品全部装入背包后，背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。
④依此策略一直地进行下去，直到背包装满为止。
4.实验环境VS2010、VS20125.实验预习要求算法设计与分析、C/C++6.评分标准考勤2分，设计4分，程序检查2分，文档2分7.实验报告体现设计和主要算法的描述，并附上关键源程序的分析思路。
8.附录计算程序运行时间的算法如下所示：#include<time.h>#include<iostream>#include<iomanip>using namespace std;void main(){int i,j=0;double k=0.0;clock_t start,end,over;start=clock();end=clock();over=end-start;start=clock();for(i=0;i<1000000000;i++)j=j+i;end=clock();printf("The time is%6.3f",(double)(end-start-over)/CLK_TCK); }实验五：贪心法求最短路径1、实验目的：通过上机实验，掌握贪心算法的思想，利用Dijkstra算法求解最短路径并实现。
2、实验要求：使用贪心法求出给定图各点的最短路径，并计算算法的执行时间，分析算法的有效性。
3、实验内容：，如上所示，求出从（1）问题描述：已知一个有向网络G=(V,E)和源点V1源点出发到图中其余顶点的最短路径。
（2）实验步骤：1用邻接矩阵表示有向图，并进行初始化，同时选择源点；2选取候选集中距离最短的顶点，把其加入终点集合中；3以该顶点为新考虑的中间顶点，修改候选集中各顶点距离，若经过该点后，各点到达源点距离比原来距离短，则修改距离；4重复以上2、3步，直到所有候选集点都被加入到终点集中。