赛程安排的算法

narkissos

算法不是太优,不过应该对.如果还不是联赛的算法,......我就不知道怎么比法了.

int n=20;
int i,j,k;
struct pair{
        int a;
        int b;
};

int compare(struct pair *y, int a, int b)
{
        for (i=0;i<n/2;i++){
                if (y.a==a || y.b==a || y.a==b || y.b==b)
                        return 0;
        }
        return 1;
}

main(){
        int m=n*(n-1)/2;
        struct pair y[n/2], x[m];

        k=0;
        for (i=1;i<=n;i++)
                for (j=i+1;j<=n;j++){
                        x[k].a=i;
                        x[k].b=j;
                        k++;
                }

        for (i=0;i<m;i++){
                k=0;
                for (j=0;j<n/2;j++){
                        y[j].a=0;
                        y[j].b=0;
                }

                j = 0;
                while (j<m){
                        while (j<m && x[j].a==-1) j++;
                        if (j>;=m) break;
                        if (x[j].a!=-1 && compare(y, x[j].a, x[j].b)){
                                y[k].a = x[j].a;
                                y[k].b = x[j].b;
                                printf("%d-%d, ", x[j].a, x[j].b);
                                x[j].a = -1;
                                k++;
                        }
                        j++;
                }
                if (k)        printf("\n";
        }
}

lisp

to narkissos:
我把你的结果贴在下面了（我把你的n改成6）

1. 
   
2. sh-2.05b$ ./c5
   
3. 1-2, 3-4, 5-6,
   
4. 1-3, 2-4,
   
5. 1-4, 2-3,
   
6. 1-5, 2-6,
   
7. 1-6, 2-5,
   
8. 3-5, 4-6,
   
9. 3-6, 4-5,
   

复制代码

下面是我今天上午的结果和实现代码

1. 
   
2. sh-2.05b$ ./c3 6
   
3. A ->; B,C ->; D,E ->; F,
   
4. A ->; C,B ->; D,F ->; E,
   
5. A ->; D,B ->; E,C ->; F,
   
6. A ->; E,B ->; F,D ->; C,
   
7. A ->; F,B ->; C,D ->; E,
   
8. B ->; A,C ->; E,D ->; F,
   
9. C ->; A,D ->; B,
   
10. C ->; B,D ->; A,
    
11. E ->; A,F ->; B,
    
12. E ->; B,F ->; A,

复制代码

1. 
   
2. include <stdio.h>;
   
3. #include <stdlib.h>;
   
4. #define SIZE 100
   
5. void
   
6. resume(char *per,int num)
   
7. {
   
8.     int i;  
   
9. 
   
10.     for(i =0; i < num; i++)
    
11.         per[i] = i + 'A';
    
12. }
    
13. 
    
14. int
    
15. main(int argc,char **argv)
    
16. {
    
17.     int num,i,j,k=0,n=1,m;
    
18.     char flag[SIZE][SIZE];
    
19.     char per[SIZE];
    
20. 
    
21.     num = atoi(argv[1]);
    
22.     for(i = 0; i < num ; i++)
    
23.         flag[i][i] = -1;
    
24.     resume(per,num);
    
25.     while(k < num*(num-1)/(num/2)) {
    
26.         for(i = 0; i<num ;i++) {
    
27.             if (per[i] != -1) {
    
28.                 for(n>;i ? (j=n):(j=i),m=0; (per[i] != -1)&& (m<num); j==num-1 ? (j=0):(j++),m++)
    
29.                     if(flag[i][j] != -1 && per[j] != -1) {
    
30.                         printf("%c ->; %c,",per[i],per[j]);   /*i,j are selected*/
    
31.                         flag[i][j] = -1;
    
32.                         per[i] = per[j] = -1;
    
33.                         (j==num-1) ? (n=0):(n=j+1);
    
34.                         break;  
    
35.                     }      
    
36.             }      
    
37.         }      
    
38.         k++;   
    
39.         n=1;   
    
40.         resume(per,num);
    
41.         printf("\n");
    
42.     }
    
43. }

复制代码

你对比看看吧

narkissos

不过,说真的,我不知道第一行的c->;d和第4行的d->;c有什么区别。

lisp

[quote]原帖由 "narkissos"]不过,说真的,我不知道第一行的c->;d和第4行的d->;c有什么区别。[/quote 发表：

不知道你看不看球，这是主客场的区别
c->;d，可以认为c是主场而d是客场

yuxh

这个问题好象不是想象中的那么简单
写了一个，只对偶数支队有效(奇数为什么不行，还在研究中。。。)，为了简化，只考虑了单循环

1. #include <stdio.h>;
   
2. #include <stdlib.h>;
   
3. #define SIZE 100
   
4. 
   
5. char flag[SIZE][SIZE];
   
6. 
   
7. int getmin(int *node, int num)
   
8. {
   
9.   int i, min;
   
10.   min = 0;
    
11.   while(min  < num && node[min] <= 0) min++;
    
12.   for(i = min+1; i < num; i++)
    
13.     if(node[i] >; 0 && node[i] < node[min]) min = i;
    
14.   return min;
    
15. }
    
16. 
    
17. int getnode(int *node, int num, int i)
    
18. {
    
19.   int j, min;
    
20. 
    
21.   for(min = 0;min < num && (node[min] < 0 || flag[i][min] == -1); min++);
    
22.   for(j = min+1; j < num; j++) {
    
23.     if(j == i) continue;
    
24.     if(node[j] >;= 0 && flag[i][j] != -1 && node[j] < node[min]) min = j;
    
25.   }
    
26.   if(node[min] < 0) return -1;
    
27.   return min;
    
28. }
    
29. 
    
30. int
    
31. main(int argc,char **argv)
    
32. {
    
33.    int num,i,j,k=0,n,t;
    
34.    int  pow[SIZE];
    
35.    int  node[SIZE];
    
36. 
    
37.    num = atoi(argv[1]);
    
38.    for(i = 0; i < num; i++) {
    
39.        pow[i] = num - 1;
    
40.        for(j = 0; j < num; j++)
    
41.            flag[i][j] = 0;
    
42.    }
    
43.    while(k < num*(num-1)/2/(num/2)) {
    
44.      i = 0;
    
45.      for(j = 0; j <  num; j++) {
    
46.        node[j] = pow[j];
    
47.        if(node[j] >; node[i])  i = j;
    
48.      }
    
49.      for(t = 0; t < num/2; t++) {
    
50.        node[i] = -1;
    
51.        for(n = 0; n < num; n++) {
    
52.          if(node[n] < 0) continue;
    
53.          if(flag[i][n] != -1) node[n]--;
    
54.        }
    
55.        j  = getnode(node, num, i);
    
56.        if(j < 0) break;
    
57.        node[j] = -1;
    
58.        for(n = 0; n < num; n++) {
    
59.          if(node[n] < 0) continue;
    
60.          if(flag[n][j] != -1) node[n]--;
    
61.        }
    
62.        flag[i][j] = flag[j][i] = -1;
    
63.        printf("%c ->; %c\n",i + 'A', j + 'A');
    
64.        pow[i]--;pow[j]--;
    
65.        i = getmin(node, num);
    
66.      }
    
67.      k++;
    
68.      printf("\n");
    
69.    }
    
70. }
    

复制代码

JohnBull

在给定场地数量后，排出赛程相对容易，但是你的赛程必须保证公平，不能让某支球队连续征战。

yuxh

在偶数支队的情况下，所有的队都在连续征战，奇数支队的时候，每场有一支队轮空
赛程并不好排，我还无法从数学上找到并证明一个可行的办法。。。
我上面的程序在算法上也是错误的。。。

lisp

to yuxh:
我把你的代码结果贴在下面了，6支球队的，你只排出了5轮比赛，轮次还不够

1. 
   
2. sh-2.05b$ ./a.out 6
   
3. A ->; B
   
4. C ->; D
   
5. E ->; F
   
6. 
   
7. A ->; C
   
8. E ->; B
   
9. D ->; F
   
10. 
    
11. A ->; D
    
12. E ->; C
    
13. B ->; F
    
14. 
    
15. A ->; E
    
16. D ->; B
    
17. C ->; F
    
18. 
    
19. A ->; F
    
20. B ->; C
    
21. D ->; E
    
22. 
    
23. sh-2.05b$
    

复制代码

你再看看吧
to JohnBull:
偶数支球队应该不存在你所说的问题，因为每个球队每轮都必须参赛。但现在贴出的代码都还没有解决偶数个球队的情况

yuxh

我是单循环，不是双循环，所以轮数是
num*(num-1)/2/(num/2)
6支队的时候是6*5/2/3=5轮
双循环的话就是10轮，把以上的结果颠倒重复即可

lisp

原帖由 "yuxh" 发表：
我是单循环，不是双循环，所以轮数是
num*(num-1)/2/(num/2)
6支队的时候是6*5/2/3=5轮
双循环的话就是10轮，把以上的结果颠倒重复即可

哦，这样的话，我上面贴出的代码也解决了偶数的问题，也可以排出奇数个球队的赛程，但会遇到JohnBull所说的球队连续比赛的问题。5个球队的赛程如下：

1. 
   
2. !./c3 5
   
3. A ->; B
   
4. C ->; D
   
5. 
   
6. A ->; C
   
7. B ->; D
   
8. 
   
9. A ->; D
   
10. B ->; E
    
11. 
    
12. A ->; E
    
13. B ->; C
    
14. 
    
15. B ->; A
    
16. C ->; E
    

复制代码