注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

众里寻他千百度,名师成就满分路

AP 微积分 AP 计算机 腾飞的博客

 
 
 

日志

 
 
关于我

大学讲师,中国首批AP计算机教师,著有中国第一套,历经五年实践证明深受学生欢迎的成功的AP计算机双语教材,2013年以93%的满分率开创了中国AP计算机成功的先河,远远超出全美26.6%的满分率,为中国AP计算机教学树立了典范,并在同年加拿大计算机竞赛中勇夺桂冠,任教学生获哥伦比亚大学,麻省理工学院,卡耐基梅隆大学,宾夕法尼亚大学,康奈尔大学,西北大学等学校录取,远程学生遍及北京、长春、南京、重庆、广州、济南, 深圳、成都、费城,洛杉矶,加州,宾州,新罕布什尔州等地,希望借此平台为信息技术的发展做出贡献!

网易考拉推荐

【转载】循环赛程表--java实现  

2017-07-22 19:00:12|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本文转载自The cat《循环赛程表--java实现》

题目: 

设计一个满足以下要求的比赛日程表:

(1)每个选手必须与其他n-1个选手各赛一次;

(2)每个选手一天只能赛一次;

(3)循环赛一共进行n-1天。

分析:

 按分治策略,将所有的选手分为两半,n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割,直到只剩下2个选手时,比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。

 

1

2

3

4

5

6

7

8

2

1

4

3

6

5

8

7

3

4

1

2

7

8

5

6

4

3

2

1

8

7

6

5

5

6

7

8

1

2

3

4

6

5

8

7

2

1

4

3

7

8

5

6

3

4

1

2

8

7

6

5

4

3

2

1

package org.hbu.mlc.match_table;

public class Table {

 /**单循环赛程表,n要为偶数
  * @param args
  */
 public void table(int a[][], int n)
 {
  if(n==1)
  {
   a[0][0]=1;
  }
  else
   table(a,n/2);
   copy(a,n);
 }
 
 public void copy(int[][] a, int n) {
  int m=n/2;
  for(int i=0;i<m;i++)
  {
   for(int j=0;j<m;j++)
   {
    a[i][j+m]=a[i][j]+m;
    a[i+m][j]=a[i][j+m];
    a[i+m][j+m]=a[i][j];

   }
  }
 }

 public static void main(String[] args) {
  // n设定为8,即有8个队参加,n为偶数
  int n=8;
  int[][] a=new int[n][n];
  Table ta=new Table();
  ta.table(a,n);
  for(int i=0;i<n;i++)
  {
   for(int j=0;j<n;j++)
   {
    //System.out.print("i="+i);
    //System.out.print("j="+j);
    System.out.print(a[i][j]);
    
   }
   System.out.println();
  }
 }

}

题目: 

设计一个满足以下要求的比赛日程表:

(1)每个选手必须与其他n-1个选手各赛一次;

(2)每个选手一天只能赛一次;

(3)循环赛一共进行n-1天。

分析:

 按分治策略,将所有的选手分为两半,n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割,直到只剩下2个选手时,比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。

 

 

1

 

 

2

 

 

3

 

 

4

 

 

5

 

 

6

 

 

7

 

 

8

 

 

2

 

 

1

 

 

4

 

 

3

 

 

6

 

 

5

 

 

8

 

 

7

 

 

3

 

 

4

 

 

1

 

 

2

 

 

7

 

 

8

 

 

5

 

 

6

 

 

4

 

 

3

 

 

2

 

 

1

 

 

8

 

 

7

 

 

6

 

 

5

 

 

5

 

 

6

 

 

7

 

 

8

 

 

1

 

 

2

 

 

3

 

 

4

 

 

6

 

 

5

 

 

8

 

 

7

 

 

2

 

 

1

 

 

4

 

 

3

 

 

7

 

 

8

 

 

5

 

 

6

 

 

3

 

 

4

 

 

1

 

 

2

 

 

8

 

 

7

 

 

6

 

 

5

 

 

4

 

 

3

 

 

2

 

 

1


public class 循环赛日程表 {
     
    //  这个只是应用于 2 的k 次方个人参加比赛,因为在分治过程中  
        // 不允许出现奇数  
    public static void divide(int data[][],int n)  
    {  
        if(n==1)  
        {  
            data[1][1] = 1;  
            return ;  
        }  
        divide(data,n/2);  
        conquer(data, n);  
    }  
    public static void conquer(int data[][],int n)  
    {  
        int m = n/2;  
        for(int i=1;i<=m;i++)  
        {  
            for(int j=1;j<=m;j++)  
            {  
                data[i][j+m] = data[i][j]+m;  
                data[i+m][j] = data[i][j+m];  
                data[i+m][j+m] = data[i][j];  
            }  
        }  
    }  
    public static void output(int[][] a)
    {
        for(int r=0;r
        {
            for(int c=0;c
                System.out.print(a[r][c]+"\t");
            System.out.println("");
        }
    }
    public static void main(String args[])  
    {  
        int n = 4;  
        int data[][] = new int[n+1][n+1];  
        divide(data,n+1);  
        output(data);
//        for(int i=1;i
//        {  
//            for(int j=1;j
//            System.out.print(data[i][j]+" ");  
//            System.out.println();  
//        }  
    }  
}

public class NewClass {
    
     public static void Table1(int n)
    {
        int m=(int)(Math.pow(2,n));
        int[][] table=new int[m][m];
        table[0][0]=1;
        int k=1,half=1;
        while(k<=n)
        {
           for(int i=0;i
           {  
            for(int j=0;j
            {  
                table[i][j+half] = table[i][j]+half;  
                table[i+half][j] = table[i][j+half];  
                table[i+half][j+half] = table[i][j];  
            }  
           }  
           half*=2;
           k++;
        }
        output(table);
    }
    public static void conquer(int data[][],int m)  
    {   

        for(int i=0;i
        {  
            for(int j=0;j
            {  
                data[i][j+m] = data[i][j]+m;  
                data[i+m][j] = data[i][j+m];  
                data[i+m][j+m] = data[i][j];  
            }  
        }          
    } 
    public static void Table2(int n)
    {
        int m=(int)(Math.pow(2,n));
        int[][] table=new int[m][m];
        table[0][0]=1;
        int k=1,half=1;
        while(k<=n)
        {
           conquer(table,half);
           half*=2;
           k++;
        }
        output(table);
    }
    public static void output(int[][] a)
    {
        for(int r=0;r
        {
            for(int c=0;c
                System.out.print(a[r][c]+"\t");
            System.out.println("");
        }
    }

    public static void main(String[] args) {
        Table2(1);
    }
}

package 循环赛日程表;

public class schedule
{
    private int level;
    public schedule(int level)
    {
        this.level=level;
        process(new int[][]{{1}},1);
    }
    public void process(int[][] last,int cur)
    {
        if (cur==level)
        {
            printanswer(last);
        }
        else
        {
            process(generate(last,cur,true),cur*2);
            process(generate(last,cur,false),cur*2);
        }
    }
    private void printanswer(int[][] x)
    {
        for (int a=0;a
        {
            for (int b=0;b
            {
                System.out.print(x[a][b]);
            }
            System.out.print("\n");
        }
        System.out.print("------------------------\n");
    }
    private int[][] generate(int[][] last,int cur,boolean state)
    {
        int temp[][]=new int[cur*2][cur*2];
        for (int a=0;a
        {
            for (int b = 0; b < temp[0].length; b++)
            {
                if (state) {
                    if (a > cur - 1 && b < cur) {
                        temp[a][b] = last[a - cur][b] + cur;
                    } else if (a < cur && b > cur - 1) {
                        temp[a][b] = last[a][b - cur] + cur;
                    } else if (a < cur && b < cur) {
                        temp[a][b] = last[a][b];
                    } else {
                        temp[a][b] = last[a - cur][b - cur];
                    }
                }
                else
                {
                    if (a > cur - 1 && b < cur) {
                        temp[a][b] = last[a - cur][b];
                    } else if (a < cur && b > cur - 1) {
                        temp[a][b] = last[a][b - cur];
                    } else if (a < cur && b < cur) {
                        temp[a][b] = last[a][b] + cur;
                    } else {
                        temp[a][b] = last[a - cur][b - cur] + cur;
                    }
                }
            }
        }
        return temp;
    }
    public static void main(String[] args)
    {
        new schedule(8);
    }
}

  评论这张
 
阅读(4)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017