资源描述：
《算法设计与分析课程设计-实验指导书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、算法设计与分析课程设计实验指导书上海第二工业大学计算机与信息学院软件工程系一、运动员比赛日程表设有n=2k个运动员要进行网球比赛。设计一个满足以下要求的比赛日程表：l每个选手必须与其它n-1个选手各赛一次l每个选手一天只能赛一次l循环赛一共进行n-1天1、运用分治策略，该问题的递归算法描述如下，根据算法编制程序并上机通过。输入：运动员人数n（假定n恰好为2的i次方）输出：比赛日程表A[1..n,1..n]1.fori←1ton//设置运动员编号2.A[i,1]←i3.endfor4.Calendar(0,n)//位移为0，运动
2、员人数为n。过程Calendar(v,k)//v表示位移（v=起始行-1），k表示运动员人数。1.ifk=2then//运动员人数为2个2.A[v+2,2]←A[v+1,1]//处理右下角3.A[v+1,2]←A[v+2,1]//处理右上角4.else5.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.fori←1tok/29.f
3、orj←1tok/210.A[v+i+k/2,j+k/2]←A[v+i,j]//沿对角线处理右下角11.endfor12.endfor13.fori←k/2+1tok14.forj←1tok/215.A[v+i-k/2,j+k/2]←A[v+i,j]//沿对角线处理右上角16.endfor17.endfor18.endif2、编制该问题的非递归算法，上机通过。将如上文件保存在命名为“学号+姓名+实验一”的文件夹中并上传到指定的服务器。二、最长公共子序列运用动态规划法最长公共子序列问题，给出最优值并输出最优解。提示：最长公共子序
4、列的结构最长公共子序列的结构有如下表示：设序列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=。子问题的递归结构由最长公共子序列问题的最优子结
5、构性质可知，要找出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-
6、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)个不同的子问题，因此
7、，用动态规划算法自底向上地计算最优值能提高算法的效率。 计算最长公共子序列长度的动态规划算法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]中。【实验要求】将如上文件保存在命名为“学号+姓名+实验二”的文件夹中
8、并上传到指定的服务器。三、桥本分数式把1，2，…，9这9个数字填入下式的9个方格中，要求：+=1、各数字不得重复2、数字“0”不得填在各分数的分子或分母的首位。3、式中各分数为最简真分数，即分子分母没有大于1的公因数这一分数等式填数共有多少种解答，试用回溯法求出所有解答。提示
