赛程安排的算法

lisp

晕，写了一个，有bug。大家帮忙看看

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;
    
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.     for(i = 0; i<num; i++)
    
25.         per[i] = i + 'A';
    
26.     while(k < 2*(num-1)) {
    
27.         for(i = 0; i<num ;i++) {
    
28.             if (per[i] != -1) {
    
29.                 for(j = 0; j <num;j++)
    
30.                     if(flag[i][j] != -1 && per[j] != -1) {
    
31.                         printf("%c ->; %c\n",per[i],per[j]);   /*i,j are selected*/
    
32.                         flag[i][j] = -1;
    
33.                         per[i] = per[j] = -1;
    
34.                         break;  
    
35.                     }      
    
36.             }      
    
37.         }      
    
38.         k++;   
    
39.         resume(per,num);
    
40.         printf("\n");
    
41.     }
    
42. }

复制代码

只对2的幂次方球队数正确，如

1. 
   
2. [root@Danny test]# ./a.out 8
   
3. A ->; B
   
4. C ->; D
   
5. E ->; F
   
6. G ->; H
   
7. 
   
8. A ->; C
   
9. B ->; D
   
10. E ->; G
    
11. F ->; H
    
12. 
    
13. A ->; D
    
14. B ->; C
    
15. E ->; H
    
16. F ->; G
    
17. 
    
18. A ->; E
    
19. B ->; F
    
20. C ->; G
    
21. D ->; H
    
22. 
    
23. A ->; F
    
24. B ->; E
    
25. C ->; H
    
26. D ->; G
    
27. 
    
28. A ->; G
    
29. B ->; H
    
30. C ->; E
    
31. D ->; F
    
32. 
    
33. A ->; H
    
34. B ->; G
    
35. C ->; F
    
36. D ->; E
    
37. 
    
38. B ->; A
    
39. D ->; C
    
40. F ->; E
    
41. H ->; G
    
42. 
    
43. C ->; A
    
44. D ->; B
    
45. G ->; E
    
46. H ->; F
    
47. 
    
48. C ->; B
    
49. D ->; A
    
50. G ->; F
    
51. H ->; E
    
52. 
    
53. E ->; A
    
54. F ->; B
    
55. G ->; C
    
56. H ->; D
    
57. 
    
58. E ->; B
    
59. F ->; A
    
60. G ->; D
    
61. H ->; C
    
62. 
    
63. E ->; C
    
64. F ->; D
    
65. G ->; A
    
66. H ->; B
    
67. 
    
68. E ->; D
    
69. F ->; C
    
70. G ->; B
    
71. H ->; A
    

复制代码

对其他的球队数会陷入一种类似死锁的错误，如

1. 
   
2. [root@Danny test]# ./a.out 6
   
3. A ->; B
   
4. C ->; D
   
5. E ->; F
   
6. 
   
7. A ->; C
   
8. B ->; D
   
9. F ->; E
   
10. 
    
11. A ->; D
    
12. B ->; C
    
13. 
    
14. A ->; E
    
15. B ->; F
    
16. D ->; C
    
17. 
    
18. A ->; F
    
19. B ->; E
    
20. 
    
21. B ->; A
    
22. C ->; E
    
23. D ->; F
    
24. 
    
25. C ->; A
    
26. D ->; B
    
27. 
    
28. C ->; B
    
29. D ->; A
    
30. 
    
31. C ->; F
    
32. D ->; E
    
33. 
    
34. E ->; A
    
35. F ->; B
    

复制代码

yuxh

to lisp:
因为比赛进行的轮次并不是2*(num-1)，而是num*(num-1)/(num/2)次(可以证明这是个整数)
所以
要把k < 2*(num-1))
改为k < num*(num-1)/(num/2)

lisp

to yuxh:
2*(num-1)，num*(num-1)/(num/2)是相等的吧

yuxh

num为奇数时不相等的
另外要保证每轮有num/2场比赛，所以原来的算法是有问题的
一个原则：越少参加比赛的队优先安排，你可以再试试。
这几天比较忙，没时间多想。。。

yuxh

...

lisp

多谢yuxh,你说到的越少参加比赛的队优先安排这个思路只有在奇数个球队下需要考虑吧。但我现在的算法连6，10，12，。。。这些情况都处理不了，只能解决4，8，16，。。。这种2的幂次方的球队数的情况。我今天上午抽时间修改了昨天的算法，想要避免上面类似死锁的状况，结果尝试了几种都不行。我现在只能想到出现死锁后用回朔将其解开。
  刚看到这个题的时候感觉很简单，也很快就写出了上面的代码。但没想到现在居然搞成这样，汗。

narkissos

main(){
        int n=6;
        int i,j;
        for (i=1;i<=n;i++)
                for (j=i+1;j<=n;j++)
                        printf("%d-%d\n", i, j);
}

lisp

原帖由 "narkissos" 发表：
main(){
        int n=6;
        int i,j;
        for (i=1;i<=n;i++)
                for (j=i+1;j<=n;j++)
                        printf("%d-%d\n", i, j);
}

大侠，你这个是用来干什么的？

narkissos

不好意思,我看错了,不太知道联赛怎么赛,原来是要日程表.

lisp

[quote]原帖由 "narkissos"]不好意思,我看错了,不太知道联赛怎么赛,原来是要日程表.[/quote 发表：

是的，就是把整个联赛的赛程排出来