求联赛赛程算法
现在我遇到一个算法,就是一个赛季可能有8个队,12个队,或者14队等等,要求每个队两两之间都要打一场比赛。 比如如果8个队,则每个队需要打七场。而且一个队一天只能有一场比赛。
------解决方案--------------------还有如果比赛队伍数为奇数时,每一轮都要有一个队轮空,还有大家的主场数应该是主客场数一致
定义几个数组,然后随机的抽出(队伍数/2)的主队,然后随机分配客队.
下一轮时,都要进行每一队的主队已分配情况查看,如果上一轮是主或者连续两轮以上为主,则不能随机到主队.然后算法基本上就差不多了.
------解决方案--------------------题目:有N队进行循环赛,用程序排出赛程表
分析:循环赛分为单循环与双循环,所谓双循环就是主客场制,那么只需要产生单循环的赛程,REVERSE后就是另一半赛程
N个队二二进行比赛,共要进行C(n,2)场比赛,而每轮能进行n/2赛(此处为c语言里的/,不是数学里的/),所以,一共要进行C(n,2)/(n/2)轮赛事,即当N为偶数时为n-1轮,N为奇数时为n轮。
所以只要能求得N个队的N或N-1组,每组n/2种组合的不同组合就可以了,所以设计一种行之有效的产生方法:
为方便理解,假设有4支队
o x + #
先将其围成一个圈:
o x
# +
得到一组组合((o,#),(x,+))
然后保持o位置不变,旋转其它元素,得到
o #
+ x
得到组合((o,+),(#,x))
继续如上步聚,得到((o,x),(+,#))
得到了三组需要的结果,此方法可推广至N队。
================================
实现代码:
/*termplay.c
*programm by ETSG(BIRDIC,CELLAR),2000-2005
*N队单循环赛赛程安排的程序
*注:程序是将各队排号,使用时可将其用实际队名替换,
*如队数为奇数,则与不存在的队比赛的队轮空
*感谢远在加拿大的组员BIRDIC提供算法
*/
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int i,j,tmp,k,arrsiz;
if(argc!=2){
printf( "uses:%s num ",argv[0]);
exit(1);
}
arrsiz=atoi(argv[1]);
arrsiz=arrsiz%2?arrsiz+1:arrsiz;
int *arr=malloc(sizeof(int)*arrsiz);
for(i=0;i <arrsiz;i++)
arr[i]=i;
for(i=1;i <arrsiz;i++){
printf( "------------BEGIN OF ROUND %d------------\n ",i);
tmp=arr[arrsiz-1];
for(j=arrsiz-1;j> 1;j--)
arr[j]=arr[j-1];
arr[1]=tmp;
for(k=0;k <arrsiz/2;k++)
printf( "%d vs %d\t ",arr[k],arr[arrsiz-1-k]);
printf( "\n------------END OF ROUND %d------------\n ",i);
}
free(arr);
return 0;
}
------解决方案--------------------轮盘算法
比较简单的,也是目前采用最多的
KimmKing已经讲了怎么做了