问题2的求解

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《问题2的求解》，欢迎阅读！

问题2的求解：

考虑到各队每两场比赛中间都至少相隔一场时让赛程尽可能公平的情况下，求每两场比赛中间相隔的场次数的上限。题目要求我们安排N支球队的单循环赛程, 并使赛程对各队来说尽量做到公平.要想做到公平, 其衡量的指标之一是: 考虑各队每两场比赛之间得到的休整时间是否均等、或是差距不大.为此, 采用“逆时针轮转法”，首先我们将参加比赛的球队由编号分别为字母A、B、C、D„分别用数字1、2、3、4、„„等代替表示，然后固定第1队, 按左边由上而下、右边由下而上(即逆时针转动)排成完整的两列.

为了确定比赛顺序,要先将比赛场次的顺序按轮转法排出. 经过我们的研究和推测,奇数会出现轮空的情况，偶数则不会，所以要分奇偶讨论(当N=<4时，各队的每两场比赛中间相隔的场次数的上限为0，在此不予讨论。)：

(1)

当N为偶数时,各队每两场比赛之间相隔的场次数的上限分析如下:

①当N= 6时,根据附录中的程序算出总共的比赛次数为15场，如

下图所示：

6个参赛队的单循环赛比赛场次顺序轮转表

第一轮 1-----2 3-----4 6-----5

第二轮 1----3 6----2 5----4

第三轮 1----6 5----3 4----2

第四轮 1----5 4----6 2----3

赛程与相隔场次数表

1 2 3 4 5 6

1 X 13 10 3 4 1

2 13 X 6 11 2 9

3 10 6 X 3 8 14

4 7 11 3 X 15 5

5 4 2 8 15 X 12

6 1 9 14 5 12 X

每两场比赛间隔场次数 2，2，2，2 3，2，1，1 2，1，1，3 1，1，3，3 1，3，3，2 3，3，2，1

第五轮 1-----4 2-----5 3-----6

由此表可得当N=6时，各队每两场比赛中间相隔的场次数的上限为1.由此我们通过编程得出当N=8，10，„„2n等偶数时重复当N=6时的算法并计算他们的上限。得出参赛对数N与队每两场比赛中间相隔的场次数的上限M的关系如下表： 参赛对

6

8

10

12

„

50

„


数N 上限M



1 2 3 4 „ 23 „

因此,由上述图表可推测得出规律:当N为偶数时, 各队每两场比赛之间相隔的场次数的上限为:（N/2）-2场。当N=100时，经过编程得出各队每两场比赛中间相隔的场次数的上限为48 ，经由我们推导出来的公式计算得当N=100时，各队每两场比赛中间相隔的场次数的上限也为48 ，由此便可验证公式的正确性。

（2）当N为奇数时各队每两场比赛之间相隔的场次数的上限分析如下： ①当N= 5时,根据附录中的程序算出总共的比赛次数为10场，如

下图所示： 第一轮 1-5 2-4 3-0

表2、五个队伍比赛间隔场次表 第二轮 1-0 5-2 4-3

第三轮 2-1 3-5 4-0

第四轮 2-0 1-3 5-4

第五轮 3-2 4-1 5-0



A B C

A X 1 6

B 1 X 4 7

C 6 4 X 2

D E 9 7 2 X 5

3 10 8 5 X

每两场比赛间相隔场次数

1, 2, 2 2, 2 ,2 1, 1, 1 2, 1, 1 1, 2, 1

D 9 E

3

10 8

由此表可得当N=5时，各队每两场比赛中间相隔的场次数的上限为1.由此我们通过编程得出当N=7，19，„„2n+1等奇数时重复当N=5时的算法并计算他们的上限。得出参赛对数N与队每两场比赛中间相隔的场次数的上限M的关系如下表： 参赛对数N 上限M

5 1

7 2

9 3

11 4

„ „

49 23

„ „

本文来源：https://www.wddqxz.cn/5b96b6f17c1cfad6195fa780.html