循环赛问题,急用,100分,绝对信誉!!!
有n个队伍(1-n),参加比赛,比赛时间不能超过n天,每支队伍每天只能参加一次比赛.每两支队伍之间仅比一次,请设计一个赛程表!
比如和世界杯32强出线以后.............
问题点数：0、回复次数：12Top
1 楼ALNG（?）回复于 2003-11-02 13:35:40 得分 0
//---------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <stdlib.h>
typedef std::vector<unsigned> vec_u;
void make_table(unsigned n, std::vector<vec_u>& table)
{
table.clear();
table.resize(n,vec_u(n,n));
std::vector<vec_u> busy_table(n,vec_u(n,0));
for(unsigned i=0; i<n-1; ++i){ // 行
for(unsigned j=i+1; j<n; ++j){ // 上三角的列
// 看看i和j两队的busy_table中那一天有空闲
unsigned k;
for(k=0; k<n; ++k){
if(busy_table[i][k]==0 && busy_table[j][k]==0){
busy_table[i][k]=1;
busy_table[j][k]=1;
table[i][j] = k; // 两队定在第k天比赛
break;
}
}
if(k==n){
std::cerr<<"没有合法的解"<<std::endl;
exit(1);
}
}
}
}
void print_table(const std::vector<vec_u>& table)
{
unsigned n=table.size();
for(unsigned i=0; i<n; ++i){ // 天
std::cout<<"第"<<i+1<<"天:"<<std::endl;
for(unsigned j=0; j<n-1; ++j) // 行
for(unsigned k=j+1; k<n; ++k) //列
if(table[j][k]==i)
std::cout<<j+1<<"队与"<<k+1<<"队"<<std::endl;
std::cout<<std::endl;
}
}
main()
{
std::vector<vec_u> table;
unsigned n=0;
while(n<2){
std::cout<<"请输入参赛队伍数目:"<<std::endl;
std::cin>>n;
}
make_table(n,table);
print_table(table);
}
Top
2 楼ALNG（?）回复于 2003-11-02 22:45:29 得分 0
上面的贪心构造方法如果得到解，是比较快的。如果得不到解，并不表明没有合法解。
看来是个状态空间搜索问题。用回溯法肯定是可以的。不过复杂度很高。Top
3 楼smilemac（子非魚）回复于 2003-11-02 23:46:15 得分 0
ALNG(?) ,
這是一個邊連通度很高的圖,而且是找到一個點才回溯一步,對於這樣一個圖,複雜度應該比貪心算法高不了太多吧.Top
4 楼plainsong（短歌)(）回复于 2003-11-03 12:33:27 得分 0
我想是不是可以这样：
首先把基数情况用“加一空位”的方法变为偶数情况
1:先生成一个所有的N取2组合的集合。
重复N-1次：
2:在集合中取出N/2个组合，保证取出的组合中不出现重复编号(也自然会包含所有的编号)
3:从集合中删除取出的组合
关键是第二步的实现。第一步可达到平方级的时间复杂度，利用对数级搜索结构，第三步可达到N*log(N)的复杂度。如果第二步复杂度能够不高于第三步，则总的时间复杂度就是N*N*Log(N)。
Top
5 楼plainsong（短歌)(）回复于 2003-11-03 12:38:35 得分 0
此外，现在实际比赛的安排通常都是限制人数用查表法解决的，比较桥牌的“豪威尔移位赛”。
如果限制人数只能是2^k或是2^k-1，就可以用分治法解决，比较简单。如果放宽轮数限制，可以通过增加多个空位的方法简化为2^k的情况。Top
6 楼luolovegui（骆归）回复于 2003-11-03 12:44:09 得分 0
说真的，这种问题我读高二的时候就写出来了。你自己好好想想吧，没有什么好难的。Top
7 楼plainsong（短歌)(）回复于 2003-11-03 12:46:20 得分 0
我在想前面说过的第二步：
集合实现为<no1,no2>的表，分别按no1,no2和<no1,no2>建立索引。
在第二步时复制当前集合(及索引)，然后每次取出第一个元素<a,b>按前两个索引分别删除no1=a和no2=b的元素，直到集合为空。这样第二步的时间复杂度也是N*log(N)(如果索引搜索是Log(N)级)。这样总的时间复杂度就是N*N*log(N).Top
8 楼plainsong（短歌)(）回复于 2003-11-03 23:35:10 得分 0
我想的不对：
由于编号是连续整数，索引可以实现为常数级的，这样时间复杂度就是平方级的了。Top
9 楼间谍（）回复于 2003-11-04 09:37:33 得分 0
那本黄皮的《初等数论》附录里有专门一节课介绍这个的吧。
******以下全部抄袭自此书，大家不要误会，不理解也不要问我，我也不会。********
首先,N支球队进行循环赛时,比赛总场数S=N*(N-1)/2.----------------------A
其次,在每一轮比赛中最多安排的比赛场数:
L=N/2 N为偶数---------------------------------------------------------------------B1
L=(N-1)/2 N为奇数-------------------------------------------------------------------B2
由A,B1,B2可以推出:
当N是偶数时,至少举行N-1轮比赛.
当N是奇数时,至少至行N轮比赛,这时每轮必有一支球队轮空.
同时,可以很方便的统一奇数偶数的不一致性,可以加入第N+1支球队E,并按N+1个队安排比赛程序,每次与E球队比赛的球队都轮空.所以,以下只对N为偶数时做讨论.
用数论中的同余原理解决这个问题,同时还可以证明安排N-1轮比赛就足够了.
首先,对N个球队进行编号: t=1,2,3…,N,在第x轮比赛中t(x)表示与第t队进行比赛的队的编号.问题转化为确定函数t(x),其中1<=x<=N-1.以下就是假设的解决方案:
(A)当t不等于N且
1. 若x为偶数,t不等于x/2……………………………………..(1)
2. 若x为奇数,t不等于(x+N-1)/2………………………………(1)
当符合上述两条件之一,则取t(x)满足:
1.t+t(x)=x(mod N-1)…………………………………………(2)
2.1<=t(x)<=N-1………………………………………………(2)
(B)当
1.x为偶数时,t=x/2…………………………………………...(3)
2.x为奇数时,(x+N-1)/2………………………………………(3)
取t(x)=N.
为证明以上方案,只要证明以下两个命题:
1.在第x(1<=x<=N-1)轮比赛中,按这样的安排,必有t(x)不等于t且不同队t不等于t’的对手也是不同的.
2.每一个确定的队x,在所有这N-1轮比赛中的对手也是不同的,即当x不等于x’时,必有t(x)不等于t(x’).
证明命题1:
当t,t’都不等于N且满足式(1)时,t(x),t’(x)由式(2)确定.
若t(x),t’(x)相等,则由式(4)推出,
t=t’(mod N-1),由此及1<=t,x’<=N-1知t=t’,所以不可能.
若t(x)=t则由式(2)知:
2t=2t(x)=x(mod N-1),由此及N是偶数推出必有式(3)成立,这和式(1)矛盾,所以也不可能.
这里还得出了附带结论,这时t(x)也满足式(1).这就证明了除了t=N以式(3)确定的一个队(显然不等于N)之外,在第x轮比赛中其它的N-1个队恰好两两分组进行比赛.而由(B)知这两个例外的球队恰好分在一组比赛.
命题1证毕.
证明命题2:
先对N支队来证明,若N(x)=N(x’),由(B)知:
N(x)=x/2, x为偶数时.
N(x)=(x+N-1)/2,x为奇数时.
所以2N(x)=x(mod N-1).
故由N(x)=N(x’)推出x=x’(mod N-1),即x=x’.
自此证明了命题2对第N队成立.
当1<=t<=N-1时,若t(x)=t(x’)=N,则由已经证明的第N队在不同轮的比赛中的对手是不同的,就推出了x=x’.
若t(x)=t(x’)且不等于N,由于命题1知式(1)对x=x’,x’’均成立,因此式(2)对x=x’,x’’也成立.所以推出x’=x’’(mod N-1),即x’=x’’.
命题2证毕.
Top
10 楼stephen85（）回复于 2003-11-04 11:26:06 得分 0
分治法Top
11 楼CD2006（小英雄）回复于 2003-11-05 12:36:54 得分 0
建立同余表!!!!
很多书上有详细过程.
这是很经典的解法.
Top
12 楼kelvinJH（kelvin_jh）回复于 2003-11-06 16:04:59 得分 0
/* 楼上的算法真是经典，看来要抽空找本数论来看啊！
程序只讨论了偶数的情况，而且第N队的情况也没写出来。大家有兴趣继续写完吧！
程序在win98,tc下编译通过
*/
#include "stdio.h"
#include "stdlib.h"
#define MAX 10
/* 函数proc中t,x,N如上述含义，返回值即第t队在第x轮比赛的队的编号。*/
int proc(int t,int x,int N);
main(){
int n;
int i,j;
printf("Enter n(1<n<%d,且n为偶数)\n",MAX);
scanf("%d",&n);
if(n%2!=0){
printf("Input error!\n"),;
exit(1);
}
printf(" ");
for(i=1;i<=n-1;i++) printf("%d ",i);
printf("\n");
for(i=1;i<n;i++){
printf("%d ",i);
for(j=1;j<n;j++) printf("%d ",proc(i,j,n));
printf("\n");
}
exit(0);
}
int proc(int t,int x,int N){
if(((x%2==0)&&(x/2!=t))||(x%2!=0)&&((x+N-1)/2!=t))
return ((x-t)%(N-1))==0 ? (N-1):((x-t)%(N-1));
else return N;
}
Top
