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

1、算法设计与分析课程设计实验指导书 一、运动员比赛日程表设有n=2k个运动员要进行网球比赛。设计一个满足以下要求的比赛日程表：l 每个选手必须与其它n-1个选手各赛一次l 每个选手一天只能赛一次l 循环赛一共进行n-1天1、 运用分治策略，该问题的递归算法描述如下，根据算法编制程序并上机通过。输入：运动员人数n（假定n恰好为2的i次方）输出：比赛日程表A1.n,1.n 1. for i1 to n /设置运动员编号2.Ai,1i 3.end for 4. Calendar(0,n)/位移为0，运动员人数为n。过程 Calendar(v, k) /v表示位移（v=起始行-1），k表示运动员人数。1

2、. if k=2 then/运动员人数为2个2. Av+2,2Av+1,1 /处理右下角3. Av+1,2Av+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 i1 to k/29. for j1 to k/210. Av+i+k/2,j+k/2Av+i,j/沿对角线处理右下角11. end for12. end for13. for ik/2

3、+1 to k 14. for j1 to k/215. Av+i-k/2,j+k/2Av+i,j/沿对角线处理右上角16. end for17. end for18. end if 2、编制该问题的非递归算法，上机通过。将如上文件保存在命名为“学号+姓名+实验一”的文件夹中并上传到指定的服务器。二、最长公共子序列运用动态规划法最长公共子序列问题，给出最优值并输出最优解。提示：最长公共子序列的结构最长公共子序列的结构有如下表示：设序列X=<x1, x2, , xm>和Y=<y1, y2, , yn>的一个最长公共子序列Z=<z1, z2, , zk>，则：若

4、xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；若xmyn且zkxm ，则Z是Xm-1和Y的最长公共子序列；若xmyn且zkyn ，则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

5、-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xmyn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。 由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。用ci,j记录序列Xi和Yj的最长公共子序列的长度。其中Xi=<x1, x2, , xi>，Yj=

6、<y1, y2, , yj>。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故ci,j=0。其他情况下，由定理可建立递归关系如下：计算最优值直接利用上节节末的递归式，我们将很容易就能写出一个计算ci,j的递归算法，但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共只有(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。 计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=<x1, x2, , xm>和Y=<y1, y2, , yn>作为输入。输出两个数组c0.m ,

7、0.n和b1.m ,1.n。其中ci,j存储Xi与Yj的最长公共子序列的长度，bi,j记录指示ci,j的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于cm,n中。【实验要求】 将如上文件保存在命名为“学号+姓名+实验二”的文件夹中并上传到指定的服务器。三、桥本分数式把1，2，9这9个数字填入下式的9个方格中，要求： + = 1、 各数字不得重复2、 数字“0”不得填在各分数的分子或分母的首位。3、 式中各分数为最简真分数，即分子分母没有大于1的公因数这一分数等式填数共有多少种解答，试用回溯法求出所有解答。提示：n 设置a数组，式中每一位置

8、用一个数组元素表示：n 为避免解重复，设a(1)<a(4)，记式中3个分母分别为n m1=a(2)a(3)=a(2)*10+a(3)n m2=a(5)a(6)=a(5)*10+a(6)n m3=a(8)a(9)=a(8)*10+a(9)n 所求分数等式等价于整数等式 a(1)*m2*m3+a(4)*m1*m3=a(7)*m1*m2成立。 n 设置中间变量g：先赋值g=1；若出现某两数字相同(即a(i)=a(k)或a(1)>a(4)，则赋值g=0(重复标记)。n 首先从a(1)=1开始，逐步给a(i)(1i9)赋值，每一个a(i)赋值从1开始递增至9。直至a(9)赋值，判断：n 若i

9、=9,g=1,a(1)*m2*m3+a(4)*m1*m3=a(7)*m1*m2同时满足，为一组解，用n统计解的个数后，格式输出这组解。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)个数字后，

10、剩下的数字按原次序组成一个新的正整数。请确定删除方案，使得剩下的数字组成的新正整数最大。例如在整数762191754639820463中删除6个数字后，所得最大整数为多大？ 提示：n 操作对象是一个可以超过有效数字位数的n位高精度数，存储在数组a中。n 在整数的位数固定的前提下，让高位的数字尽量大，整数的值就大。这就是所要选取的贪心策略。n 每次删除一个数字，选择一个使剩下的数最大的数字作为删除对象。选择这样“贪心”操作，是因为删k个数字的全局最优解包含了删一个数字的子问题的最优解。n 当k=1时，在n位整数中删除哪一个数字能达到最大？从左到右每相邻的两个数字比较：若出现增，即左边数字小于右边

11、数字，则删除左边的小数字。若不出现增，即所有数字全部降序或相等，则删除最右边的小数字。 n 例如，在18位整数762191754639820463中，删除1个数字，使剩下的17位数最大，如何删？n 要使删除1个数字后的17位数最大，须首位数字最大。首先，首位数字“7”大于第2位数字“6”比较，首位数字“7”不能删！n 往后推，“6”与“2”比较，因6>2，为减，“6”不能删；n 再往后推，“2”与“1”比较，因2>1,为减，“2”不能删 ；n 继续往后推，“1”与“9”比较，因1<9，出现增，则删除左边的小数字“1”。n 当k>1（当然小于n），按上述操作,每一次操作从

12、串首开始，每相邻的两个数字比较，出现“增”时，删除左边的小数字。每次操作删除一个数字后，后面的数字向前移位。n 因此，只要从左至右每两相邻数字比较，出现“增”，即删除首数字。直到不出现“增”时，此时如果还不到删除指定的k位，打印剩下串的左边nk个数字即可（相当于删除了余下的最右边若干个小数字）。将如上文件保存在命名为“学号+姓名+实验四”的文件夹中并上传到指定的服务器。五*马步遍历问题在给定棋盘中，马从棋盘的某个起点出发，按“马走日”的行走规则经过棋盘中的每一个方格恰好一次。该问题称为马步遍历问题，经过棋盘的每一个方格恰好一次的线路称为马步遍历路径。例如下表所示即为4行5列棋盘中，马从起点(1

13、,1)出发的一条马步遍历路径。 求解在n行×m列广义棋盘中，马从棋盘的某个指定起点出发的马步遍历路径。 1. 回溯设计 （1） 位置表示n 设置数组x(i),y(i)记录遍历中第i步的行列位置，设置二维数组d(u,v)记录棋盘中位置(u,v)即第u行第v列所在格的整数值，该整数值即为遍历路径上的步数。n 例如上表所示遍历，第8步走在(3,2），x(8)=3,y(3)=2；d(3,2)=8。n 若d(i,j)=0，表示(i,j)为空，可走位。n 注意到马走“日”形，对于有些马位，马最多可走8个方向。如图3所示，当马处在(x,y)时可选的8个方向：（2）控制马步规则 n 设置控制马步规则

14、的数组a(k)、b(k)，若马当前位置为（x,y），马步可跳的8个位置分别为（x+a(k),y+b(k)）,其中n a(k)= 2, 1,-1,-2,-2,-1, 1, 2 n b(k)= 1, 2, 2, 1,-1,-2,-2,-1 （k=1,2,8） 在回溯过程中，需知第i步到第i+1步原已选取到了哪一个方向，设置t(i)记录第i步到第i+1步原已选取的方向数，回溯时只要从t(i)+18选取方向即可。（3）回溯 实施n 设遍历起点为(u,v)，即位置(u,v)点为1。显然 x(1)=u,v(1)=v,d(u,v)=1。n 回溯从i=1开始进入条件循环，条件循环的条件为i>0。即当i&

15、gt;0时还未回溯完成，继续试探走马。n 设置k（t(i)+18）循环依次选取方向，当t(i)=0时，即从18选取方向，并求出此方向的走马位置：u=x(i)+a(k), v=y(i)+b(k)。n 判断：若1un, 1vm, d(u,v)=0，即所选位置在棋盘中且该位为空，可走马步d(u,v)=i+1；同时记录此时的方向t(i)=k，q=1标志此步走马成功，退出选方向循环。n 走马成功后，检测若i=m*n-1，标志已完成遍历，以二维形式输出此遍历解。 （4）继续求出所有解n 若需继续求解，方向t(i)与最后两步马位清“0”后，经i=i-1回溯继续，可求出所有遍历解。n 走马成功后，检测若i<m*n-1，还未完成遍历，经i=i+1继续下一步探索。n 若保持q