[讨论]悬赏千金求一算法二--联赛问题 - C语言论坛

myajax95

等　级：版主
威　望：30
帖　子：2978
专家分：0
注　册：2006-3-5

楼主

问题点数：0 回复次数：12

[讨论]悬赏千金求一算法二--联赛问题

有N支球队(N>=4 && N<=30)，名字分别为T1，T2，T3。。。TN-1，TN。在联赛中进行单循环比赛。(任何两支球队交手一次，每轮共(int)N/2场比赛)
请列出一个可行的赛程表。要求程序在正常的机器上5秒中之内算的出来。

搜索更多相关主题的帖子: 算法　千金　联赛　悬赏　

2006-06-05 00:04

myajax95

等　级：版主
威　望：30
帖　子：2978
专家分：0
注　册：2006-3-5

第 3 楼

得分:0

随便一个可行的就行。不用穷举，如果不需要的话。

http://myajax95./

2006-06-05 01:03

myajax95

等　级：版主
威　望：30
帖　子：2978
专家分：0
注　册：2006-3-5

第 5 楼

得分:0

以下是引用–★–在2006-6-5 12:54:00的发言：
//以下代码存在最大的缺陷是
//不能让比赛在最短天数结束
#include<stdio.h>
#define N 8 //队伍数,12效果尚可
main( )
{
static char b[N][N][2];
int i,j,k,n,flag;
for(k=0; ;k++)
{
flag=0;
for(i=0;i<N-1;i++)
for(j=i+1;j<N;j++)
if(b[i][j][0]==0)
if(b[i][j][1]==k)
{ b[i][j][0]=1;
if(!flag){flag=1;
printf("\n第%d天的赛事安排:\n",k+1);}
printf("%d:%d ",i+1,j+1);
for(n=0;n<N;n++)b[i][n][1]=k+1;
for(n=0;n<N;n++)b[j][n][1]=k+1;
for(n=0;n<N;n++)b[n][i][1]=k+1;
for(n=0;n<N;n++)b[n][j][1]=k+1;
}
if(flag==0)break;
}
printf("\n\n");
}

N=10的怎么改？

http://myajax95./

2006-06-05 12:58

myajax95

等　级：版主
威　望：30
帖　子：2978
专家分：0
注　册：2006-3-5

第 7 楼

得分:0

感觉下面这个算法应该比较完全了，看看有没有bug，27个队的联赛赛程为：
round 1
T00vsT01 T02vsT03 T04vsT05 T06vsT13 T07vsT08 T09vsT10 T11vsT12 T14vsT15 T16vsT17 T18vsT19 T21vsT22 T23vsT24 T25vsT26
round 2
T00vsT02 T01vsT03 T04vsT06 T05vsT12 T07vsT09 T08vsT10 T11vsT13 T14vsT16 T15vsT17 T18vsT20 T19vsT26 T21vsT23 T22vsT24
round 3
T00vsT03 T01vsT02 T04vsT11 T05vsT06 T07vsT10 T08vsT09 T12vsT13 T14vsT17 T15vsT16 T18vsT25 T19vsT20 T21vsT24 T22vsT23
round 4
T00vsT04 T01vsT05 T02vsT06 T03vsT10 T07vsT11 T08vsT12 T09vsT13 T14vsT18 T15vsT19 T16vsT20 T17vsT24 T21vsT25 T22vsT26
round 5
T00vsT05 T01vsT06 T02vsT09 T03vsT04 T07vsT12 T08vsT13 T10vsT11 T14vsT19 T15vsT20 T16vsT23 T17vsT18 T21vsT26 T24vsT25
round 6
T00vsT06 T01vsT08 T02vsT04 T03vsT05 T07vsT13 T09vsT11 T10vsT12 T14vsT20 T15vsT22 T16vsT18 T17vsT19 T23vsT25 T24vsT26
round 7
T00vsT07 T01vsT04 T02vsT05 T03vsT06 T08vsT11 T09vsT12 T10vsT13 T14vsT21 T15vsT18 T16vsT19 T17vsT20 T22vsT25 T23vsT26
round 8
T00vsT08 T01vsT09 T02vsT10 T03vsT11 T04vsT12 T05vsT13 T06vsT07 T14vsT22 T15vsT23 T16vsT24 T17vsT25 T18vsT26 T20vsT21
round 9
T00vsT09 T01vsT10 T02vsT11 T03vsT12 T04vsT13 T05vsT07 T06vsT08 T14vsT23 T15vsT24 T16vsT25 T17vsT26 T19vsT21 T20vsT22
round 10
T00vsT10 T01vsT11 T02vsT12 T03vsT13 T04vsT07 T05vsT08 T06vsT09 T14vsT24 T15vsT25 T16vsT26 T18vsT21 T19vsT22 T20vsT23
round 11
T00vsT11 T01vsT12 T02vsT13 T03vsT07 T04vsT08 T05vsT09 T06vsT10 T14vsT25 T15vsT26 T17vsT21 T18vsT22 T19vsT23 T20vsT24
round 12
T00vsT12 T01vsT13 T02vsT07 T03vsT08 T04vsT09 T05vsT10 T06vsT11 T14vsT26 T16vsT21 T17vsT22 T18vsT23 T19vsT24 T20vsT25
round 13
T00vsT13 T01vsT07 T02vsT08 T03vsT09 T04vsT10 T05vsT11 T06vsT12 T15vsT21 T16vsT22 T17vsT23 T18vsT24 T19vsT25 T20vsT26
round 14
T00vsT14 T01vsT15 T02vsT16 T03vsT17 T04vsT18 T05vsT19 T06vsT20 T07vsT21 T08vsT22 T09vsT23 T10vsT24 T11vsT25 T12vsT26
round 15
T00vsT15 T01vsT16 T02vsT17 T03vsT18 T04vsT19 T05vsT20 T06vsT21 T07vsT22 T08vsT23 T09vsT24 T10vsT25 T11vsT26 T13vsT14
round 16
T00vsT16 T01vsT17 T02vsT18 T03vsT19 T04vsT20 T05vsT21 T06vsT22 T07vsT23 T08vsT24 T09vsT25 T10vsT26 T12vsT14 T13vsT15
round 17
T00vsT17 T01vsT18 T02vsT19 T03vsT20 T04vsT21 T05vsT22 T06vsT23 T07vsT24 T08vsT25 T09vsT26 T11vsT14 T12vsT15 T13vsT16
round 18
T00vsT18 T01vsT19 T02vsT20 T03vsT21 T04vsT22 T05vsT23 T06vsT24 T07vsT25 T08vsT26 T10vsT14 T11vsT15 T12vsT16 T13vsT17
round 19
T00vsT19 T01vsT20 T02vsT21 T03vsT22 T04vsT23 T05vsT24 T06vsT25 T07vsT26 T09vsT14 T10vsT15 T11vsT16 T12vsT17 T13vsT18
round 20
T00vsT20 T01vsT21 T02vsT22 T03vsT23 T04vsT24 T05vsT25 T06vsT26 T08vsT14 T09vsT15 T10vsT16 T11vsT17 T12vsT18 T13vsT19
round 21
T00vsT21 T01vsT22 T02vsT23 T03vsT24 T04vsT25 T05vsT26 T07vsT14 T08vsT15 T09vsT16 T10vsT17 T11vsT18 T12vsT19 T13vsT20
round 22
T00vsT22 T01vsT23 T02vsT24 T03vsT25 T04vsT26 T06vsT14 T07vsT15 T08vsT16 T09vsT17 T10vsT18 T11vsT19 T12vsT20 T13vsT21
round 23
T00vsT23 T01vsT24 T02vsT25 T03vsT26 T05vsT14 T06vsT15 T07vsT16 T08vsT17 T09vsT18 T10vsT19 T11vsT20 T12vsT21 T13vsT22
round 24
T00vsT24 T01vsT25 T02vsT26 T04vsT14 T05vsT15 T06vsT16 T07vsT17 T08vsT18 T09vsT19 T10vsT20 T11vsT21 T12vsT22 T13vsT23
round 25
T00vsT25 T01vsT26 T03vsT14 T04vsT15 T05vsT16 T06vsT17 T07vsT18 T08vsT19 T09vsT20 T10vsT21 T11vsT22 T12vsT23 T13vsT24
round 26
T00vsT26 T02vsT14 T03vsT15 T04vsT16 T05vsT17 T06vsT18 T07vsT19 T08vsT20 T09vsT21 T10vsT22 T11vsT23 T12vsT24 T13vsT25
round 27
T01vsT14 T02vsT15 T03vsT16 T04vsT17 T05vsT18 T06vsT19 T07vsT20 T08vsT21 T09vsT22 T10vsT23 T11vsT24 T12vsT25 T13vsT26

程序代码：


const int intTeamNumber = 27;
void FillMatrix(int intSchedule[][intTeamNumber], int intCurrentNumber);
void FillRemainingMatrix(int intSchedule[][intTeamNumber], int intCurrentNumber);
int main(int argc, char* argv[])
{
int intRound, intCount1, intCount2, intTotalRound;
int intSchedule[intTeamNumber][intTeamNumber] = {0};
for (intCount1 = 0; intCount1 < intTeamNumber; intCount1++)
  intSchedule[intCount1][intCount1] = -1;
FillMatrix(intSchedule, intTeamNumber);
intTotalRound = intTeamNumber%2 ? intTeamNumber : intTeamNumber-1;
for (intRound = 1; intRound <= intTotalRound; intRound++)
{
  for (intCount1 = 0; intCount1 < intTeamNumber; intCount1 ++)
  {
   for (intCount2 = intCount1+1; intCount2 < intTeamNumber; intCount2 ++)
    if (intSchedule[intCount1][intCount2] == intRound)
     printf(\"T%02d vs T%02d       \", intCount1, intCount2);
  }
  printf(\"\n\");
}
return 0;
}
void FillMatrix(int intSchedule[][intTeamNumber], int intCurrentNumber)
{
int intLocalSchedule[intTeamNumber][intTeamNumber] = {0};
int intCount1, intCount2, intNextNumber = (intCurrentNumber+1)/2;
if (intCurrentNumber > 2)
{
  FillMatrix(intLocalSchedule, intNextNumber);
  for (intCount1 = 0; intCount1 < intNextNumber; intCount1++)
  {
   for (intCount2 = intCount1+1; intCount2 < intNextNumber; intCount2++)
   {
    intSchedule[intCount1][intCount2] = intLocalSchedule[intCount1][intCount2];
    if (intCount2+intNextNumber < intCurrentNumber)
     intSchedule[intCount1+intNextNumber][intCount2+intNextNumber] = intLocalSchedule[intCount1][intCount2];
   }
  }
  FillRemainingMatrix(intSchedule, intCurrentNumber);
}
else
  intSchedule[0][1]=1;
}
void FillRemainingMatrix(int intSchedule[][intTeamNumber], int intCurrentNumber)
{
int intCount1, intCount2, intRound, intNextNumber = (intCurrentNumber+1)/2;
bool bMissRound;
for (intCount1 = 0; intCount1 < intNextNumber; intCount1++)
{
  if (intNextNumber > 2 && intNextNumber % 2)
  {
   for (intRound = 1; intRound < intNextNumber+1; intRound++)
   {
    bMissRound = true;
    for (intCount2 = 0; intCount2 < intNextNumber && bMissRound; intCount2++)
    {
     if (intSchedule[intCount1][intCount2] == intRound || intSchedule[intCount2][intCount1] == intRound)
      bMissRound = false;
    }
    if (bMissRound)
    {
     intSchedule[intCount1][intCount1+intNextNumber] = intRound;
     break;
    }
   }
  }
  else if (intCount1 + intNextNumber < intCurrentNumber)
   intSchedule[intCount1][intCount1+intNextNumber] = intNextNumber;
}
for (intRound = intNextNumber+1; intRound < (intNextNumber*2); intRound++)
{
  for (intCount1 = 0; intCount1 < intNextNumber; intCount1++)
  {
   if (intCurrentNumber % 2 && intCount1+intRound == intCurrentNumber)
    continue;
   if (intCount1 + intRound < intNextNumber * 2)
    intSchedule[intCount1][intCount1+intRound] = intRound;
   else
    intSchedule[intCount1][intCount1+intRound-intNextNumber] = intRound;
  }
}
}

[此贴子已经被作者于2006-6-6 7:40:36编辑过]

http://myajax95./

2006-06-05 15:03

myajax95

等　级：版主
威　望：30
帖　子：2978
专家分：0
注　册：2006-3-5

第 9 楼

得分:0

24楼的方法已经差不多了，就是不能保证最短时间内完成比赛，也就是每轮有N/2场比赛。加入以下判断应该就可以了：
1。如果是2或2的幂次当然就搞定了。
2。如果不是，那么作如下递归：例如是27个队：27个队的赛程和28个队一样，除了有一支球队轮空，就是和NULL比赛。所以处理28支队的情况。28支队分成两组，每组14支，组内先循环，然后两组打1对1对抗填满剩下的。那么问题就变成了14个队的联赛。继续递归分两组，每组7支队，7支队和8支队的赛程一样，8是2的幂次，那么8支队就搞定了，于是7支队就搞定了。推回去就搞定了。

http://myajax95./

2006-06-06 03:08