129944793285781250算法指导书(2012)

实验一：分治与递归

【实验目的】

应用分治与递归的算法求循环赛问题。

【实验性质】

验证性实验。

【实验内容与要求】

设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：⑴每个选手必须与其他n-1个选手各赛一次；⑵每个选手一天只能赛一次；⑶循环赛一共进行n-1天。按此要求可将比赛日程表设计－成有n行和n-l列的一个表。在表中第i行和第j列处填入第i个选手在第j天所遇到的选手。用分治法编写为该循环赛设计一张比赛日程表的算法并运行实现、对复杂度进行分析。

算法思想：按分治策略，我们可以将所有选手对分为两组，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用这种一分为二的策略对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。

下图所列出的正方形表是4个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手2和选手3至选手4第1天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手2和选手3至选手4在后2天的比赛日程。这种安排是符合要求的。

1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1

依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。下表是8个选手的日程安排表。

1 2 3 4 5 6 7 8

2 1 4 3 6 5 8 7

3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1

【调试分析和心得体会】

运行依算法写出的程序并分析算法实现的时间复杂度情况。

实验二：贪心算法

【实验目的】

应用贪心算法求解活动安排问题。

【实验性质】

验证性实验。

【实验要求】

活动安排问题是可以用贪心算法有效求解的很好的例子。

问题：有n个活动的集合A={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。

求解：安排尽量多项活动在该场地进行，即求A的最大相容子集。

设待安排的11个活动的开始时间和结束时间按结束时间的升序排列如下： i 1 2 3 5 3 0 6 4 5 7 5 3 8 6 5 9 7 6 10 8 8 11 9 8 12 10 2 13 11 12 14 s[i] 1 f[i] 4 将此表数据作为实现该算法的测试数据。

【算法分析】

分析：每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si

例：给出待安排的11个活动的开始时间和结束时间，要求安排尽量多项活动使用会场。 首先，任意输入这11个活动。

然后对活动以其完成时间的非减序排列。（意义：使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。）

将第一次活动结束时间f[1]与后面活动开始时间s[2]相比较，若s[2]

s[4]>f[1]，选中此活动。再用活动4的结束时间f[4]与其后活动的开始时间比较……同理类推，直到比较完成为止，最后选出合条件的活动1，活动4，活动8和活动11，它们将依次被安排使用该场地。

【调试分析和心得体会】

运行依算法写出的程序并分析算法实现的时间复杂度情况。

实验三：动态规划法

【实验目的】

应用动态规划算法思想求解矩阵连乘的顺序问题。

【实验性质】

验证性实验。

【实验要求】

应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想，应用动态规划策略写出算法及相应的程序，求解此题。要读懂读透A[i,j]，A[1,n]=A[1,k] ×A[k+1,n]，m[i][j]，s[i][j]各式所表达的含义并正确加以应用。m[i][j]的递归定义： 0 （ i=j ）

m[i][j]=

min{m[i][k]＋ m[k+1][j]+ni-1nknj （ i

要求完成：⑴算法描述⑵写出程序代码⑶完成调试⑷进行过程与结果分析。

【实验内容】

对于下列所描述的问题，给出相应的算法描述，并完成程序实现与时间复杂度的分析。该问题描述为：一般地，考虑矩阵A1，A2，… ，An的连乘积，它们的维数分别为d0,d1,…,dn,即Ai的维数为di-1×di (1≤i≤n)。确定这n个矩阵的乘积结合次序，使所需的总乘法次数最少。对应于乘法次数最少的乘积结合次序为这n个矩阵的最优连乘积次序。按给定的一组测试数据对根据算法设计的程序进行调试：6个矩阵连乘积A=A1×A2×A3×A4×A5×A6，各矩阵的维数分别为：A1：10×20，A2：20×25，A3：25×15，A4：15×5，A5：5×10，A6：10×25。完成测试。

【调试分析和心得体会】

运行依算法写出的程序并分析算法实现的时间复杂度情况。

实验四：回溯法

【实验目的】

应用回溯法求解图的着色问题

【实验性质】

综合性实验

【实验要求】

设下图G=(V,E)是一连通无向图，有3种颜色，用这些颜色为G的各顶点着色，每个顶点着一种颜色，且相邻顶点颜色不同。试用回溯法设计一个算法，找出所有可能满足上述条件的着色法，如果这个图不能用3种颜色着色满足相邻顶点颜色互异的要求就给出否定的回答。

1 0 4 2 3 实验五：分枝限界法

【实验目的】

应用分枝限界法的算法设计思想求解单源最短路径问题。

【实验内容与要求】

采用分支限界法编程求源点0到终点6的最短路径及其路径长度。

要求完成：⑴算法描述⑵写出程序代码⑶完成调试⑷进行过程与结果分析。

【实验性质】

在完成的过程中注意与回溯算法思想的比较，重点注意两种算法思想各自的特点以及实现方式比较。此实验的性质为综合性实验。

本文来源：https://www.bwwdw.com/article/d5yv.html