算法设计与分析课程设计实验指导书上海第二工业大学计算机与信息学院软件工程系一、运动员比赛日程表设有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]←i3. end for4. 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. 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. for i←1 to k/29. for j←1 to k/210. A[v+i+k/2,j+k/2]←A[v+i,j] //沿对角线处理右下角11. end for12. end for13. for i←k/2+1 to k14. for j←1 to k/215. A[v+i-k/2,j+k/2]←A[v+i,j] //沿对角线处理右上角16. end for17. end for18. end if2、编制该问题的非递归算法，上机通过。

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

二、最长公共子序列运用动态规划法最长公共子序列问题，给出最优值并输出最优解。

提示：最长公共子序列的结构最长公共子序列的结构有如下表示：设序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的一个最长公共子序列Z=<z1, z2, …, zk>，则：若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=<x1, x2, …, xm-1>，Yn-1=<y1, y2, …, yn-1>，Zk-1=<z1, z2, …, zk-1>。

子问题的递归结构由最长公共子序列问题的最优子结构性质可知，要找出X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的最长公共子序列，可按以下方式递归地进行：当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=<x1, x2, …, xi>，Yj=<y1, y2, …, yj>。

当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。

其他情况下，由定理可建立递归关系如下：计算最优值直接利用上节节末的递归式，我们将很容易就能写出一个计算c[i,j]的递归算法，但其计算时间是随输入长度指数增长的。

由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。

计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>作为输入。

输出两个数组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]中。

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

三、桥本分数式把1，2，…，9这9个数字填入下式的9个方格中，要求：1、各数字不得重复2、数字“0”不得填在各分数的分子或分母的首位。

3、式中各分数为最简真分数，即分子分母没有大于1的公因数这一分数等式填数共有多少种解答，试用回溯法求出所有解答。

提示：⏹设置a数组，式中每一□位置用一个数组元素表示：⏹为避免解重复，设a(1)<a(4)，记式中3个分母分别为⏹m1=a(2)a(3)=a(2)*10+a(3)⏹m2=a(5)a(6)=a(5)*10+a(6)⏹m3=a(8)a(9)=a(8)*10+a(9)⏹所求分数等式等价于整数等式a(1)*m2*m3+a(4)*m1*m3=a(7)*m1*•m2成立。

⏹设置中间变量g：先赋值g=1；若出现某两数字相同(即a(i)=a(k))或a(1)>a(4)，则赋值g=0(重复标记)。

⏹首先从a(1)=1开始，逐步给a(i)(1≤i≤9)赋值，每一个a(i)赋值从1开始递增至9。

直至a(9)赋值，判断：⏹若i=9,g=1,a(1)*m2*m3+a(4)*m1*m3=a(7)*m1*m2•同时满足，为一组解，用n统计解的个数后，格式输出这组解。

⏹若i<9且g=1，表明还不到9个数字，则下一个a(i)从1开始赋值继续。

若a(9)=9，则返回前一个数组元素a(8)增1赋值(此时，a(9)又从1开始)再试。

若a(8)=9，则返回前一个数组元素a(7)增1赋值再试。

依此类推，直到a(1)=9时，已无法返回，意味着已全部试毕，求解结束。

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

四、删数字问题在给定的n个数字的数字串中，删除其中k(k<n)个数字后，剩下的数字按原次序组成一个新的正整数。

请确定删除方案，使得剩下的数字组成的新正整数最大。

例如在整数762191754639820463中删除6个数字后，所得最大整数为多大？提示：⏹操作对象是一个可以超过有效数字位数的n位高精度数，存储在数组a中。

⏹在整数的位数固定的前提下，让高位的数字尽量大，整数的值就大。

这就是所要选取的贪心策略。

⏹每次删除一个数字，选择一个使剩下的数最大的数字作为删除对象。

选择这样“贪心”操作，是因为删k个数字的全局最优解包含了删一个数字的子问题的最优解。

⏹当k=1时，在n位整数中删除哪一个数字能达到最大？从左到右每相邻的两个数字比较：若出现增，即左边数字小于右边数字，则删除左边的小数字。

若不出现增，即所有数字全部降序或相等，则删除最右边的小数字。

⏹例如，在18位整数762191754639820463中，删除1个数字，使剩下的17位数最大，如何删？⏹要使删除1个数字后的17位数最大，须首位数字最大。

首先，首位数字“7”大于第2位数字“6”比较，首位数字“7”不能删！⏹往后推，“6”与“2”比较，因6>2，为减，“6”不能删；⏹再往后推，“2”与“1”比较，因2>1,为减，“2”不能删；⏹继续往后推，“1”与“9”比较，因1<9，出现增，则删除左边的小数字“1”。

⏹当k>1（当然小于n），按上述操作,每一次操作从串首开始，每相邻的两个数字比较，出现“增”时，删除左边的小数字。

每次操作删除一个数字后，后面的数字向前移位。

⏹因此，只要从左至右每两相邻数字比较，出现“增”，即删除首数字。

直到不出现“增”时，此时如果还不到删除指定的k位，打印剩下串的左边n−k个数字即可（相当于删除了余下的最右边若干个小数字）。

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

五***马步遍历问题在给定棋盘中，马从棋盘的某个起点出发，按“马走日”的行走规则经过棋盘中的每一个方格恰好一次。

该问题称为马步遍历问题，经过棋盘的每一个方格恰好一次的线路称为马步遍历路径。

例如下表所示即为4行5列棋盘中，马从起点(1,1)出发的一条马步遍历路径。

求解在n行×m列广义棋盘中，马从棋盘的某个指定起点出发的马步遍历路径。

1. 回溯设计（1）位置表示⏹设置数组x(i),y(i)记录遍历中第i步的行列位置，设置二维数组d(u,v)记录棋盘中位置(u,v)即第u行第v列所在格的整数值，该整数值即为遍历路径上的步数。

⏹例如上表所示遍历，第8步走在(3,2），x(8)=3,y(3)=2；d(3,2)=8。

⏹若d(i,j)=0，表示(i,j)为空，可走位。

⏹注意到马走“日”形，对于有些马位，马最多可走8个方向。

如图3所示，当马处在(x,y)时可选的8个方向：（2）．控制马步规则⏹设置控制马步规则的数组a(k)、b(k)，若马当前位置为（x,y），马步可跳的8个位置分别为（x+a(k),y+b(k)）,其中⏹a(k)={ 2, 1,-1,-2,-2,-1, 1, 2 }⏹b(k)={ 1, 2, 2, 1,-1,-2,-2,-1 }（k=1,2, (8)在回溯过程中，需知第i步到第i+1步原已选取到了哪一个方向，设置t(i)记录第i步到第i+1步原已选取的方向数，回溯时只要从t(i)+1——8选取方向即可。

（3）回溯实施⏹设遍历起点为(u,v)，即位置(u,v)点为1。

显然x(1)=u,v(1)=v,d(u,v)=1。

⏹回溯从i=1开始进入条件循环，条件循环的条件为i>0。

即当i>0时还未回溯完成，继续试探走马。

⏹设置k（t(i)+1——8）循环依次选取方向，当t(i)=0时，即从1——8选取方向，并求出此方向的走马位置：u=x(i)+a(k), v=y(i)+b(k)。

⏹判断：若1≤u≤n, 1≤v≤m, d(u,v)=0，即所选位置在棋盘中且该位为空，可走马步d(u,v)=i+1；同时记录此时的方向t(i)=k，q=1标志此步走马成功，退出选方向循环。