使用分治策略递归和非递归和递推算法解决循环赛日程表代码

#include #include #include

const int MAX = 1024;//

int a[MAX][MAX];//二位数组 int Number=2,g_K=1;

clock_t start, finish;//开始和结束时间 double duration;//程序运行时间 void Menu();//菜单实现

void Test1(int k,int m);//分治策略 递归实现 void Test2(int k);//分治策略 非递归实现 void Test3(int k);//对推策略实现

int main(void) {

printf(\请输入指数k\\n\while(scanf(\ fflush(stdin); }

for (int i=1;i

printf(\参赛人员\

for(int z=1;z

printf(\

for( i=1;i<=Number;i++)// {

for(int j=1;j<=Number;j++)//第一列为参赛人员 printf(\ %d \ printf(\ } printf(\程序循环10000次所用的时间：%lfms\\n\ return 0; }

void Menu(){//菜单栏选项 int choice;

printf(\ \\n\

printf(\ 循环赛日程表 \\n\ printf(\ \\n\\n\ printf(\请选择采用什么方法实现 \\n\ printf(\输入1：分治策略递归算法\\n\\n\ printf(\输入2：分治策略非递归算法\\n\\n\ printf(\输入3：递推策略算法\\n\\n\ scanf(\ switch(choice){ case 1:{ system(\ start=clock(); for(int i=0;i<10000;i++) Test1(1,Number); finish=clock(); duration=finish-start; } break; case 2:{ system(\ start=clock(); for(int i=0;i<10000;i++) Test2(g_K); finish=clock(); duration=finish-start; } break; case 3:{ system(\ start=clock(); for(int i=0;i<10000;i++) Test3(Number); finish=clock(); duration=finish-start; } break; default: break; } }

void Test1(int k,int m)//采用分治策略递归实现 {

int i,j;

if(m==2)//只有两个人的时候 { a[k][1]=k; a[k+1][1]=k+1; } else { Test1(k,m/2); Test1(k+m/2,m/2); }

for(i=k;i

void Test2(int k){//分治策略非递归方式实现 int i,j; int n;

n=Number;//拷贝参赛选手人数 for(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(i = m+1 ; i <= 2*m ; i++) {

for(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; }

}

void Test3(int num){//递推算法实现 a[1][1]=1; int n,n0,i,j,k,k0; n0=1; n=2; k=g_K;//人数 for (k0=1;k0<=k;k0++) { for (i=n0+1;i<=n;i++) { for (j=1;j<=n;j++) { a[i][j]=a[i-n0][j]+n0; } } for (j=n0+1;j<=n;j++) { for (i=1;i<=n0;i++) { a[i][j]=a[i][j-n0]+n0; } } for (j=n0+1;j<=n;j++) { for (i=n0+1;i<=n;i++) { a[i][j]=a[i][j-n0]-n0; } } n0=n; n=n*2; } }