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

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

3、。遞歸地用這種一分為二的策略對選手進行分割，直到只剩下2個選手時，比賽日程表的制定就變得很簡單。這時只要讓這兩個選手進行比賽就可以了。 下圖給出的是六個選手的比賽日程表，其中第一列表示1-6個選手，第二列到第六列表示各個選手在第一天到第五天的所遇到的選手。(2) 框圖比賽人數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) / 實現n/2為奇數時的復制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+) / 這個循環比較難看懂

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;四、詳細設計及說明1.輸入數字n判斷n的奇偶性，根據情況進行分治法，安排賽程。2.用一個for循環輸出日程表的第一行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循環將問題分成幾部分，對于k=3，n=8，將問題分成3大部分，第一部分為，根據已經填充的第一行，填寫第二行，第二部分為，根據已經填充好的第一部分，填寫第三四行，第三部分為，根據已經填充好的前四行，填寫最后四行。for (int s=1;s=k;s+)N/=2;4.用一個for循環對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.設計界面，讓產生的表格輸出，用java實現。五、調試與測試1.還未輸入參數時：2.輸入一個奇數測試：3.輸入一個偶數測試：六、實習日志5月16日理解題意，題目要求，確定使用分治法解決。5月17日根據書上分治法的設計思路以及所提供的代碼按題目要求設計算法。5月18日 根據算法寫出代碼，并測試調試。5月19日 根據代碼，及要產生的表，用java設計界面。5月20日 總結，寫論文，ppt等。七、實習總結根據分治算法，將本問題進行了由小規模到大規模的求解設計，程序設計的關鍵點在于如何對問題進行劃分和填充公式的歸納。在劃分時，主要運用了

9、兩個for循環；在填充時，運用了兩個for循環。通過這次程序設計，加深了對分治算法的認識。解決具體問題時，程序故重要，但一個好的算法更加重要。不足之處即花費了很長時間來推導這個算法，對算法掌握還不夠熟練。八、附錄：核心代碼清單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) / 實現n/2為奇數時的復制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+) / 這個循環比較難看懂，試著在紙上走走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(網球賽程表);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(請輸入參賽隊數：);/ 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(歡迎使用網球賽程安排系統);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(還未輸入參賽隊數);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(選手/天數);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(當前參賽隊數為： + num);jf.add(centerPanel, BorderLayout.CENTER); else JButt