最代碼廣告位
大風起兮大風起的gravatar頭像
大風起兮大風起2019-12-15 10:43:49

java編寫循環賽制日程表算法問題

1.問題描述

設有k(k=2^m)個運動員,要進行循環賽。現在要設計一個滿足以下要求的比賽日程表:

•  每個選手必須與其他k-1個選手各賽一次;

•  每個選手一天只能賽一次;

•   循環賽一共進行k-1天。

2.實驗目的

通過對循環賽日程表的練習,熟悉分治思想的應用。

3.分析                             

算法分析:

按分治策略,我們可以將所有的選手分為兩半,則n個選手的比賽日程表可以通過n/2個選手的比賽日程表來決定。遞歸地用這種一分為二的策略對選手進行劃分,直到只剩下兩個選手時,比賽日程表的制定就變得很簡單。這時只要讓這兩個選手進行比賽就可以了。如上圖,所列出的正方形表是8個選手的比賽日程表。其中左上角與左下角的兩小塊分別為選手1至選手4和選手5至選手8前3天的比賽日程。據此,將左上角小塊中的所有數字按其相對位置抄到右下角,又將左下角小塊中的所有數字按其相對位置抄到右上角,這樣我們就分別安排好了選手1至選手4和選手5至選手8在后4天的比賽日程。依此思想容易將這個比賽日程表推廣到具有任意多個選手的情形。

人數K=2:

           ?java編寫循環賽制日程表算法問題

人數K=4:        

   ?java編寫循環賽制日程表算法問題

人數K=8:

 java編寫循環賽制日程表算法問題java編寫循環賽制日程表算法問題

以此類推,我們不難發現,我們可以用分治的方法實現,現自頂向下分解,直到分解到最簡單的情況,即人數為2人,這時就可以兩兩比賽,表的填充為對角填充的方式,然后再自底向上填充表格,具體的看上面的的循環表就很好理解了。

4.源代碼展示

?? public static int[][] table(int n){
     //   int n = k<<1;
        int[][] a = new int[n][n];
        //構造賽程表第一行數據
        for(int i = 0; i<n;i++)
            a[0][i] = i+1;
        //采用分治算法,構造整個賽程表
        for(int r = 1;r<n;r<<=1){
            for(int i =0;i<n;i += 2*r){
                copy(a,r,r+i,0,i,r);
                copy(a,r,i,0,r+i,r);
            }
        }
        return a;
    }
    
    private static void copy(int[][] a, int tox, int toy, 
            int fromx, int fromy, int r){
        for(int i =0;i<r;i++){
            for(int j = 0;j<r;j++){
                a[tox+i][toy+j] = a[fromx+i][fromy+j];
            }
        }
        
    }
    public static void main(String[] args) {
        System.out.println("請輸入參賽人數:");
		Scanner scan =new Scanner(System.in);
		Integer read = scan.nextInt();
		int num=read.intValue();
		if(num%2!=0) {
			System.out.println("輸入人數不滿足要求");
			System.exit(0);
		}
        int[][] a = table(num);
        for(int i=0;i<a.length;i++){
            for(int j = 0;j<a[0].length;j++){
                System.out.print(a[i][j] + "|");
            }
            System.out.println();
        }
}
} 

5.程序結果展示

java編寫循環賽制日程表算法問題java編寫循環賽制日程表算法問題 java編寫循環賽制日程表算法問題


打賞

頂部客服微信二維碼底部
>掃描二維碼關注最代碼為好友掃描二維碼關注最代碼為好友
福彩3d组选020前后关系