1、算法分析與設(shè)計綜合訓練實習報告題 目：利用分治思想設(shè)計循環(huán)賽日程表 學 號姓 名專業(yè)班級指導教師實踐日期目 錄一、綜合訓練目的與要求1二、綜合訓練任務(wù)描述1三、算法設(shè)計1四、詳細設(shè)計及說明1五、調(diào)試與測試1六、實習日志1七、實習總結(jié)1八、附錄：核心代碼清單1一、綜合訓練目的與要求本綜合訓練是軟件工程專業(yè)重要的實踐性環(huán)節(jié)之一，是在學生學習完算法分析課程后進行的綜合練習。本課綜合訓練的目的和任務(wù)：1. 鞏固和加深學生對算法分析課程基本知識的理解和掌握；2. 培養(yǎng)利用算法知識解決實際問題的能力；3. 掌握利用程序設(shè)計語言進行算法程序的開發(fā)、調(diào)試、測試的能力；4. 掌握書寫算法設(shè)計說明文檔的能力；5.

2、 提高綜合運用算法、程序設(shè)計語言、數(shù)據(jù)結(jié)構(gòu)知識的能力。二、綜合訓練任務(wù)描述有n個運動員要進行網(wǎng)球循環(huán)賽，設(shè)計比賽日程表：（1） 每個選手必須與其他n-1個選手賽一次；（2） 每個選手一天只能賽一次；（3） 當n是偶數(shù)時，循環(huán)賽進行n-1天；當n是奇數(shù)時，循環(huán)賽進行n天；（4） 要求掌握分治法或者多邊形方法；（5） 設(shè)計一個界面，顯示產(chǎn)生的日程表；（6） 編程語言不限；三、算法設(shè)計(1) 文字描述按分治策略，可以將所有的選手對分為兩組（如果n是偶數(shù)，則直接分為n/2每組，如果n是奇數(shù)，則?。╪+1）/2每組），n個選手的比賽日程表就可以通過為（n/2或（n+1）/2）個選手設(shè)計的比賽日程表來決定

3、。遞歸地用這種一分為二的策略對選手進行分割，直到只剩下2個選手時，比賽日程表的制定就變得很簡單。這時只要讓這兩個選手進行比賽就可以了。 下圖給出的是六個選手的比賽日程表，其中第一列表示1-6個選手，第二列到第六列表示各個選手在第一天到第五天的所遇到的選手。(2) 框圖比賽人數(shù)nnnynynyynyint i=1i=ni+a1i=ii+m=1s=1s=k?n=n/2int t=1t=n?int i=m+1i=2*mj=m+1j=m+1aij+(t-1)*m*2 = ai-mj+(t-1)*m*2-maij+(t-1)*m*2-m = ai-mj+(t-1)*m*2j+i+t+s+m=m*2k+=

4、1偽代碼public static void copy(int n) int m = n / 2;for (int i = 1; i = m; i+)for (int j = 1; j 1 & odd(n / 2)copyodd(n);elsecopy(n);public static void copyodd(int n) / 實現(xiàn)n/2為奇數(shù)時的復制int b = new intsize;int m = n / 2;for (int i = 1; i = m; i+) bi = m + i;bm + i = bi;for (int i = 1; i = m; i+) / 這個循環(huán)比較難看懂

5、，試著在紙上走走n=6時的情形，就能明白為什么要這么寫for (int j = 1; j m) aij = bi;am + ij = (bi + m) % n; elseam + ij = aij + m;for (int j = 2; j = m; j+) aim + j = bi + j - 1;abi + j - 1m + j = i;四、詳細設(shè)計及說明1.輸入數(shù)字n判斷n的奇偶性，根據(jù)情況進行分治法，安排賽程。2.用一個for循環(huán)輸出日程表的第一行for (int i = 1; i = num - 1; i+) jb_s1i = new jbutton(第 + i + 天);jb_s1

6、i.setbackground(color.lightgray);centerpanel.add(jb_s1i);3.用一個for循環(huán)將問題分成幾部分，對于k=3，n=8，將問題分成3大部分，第一部分為，根據(jù)已經(jīng)填充的第一行，填寫第二行，第二部分為，根據(jù)已經(jīng)填充好的第一部分，填寫第三四行，第三部分為，根據(jù)已經(jīng)填充好的前四行，填寫最后四行。for (int s=1;s=k;s+)n/=2;4.用一個for循環(huán)對4中提到的每一部分進行劃分for(int t=1;t=n;t+)對于第一部分，將其劃分為四個小的單元，即對第二行進行如下劃分同理，對第二部分（即三四行），劃分為兩部分，第三部分同理5.最后

7、，進行每一個單元格的填充。填充原則是：對角線填充for(int i=m+1;i=2*m;i+)/i控制行for(int j=m+1;j=2*m;j+) /j控制列 aij+(t-1)*m*2 = ai-mj+(t-1)*m*2-m;/*右下角的值等于左上角的值 */ aij+(t-1)*m*2-m = ai-mj+(t-1)*m*2;/*左下角的值等于右上角的值 */ 例：由初始化的第一行填充第二行1234567821436587進行第二部分的填充12345678214365873412785643218765最后是第三部分的填充12345678214365873412785643218765

8、567812346587214378563412876543216.設(shè)計界面，讓產(chǎn)生的表格輸出，用java實現(xiàn)。五、調(diào)試與測試1.還未輸入?yún)?shù)時：2.輸入一個奇數(shù)測試：3.輸入一個偶數(shù)測試：六、實習日志5月16日理解題意，題目要求，確定使用分治法解決。5月17日根據(jù)書上分治法的設(shè)計思路以及所提供的代碼按題目要求設(shè)計算法。5月18日 根據(jù)算法寫出代碼，并測試調(diào)試。5月19日 根據(jù)代碼，及要產(chǎn)生的表，用java設(shè)計界面。5月20日 總結(jié)，寫論文，ppt等。七、實習總結(jié)根據(jù)分治算法，將本問題進行了由小規(guī)模到大規(guī)模的求解設(shè)計，程序設(shè)計的關(guān)鍵點在于如何對問題進行劃分和填充公式的歸納。在劃分時，主要運用了

9、兩個for循環(huán)；在填充時，運用了兩個for循環(huán)。通過這次程序設(shè)計，加深了對分治算法的認識。解決具體問題時，程序故重要，但一個好的算法更加重要。不足之處即花費了很長時間來推導這個算法，對算法掌握還不夠熟練。八、附錄：核心代碼清單package .js3;import java.util.scanner;import javax.swing.*;import javax.swing.table.*;import java.awt.*;import java.awt.event.*;import java.util.*;class text1 public static final in

10、t size = 50;public static int a = new intsizesize;public static void copy(int n) int m = n / 2;for (int i = 1; i = m; i+)for (int j = 1; j 1 & odd(n / 2)copyodd(n);elsecopy(n);public static void copyodd(int n) / 實現(xiàn)n/2為奇數(shù)時的復制int b = new intsize;int m = n / 2;for (int i = 1; i = m; i+) bi = m + i;bm +

11、 i = bi;for (int i = 1; i = m; i+) / 這個循環(huán)比較難看懂，試著在紙上走走n=6時的情形，就能明白為什么要這么寫for (int j = 1; j m) aij = bi;am + ij = (bi + m) % n; elseam + ij = aij + m;for (int j = 2; j = m; j+) aim + j = bi + j - 1;abi + j - 1m + j = i;public class text implements actionlistener jframe jf;jbutton jb;jpanel centerpane

12、l;jtextfield textfield;jlabel jl_w;imageicon icon = new imageicon(qck.jpg);jpanel southpanel;jpanel wpanel;text1 text;public static void main(string args) text frame = new text();public text() jf = new jframe(網(wǎng)球賽程表);jf.setbounds(150, 150, 550, 550);jf.setdefaultcloseoperation(jframe.exit_on_close);f

13、inal jpanel viewpanel = new jpanel();container c = jf.getcontentpane();viewpanel.setbackground(color.lightgray);textfield = new jtextfield();jlabel jl = new jlabel(請輸入?yún)①愱爺?shù)：);/ jl.setbackground(color.red);viewpanel.add(jl);textfield.setcolumns(10);viewpanel.add(textfield);jb = new jbutton(確定);jb.adda

14、ctionlistener(this);viewpanel.add(jb);c.add(viewpanel, borderlayout.north);centerpanel = new jpanel();jlabel j = new jlabel();j.settext(歡迎使用網(wǎng)球賽程安排系統(tǒng));j.setfont(new font(, font.bold, 16);j.setbounds(100, 100, 0, 0);j.sethorizontalalignment(j.center);j.sethorizontaltextposition(j.center);j.setvertical

15、textposition(j.bottom);j.seticon(icon);centerpanel.add(j);southpanel = new jpanel();jl_w = new jlabel(還未輸入?yún)①愱爺?shù));southpanel.add(jl_w);wpanel = new jpanel();jpanel epanel = new jpanel();c.add(centerpanel, borderlayout.center);c.add(southpanel, borderlayout.south);c.add(wpanel, borderlayout.west);c.add

16、(epanel, borderlayout.east);jf.setvisible(true);public void actionperformed(actionevent e) if (e.getsource() = jb) string str = textfield.gettext();int num = integer.parseint(str);centerpanel.removeall();centerpanel.repaint();centerpanel.validate();final gridlayout gridlayout = new gridlayout(num +

17、1, num);centerpanel.setlayout(gridlayout);text.tournament(num);if (!text.odd(num) jbutton jb_s = new jbuttonnum + 2num + 1;jb_s11 = new jbutton(選手/天數(shù));jb_s11.setbackground(color.orange);centerpanel.add(jb_s11);for (int i = 1; i = num - 1; i+) jb_s1i = new jbutton(第 + i + 天);jb_s1i.setbackground(colo

18、r.lightgray);centerpanel.add(jb_s1i);for (int i = 2; i = num + 1; i+) for (int j = 1; j = num; j+) jb_sij = new jbutton();jb_sij.setbackground(color.cyan);centerpanel.add(jb_sij);for (int i = 2; i = num + 1; i+) for (int j = 1; j = num; j+) jb_sij.settext(選手 + text.ai - 1j);jl_w.settext(當前參賽隊數(shù)為： + num);jf.add(centerpanel, borderlayout.center); else jbutt