《算法A》实验指导书(2015版).doc

算法设计与分析A实验指导书实验总要求1 遵守机房纪律，服从机房调度。2 努力准备上机内容，并预先做一些情况分析。3 仔细观察上机现象，记录主要情况。4 认真填写实验报告，包括姓名、所在班级、实验题目、实验目的、实验要求、程序框图及程序清单和运行结果，运行情况分析，意见，程序清单要有注释。5 四个实验订在一起，只要一个封皮。实验一 分治法程序设计目的和要求（一） 目的本实验的目的是了解分治策略算法思想，了解递归算法的设计思路，掌握两路合并排序算法。（二） 要求1. 写出源程序，并编译运行。2. 详细记录程序调试及运行结果。实验内容编写一个简单的程序，实现归并排序；算法思想分析两路合并排序：将待排序的元素序列一分为二分，得到两个长度基本相等的子序列，如同对半搜索的做法；然后对两个子序列分别排序，如果子序列较长，还可继续细分，直到子序列的长度不超过1为止；当分解所得的子序列已排列有序，可以将两个有序子序列，合并成一个有序子序列的方法，实现将子问题的解组合成原问题解，这是分治法不可缺少的一步。实验二 贪心算法程序设计目的和要求（一） 目的本实验的目的是了解贪心算法思想，掌握贪心算法典型问题，如迪杰斯特拉算法求单源最短路径问题。（二） 要求1.写出源程序，并编译运行。2.详细记录程序调试及运行结果。实验内容编写一个程序，实现单源最短路径问题。算法思想分析设集合S存放已经求得最短路径的终点，则V-S为尚未求得最短路径的终点集合。初始状态时，集合S中只有一个源点，设为结点s。迪杰斯特拉的具体做法是：首先将源点s加入S中；在算法的每一步中，按照最短路径值的非减次序，产生下一条最短路径(s-t)，并将该路径的终点tV-S加入S中；直到S=V，算法结束。当前最短路径：在算法执行中，一个结点tV-S的当前路径，是一条从源点s到结点t的路径，在该路径上，除结点t外，其余结点都属于S，当前最短路径是所有这些路径中的最短者。于是可将最优量度标准设计为：从V-S中选择具有最短的“当前最短路径”的结点加入集合S中。实验三 动态规划法程序设计目的和要求（一）目的掌握动态规划法思想，掌握最优子结构原理，掌握最长公共子序列问题，了解动态规划一般问题。最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。（二）要求1.写出源程序，并编译运行。2.详细记录程序调试及运行结果。实验内容编写一个程序，实现最长公共子序列问题。算法思想分析一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。实验四 回溯法程序设计目的和要求（一）目的掌握回溯法思想，掌握回溯递归原理，掌握n-皇后问题。（二）要求1.写出源程序，并编译运行。2.详细记录程序调试及运行结果。实验内容编写一个程序，实现8-皇后问题。算法思想分析皇后问题要求在一个88的棋盘上放置8个皇后，使得它们彼此不受“攻击”。8-皇后问题要求寻找在棋盘上放置这8个皇后的方案，使得它们中任何两个都不在同一行、同一列或同一斜线上。每一行可以而且必须放一个皇后，所以n皇后问题的解可以用一个n元向量X=（x1,x2,.xn）表示，其中，1in且1xin，即第n个皇后放在第i行第xi列上。由于两个皇后不能放在同一列上，所以，解向量X必须满足的约束条件为:xixj;若两个皇后的摆放位置分别是（i,xi）和（j,xj），在棋盘上斜率为-1的斜线上，满足条件i-j=xi-xj