算法设计与分析课程设计-实验指导书

算法设计与分析课程设计

实验指导书

上海第二工业大学

计算机与信息学院软件工程系

一、运动员比赛日程表

设有n=2k个运动员要进行网球比赛。设计一个满足以下要求的比赛日程表：

? 每个选手必须与其它n-1个选手各赛一次 ? 每个选手一天只能赛一次 ? 循环赛一共进行n-1天

1、 运用分治策略，该问题的递归算法描述如下，根据算法编制程序并上机

通过。

输入：运动员人数n（假定n恰好为2的i次方） 输出：比赛日程表A[1..n,1..n] 1. for i←1 to n //设置运动员编号 2. A[i,1]←i 3. end for

4. Calendar(0,n) //位移为0，运动员人数为n。

过程 Calendar(v, k) //v表示位移（v=起始行-1），k表示运动员人数。 1. if k=2 then //运动员人数为2个 2. A[v+2,2]←A[v+1,1] //处理右下角 3. A[v+1,2]←A[v+2,1] //处理右上角 4. else

5. Calendar(v,k/2) //假设已制定了v+1至v+k/2运动员循环赛日程表 6. Calendar(v+k/2,k/2) //假设已制定了v+k/2+1至v+k运动员循环赛日程表 7. comment：将2个k/2人组的解，组合成1个k人组的解。 8. for i←1 to k/2

9. for j←1 to k/2 10. A[v+i+k/2,j+k/2]←A[v+i,j] //沿对角线处理右下角 11. end for 12. end for

13. for i←k/2+1 to k 14. for j←1 to k/2 15. A[v+i-k/2,j+k/2]←A[v+i,j] //沿对角线处理右上角 16. end for 17. end for 18. end if

2、编制该问题的非递归算法，上机通过。

将如上文件保存在命名为“学号+姓名+实验一”的文件夹中并上传到指定的服务器。

二、最长公共子序列

运用动态规划法最长公共子序列问题，给出最优值并输出最优解。 提示：最长公共子序列的结构

最长公共子序列的结构有如下表示：

设序列X=和Y=的一个最长公共子序列Z=，则：

若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列； 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列； 若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。

其中Xm-1=，Yn-1=，Zk-1=。

子问题的递归结构

由最长公共子序列问题的最优子结构性质可知，要找出X=和Y=的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。

由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。

用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=，Yj=。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。其他情况下，由定理可建立递归关系如下：

计算最优值

直接利用上节节末的递归式，我们将很容易就能写出一个计算c[i,j]的递归算法，但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。

计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=和Y=作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与Yj的最长公共子序列的长度，b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于c[m,n]中。

【实验要求】

将如上文件保存在命名为“学号+姓名+实验二”的文件夹中并上传到指定的服务器。