资源描述
一
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<iostream>
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;i<step;i++)
21 for(int j=0;j<step;j++){
22 table[x+step+i][y+step+j]=table[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<<table[i][j]<<" ";
34 cout<<endl;
35 }
36 return 0;
37 }
三
1 #include<iostream>
2 using namespace std ;
3 #include<vector>
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<<n<<endl;
16 if(n<0){cout<<"m is wrong number !"<<endl;return 0;}
17 vector<vector<int>>arr(m,vector<int>(m));
18 for(i=0;i<m;i++)arr[i][0]=i+1;
19 for(i=0;i<n;i++){
20 int updown=0;
21 for(j=0;j<m;j++){
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;i<m;i++){
37 for(j=0;j<m;j++)
38 cout<<arr[i][j]<<" ";
39 cout<<endl;
40 }
41 return 0;
42 }
四
1、算法一：
#include<stdio.h>
#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<k;t++)//迭代处理，依次处理2^2,....,2^k个选手比赛日程
{
int temp=n;n=n*2;
//填左下角元素
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<iostream>
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<stdio.h>
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;
}
}
}
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
