算法上机实验报告

实 验 报 告

填写时间：2013.12.4

课程名称 任课教师 姓名 算法设计与分析 戴瀚波 学号 专业年级 实验一：课程项目讨论（Class room sitting pattern project） 实验目的： 根据学生上课座位就坐模式（位置）预测学生考试成绩 实验步骤： 1. 大量统计一个班级所有学生上课就坐座位位置及考试成绩； 2. 根据教室座位分布情况，建立适当的坐标，方便直观的确定学生选择的座位位置； 3. 分析数据，选择合适的算法； 4. 根据选择的算法编写程序，实现实验目的； 5. 输入数据，将输出的结果与考试成绩进行比较，并分析实验中的误差。 实验结果： 第 1 页 共 8 页

算法分析与设计实验报告 计算机与信息工程学院

实验二：Merge Sort（归并排序） 实验目的： 多次将两个或两个以上的有序表合并成一个新的有序表 实验步骤： 1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列； 2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置； 3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置； 第 2 页 共 8 页

算法分析与设计实验报告 计算机与信息工程学院

4. 重复步骤3直到某一指针超出序列尾； 5. 将另一序列剩下的所有元素直接复制到合并序列尾。 实验结果： 输入为：18，2，20，34，12，32，6，16 输出为：2，6，12，16，18，20，32，34 实验三：Counting inversion（统计逆序数） 实验目的： 用Merge Sort算法统计给定序列中的逆序数 实验步骤： 1. 利用归并排序产生两个有序序列seg1,seg2; 2. 对于序列seq1中的某个数a[i],序列seq2中的某个数a[j]，如果a[i]a[j]，那么逆序数为seq1中a[i]后边元素的个数(包括a[i])，即len1-i+1; 3. 累加每次递归过程的逆序数，在完成整个递归过程之后，求得最后累加； 4． 累加和为逆序数个数，输出逆序数。 实验结果： 输入为：1，3，5，7，2，4，6 输出为： 第 3 页 共 8 页

算法分析与设计实验报告 计算机与信息工程学院

逆序数为：6 实验四：quick sort（快速排序） 实验目的： 采用快速排序方法对输入的数据按升序和降序两种顺序进行排序，并显示中间排序的过程。 实验步骤： 1. 设置两个变量i、j，排序开始的时候：i=0，j=N-1； 2. 以第一个数组元素作为关键数据，赋值给key，即key=A[0]； 3. 从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将值为key的项与A[j]交换； 4. 从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将值为key的项与A[i]交换； 5. 重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[j]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。 实验结果： 输入为：6，8，7，9，0，1，3，2，4，5 第 4 页 共 8 页

算法分析与设计实验报告 计算机与信息工程学院

输出为：0，1，2，3，4，5，6，7，8，9 实验五:Karger’s algorithm 实验目的： 无向图中任意两点s和t，它们要么属于最小割的两个不同集中，要么属于同一个集 实验步骤： 1. min=MAXINT，固定一个顶点P 2. 从点P用类似prim的s算法扩展出“最大生成树”，记录最后扩展的顶点和最后扩展的边 3. 计算最后扩展到的顶点的切割值（即与此顶点相连的所有边权和），若比min小更新min 4. 合并最后扩展的那条边的两个端点为一个顶点 5. 转到2，合并N-1次后结束 6. min即为所求，输出min 实验结果： 实验六：Dijkstra's Algorithm（迪杰斯特拉算法） 第 5 页 共 8 页

算法分析与设计实验报告 计算机与信息工程学院

实验目的： 以某一节点为出发点,计算从该节点出发到所有其他节点的最短路径 实验步骤： 按路径长度递增次序产生算法： 1. 把顶点集合V分成两组： （1）S：已求出的顶点的集合（初始时只含有源点V0）； （2）V-S=T：尚未确定的顶点集合。 2. 将T中顶点按递增的次序加入到S中，保证： （1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度； （2）每个顶点对应一个距离值。 S中顶点：从V0到此顶点的长度 T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度 依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和 3. 求最短路径步骤 算法步骤如下： （1）初始时令 S={V0},T={其余顶点}，T中顶点对应的距离值 若存在，d(V0,Vi)为弧上的权值 若不存在，d(V0,Vi)为∞ （2）从T中选取一个其距离值为最小的顶点W且不在S中，加第 6 页 共 8 页

算法分析与设计实验报告 计算机与信息工程学院

入S （3）对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值 （4）重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止 实验结果： 程序中的输入为： 输出为： 实验七：DFS与BFS 实验目的： 通过深度优先和广度优先遍历图 实验步骤： 第 7 页 共 8 页

算法分析与设计实验报告 计算机与信息工程学院

1. 从图的某个顶点v出发，首先访问初始顶点v； 2. DFS：选择一个与顶点v相邻且没有被访问过的顶点w为初始顶点； BFS:访问顶点v的所有未被访问过的邻接顶点v1,v2,…,vt； 3. BFS：从w出发深度优先遍历，直到图中与当前顶点v相邻的所有顶点都被访问为止。 DFS:按照v1,v2,…,vt的次序访问每一个顶点的所有未被访问过的邻接点，直到图中所有和初始顶点v有路径想通的顶点都被访问过为止。 实验结果： 遍历图形为： DFS：2 1 0 3 4 BFS：2 1 3 4 0

第 8 页 共 8 页