算法.循环赛.doc

一
void Table(int k,int * *a)
{

int n=1;
for (int i=1;i<=k;i++)n* =2;
for (int i=1;i<=n;i++)a[1][i]=i;
int m=1;

for (int s=1;s<=k;s++)
{

n/=2;

for(int t=1;t<=n;t++)

for(int i=m+1;i<=2*m;i++)

for(int j=m+1;j<=2*m;j++)
{

a[i][j+(t-1)*m*2]=a[i-m][j+(t-1)*m*2-m];

a[i][j+(t-1)*m*2-m]=a[i-m][j+(t-1)*m*2];
}

m* =2;

}

}

二

1 #include
2 using namespace std;
3 const int SIZE = 100;
4 int table[SIZE][SIZE];
5 void fillTable(int x,int y,int step){
6 /*其实step=2的情形也可以用下面的递归通式完成
7 if(step==2){
8 table[x+1][y+1]=table[x][y];
9 table[x][y+1]=table[x+1][y];
10 return ;
11 }*/
12 if(step==1)return;
13
14 step/=2;//把原问题分为四个表格的填写
15 fillTable(x,y,step);//填写左上子表格
16 fillTable(x+step,y,step);//填写左下的子表格
17 //右上的子表格抄写左下的子表格
18 //右下的子表格抄写左上的子表格
19 //注意坐标要使用相对坐标
20 for(int i=0;itable[x+i][y+j];
23 table[x+i][y+step+j]=table[x+step+i][y+j];
24 }
25 }
26
27 int main(){
28 int n;cin>>n;
29 for(int i=1;i<=n;i++)table[i][1]=i;
30 fillTable(1,1,n);
31 for(int i=1;i<=n;i++){
32 for(int j=1;j<=n;j++)
33 cout<e[i][j]<<" ";
34 cout<
2 using namespace std ;
3 #include
4 int main(){
5 int m,n=-1,i,j,k;
6 int two[20];
7 cin>>m;
8 j=1;
9 for(i=0;i<20;i++){
10 two[i]=j;
11 if(m==j)n=i;
12 j*=2;
13
14 }
15 cout<>arr(m,vector(m));
18 for(i=0;i{
22 if(j%two[i]==0)updown++;
23 if(updown%2==1){
24 for(k=two[i];k<=two[i+1]-1;k++){
25 arr[j+two[i]][k]=arr[j][k-two[i]];
26 }
27 }
28 else{
29 for(k=two[i];k<=two[i+1]-1;k++){
30 arr[j-two[i]][k]=arr[j][k-two[i]];
31 }
32 }
33 }
34 }
35
36 for(i=0;ilude
#define N 64
void GameTable(int k,int a[][N])
{
//n=2^k(k>=1)个选手参加比赛，二维数组a表示日程安排，数组下标从1开始
int n=2;//k=0,两个选手比赛日程可直接求得
//求解两个选手比赛日程，得到左上角元素
a[1][1]=1;a[1][2]=2;
a[2][1]=2;a[2][2]=1;
int i,j,t;
for(t=1;t下角元素
    for(i=temp+1;i<=n;i++)
         for(j=1;j<=temp;j++)
             a[i][j]=a[i-temp][j]+temp;//左下角元素和左上角元素的对应关系
         //将左下角元素抄到右上角
         for(i=1;i<=temp;i++)
             for(j=temp+1;j<=n;j++)
                 a[i][j]=a[i+temp][(j+temp)%n];
             //将左上角元素抄到右下角
             for(i=temp+1;i<=n;i++)
                 for(j=temp+1;j<=n;j++)
                     a[i][j]=a[i-temp][j-temp];

}
for(i=1;i<=n;i++)//显示日程表
     for(j=1;j<=n;j++)
     {
         printf("- ",a[i][j]);
         if(j==n)
             printf("n");
     }
}
void main()
{
int a[N][N];
int k;
printf("输入选手的个数：(注意为2的平方)");
scanf("%d",&k);
GameTable(k,a);
}
2、结果验证
当两个选手，即k=1时

当4个选手时，即k=2

当8个选手，即k=3

当16个选手时，即k=16

时间复杂度分析：
迭代处理的循环体内部3个循环语句，每个循环语句都是一个嵌套的for循环，且它们的执行次数相同，基本语句是最内层循环体的赋值语句，即填写比赛日程表的元素。基本执行语句的执行次数是：
T(n)=
所以时间复杂度为O(4k)

改进的算法：
#include   
using namespace std;   

const int SIZE = 50;   
int a[SIZE][SIZE];   

void copy(int n);   
void tournament(int n);     
int odd(int n);  //判断奇偶性 
void makecopy(int n);  //makecopy 与copy算法类似，但是区分了n/2为奇数或偶数的情形 
void copyodd(int n);  // 实现n/2为奇数时的复制   

void  main()   
{   

    int n;   
    int i,j;   
    cin >> n;   
    tournament(n);   
    if(odd(n))   // n为奇数和偶数输出情况不同，要分别考虑    
    {   
        for(i = 1; i<=n; i++)   
        {   
            for(j = 1; j<=n+1; j++)   
                if(a[i][j] == n+1)   
                    cout << "0  ";   
                else  
                    cout << a[i][j] << "  " ;   
            cout << endl;   
        }   
    }   
    else  
    {   
        for(i = 1; i<=n; i++)   
        {   
            for(j = 1; j<=n; j++)   
                cout << a[i][j] << "  " ;   
            cout << endl;   
        }   

    }      
}   

void copy(int n)       
{   
    int m = n/2;   
    for(int i = 1; i<=m; i++)   
        for(int j = 1; 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];   
        }   
}   

void tournament(int n)   
{   
    if(n == 1)   
    {   
        a[1][1] = 1;   
        return;    
    }   
    if(odd(n))   
    {   
        tournament(n+1);   
        return;   
    }   
    tournament(n/2);   
    makecopy(n);   
}   

int  odd(int n)   
{   
if(n%2==1)
    return 1;  
else return 0;
}   

void makecopy(int n)  //makecopy 与copy算法类似，但是要区分n/2为奇数或偶数的情形   
{   
    if(n/2 > 1 && odd(n/2))    
        copyodd(n);   
    else  
        copy(n);   
}   

void copyodd(int n)        // 实现n/2为奇数时的复制   
{   
    int b[SIZE];   
    int m = n/2;   
    for(int i = 1; i<=m; i++)   
    {   
        b[i] = m+i;   
        b[m+i] = b[i];   
    }   
    for(i = 1; i<=m; i++)             
    {   
        for(int j=1; j<=m+1; j++)   
        {   
            if(a[i][j] > m)   
            {   
                a[i][j] = b[i];    
                a[m+i][j] = (b[i] + m)%n;   
            }   
            else  
                a[m+i][j] = a[i][j] + m;   
        }   
        for(j = 2; j<=m; j++)   
        {   
            a[i][m+j] = b[i+j-1];    
            a[b[i+j-1]][m+j] = i;   
        }   
    }   
} 
结果验证：
当参赛人数为偶数 8时

当参赛人数为奇数  7时
六

#include
void copy(int n);
void tour(int n);
void makecopy(int n);
void copyodd(int n);
int a[100][100];
int b[100];
int main()
{
int n,i,j;
printf("Please input n :\n");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
a[1][i]=i;
a[i][1]=i;
}
tour(n);
if(n % 2 == 1)
for(i=1;i<=n;i++)
{
for(j=1;j<=n+1;j++)
{
if(a[i][j] == n +1)
printf(" ");
else
printf("%-4d",a[i][j]);
}
printf("\n");;
}
else
for(i=1;i<n;i++)
{
for(j=1;j <= n;j++)
{
if(a[i][j] == n +1)
printf(" ");
else
printf("%-4d",a[i][j]);
}
printf("\n");;
}
}
void copy(int n)
{
int m = n/2;
int i,j;
for(i=1;i<=m;i++)
for(j=1;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];
}
}
void tour(int n)
{
if(n==1)
{
a[1][1]=1;
return;
}
if(n%2==1)//奇数
{
tour(n+1);
return;
}
tour(n/2);
makecopy(n);
}
void makecopy(int n)
{
if(n/2>1 && ((n/2)%2))
copyodd(n);
else
copy(n);
}
void copyodd(int n)
{
int i,j;
int m=n/2;
for(i=1;i<=m;i++)
{
b[i]=m+i;
b[m+i]=b[i];
}
for(i=1;i<=m;i++)
{
for(j=1;j<=m+1;j++)
{
if(a[i][j]>m)
{
a[i][j]=b[i];
a[m+i][j]=(b[i]+m)%n;
}
else
{
a[m+i][j]=a[i][j]+m;
}
}
for(j=2;j<=m;j++)
{
a[i][m+j]=b[i+j-1];
a[b[i+j-1]][m+j]=i;
}
}
}