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