首页 > 代码库 > 分治 赛程安排
分治 赛程安排
问题描述:有n个运动员进行循环赛,要求设计满足一下要求的日程表
1、 每两人必须比赛一次且只比赛一次
2、 每个选手每天只能比赛一次
3、 要求比赛时间尽可能短(即n为偶数时比赛n-1天,n为奇数时比赛n天)
一、分治法
算法思想,先算n/2的日程表,然后将循环赛日程表左上复制到右下,左下复制到右上,得到n的日程表,递归实现
#include <stdio.h>#define N 1000int a[N][N];int b[N]; bool odd(int n){ return n%2;}void copy(int n)//将左上角抄到右下角,将右上角加n/2后抄到左下角,将左下角抄到右上角{ 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];//将右上角加n/2后抄到左下角 a[i+m][j+m]=a[i][j];//将左下角抄到右上角 }}void copyodd(int n) /// n/2为奇数时的复制,让轮空选手与下一个为参赛选手进行比赛{ int m=n/2; int i,j; 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; } }}void makecopy(int n){ if(n/2>1 && odd(n/2)) copyodd(n); else copy(n);}void tour(int n){ if(n==1) { a[1][1]=1; return; } if(odd(n)) { tour(n+1);//当n为奇数,就设置一个虚拟的n+1,然后就有偶数个人了。。。。和一休的那个分马很像啊 return; } tour(n/2); makecopy(n);}void out(int n){ if(n==1) { printf("1\n"); return; } int i,j; int m; if(odd(n)) m=n+1; else m=n; for(i=1; i<=n; ++i) { for(j=1; j<=m; ++j) { if(a[i][j]>n)//当比赛日程是与那位虚拟出来的n+1号选手比赛时,输出0,代表轮空 printf("0 "); else printf("%d ",a[i][j]); } printf("\n"); }}int main(){ int n; while(scanf("%d",&n),n) { tour(n); out(n); } return 0;}
///2、多边形法(我的实现),通过旋转多边形的一种巧妙方法//循环赛日程表#include <stdio.h>#define N 1000int a[N][N];bool odd(int n){ return n & 1;}void init(){ int i; for(i=1; i<=N; ++i) a[i][0]=i; ///for(int i=0;i<N;i++) /// a[i][0]=i;}void tour(int n){ if(odd(n)) tour(n+1); else { int i,j,k; int m=n-1; int p,q; for(i=1; i<=m; ++i) //第一天到第n-1天 { j=i; p=j+1; if(p>m) p=p-m; a[p][i]=n; a[n][i]=p; for(k=0; k<=n/2-2; ++k) { q=j-k; p=j+k+2; if(p>m) p-=m; if(q<=0) q+=m; a[q][i]=p; a[p][i]=q; } } }}void out(int n){ if(n==1) { printf("1\n"); return; } int i,j; int m; if(odd(n)) m=n+1; else m=n; for(i=1; i<=n; ++i) { for(j=0; j<m; ++j) { if(a[i][j]>n) printf("0 "); else printf("%d ",a[i][j]); } printf("\n"); }}int main(){ int n; init(); while(scanf("%d",&n),n) { tour(n); out(n); } return 0;}
输出自己看一下 还有一个输出样式不一样的
#include <iostream>#include <string.h>#include <stdio.h>using namespace std;#define MAX 210int a[MAX][MAX];int main(){ int n; while(scanf("%d", &n) != EOF) { int k; memset(a,0,sizeof(a)); int l=2*n+1; for(int i=1;i<=l;i++) {k=i-1; for(int j=1;j<=i;j++) { if(i!=j) a[i][j]=k++; if(k>l) k=1; a[j][i]=a[i][j]; } } for(int i=1;i<=l;i++) { for(int j=1;j<=l;j++) { printf("%d",a[i][j]); //cout<<a[i][j]; if(j!=l) printf(" "); } printf("\n"); } } return 0;}/*0 1 21 0 32 3 0*/
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。