篮球分组问题讨论

1 问题概述

问题：有5支球队在同一块场地上进行单循环赛,共要进行10场比赛。下表是一个赛程安排，有些队觉得不公平。研究以下问题

	A	B	C	D	E	每两场比赛间相隔场次数
A	X	1	9	3	6	1, 2, 2
B	1	X	2	5	8	0, 2, 2
C	9	2	X	7	10	4, 1, 0
D	3	5	7	X	4	0, 0, 1
E	6	8	10	4	X	1, 1, 1

然后我们不难看到左边的数字有的人比赛1场之后休息一场，但是有的球队是比赛1场之后就休息4场，这明显很不公平，接下来我们要研究的是，我们要怎么进行分配才可以最合适

比赛5场 只可以有1，2间隔场次
比赛6场 只可以有1，2，3间隔场次
比赛7场 只可以有2，3间隔场次
比赛8场 只可以有2，3，4间隔场次......依次类推

---

我们先来想想思路
我们要去解决一个实际问题，而不是一个数学游戏，所以我们要按照实际情况去考虑

一开始我的思路是观察对角线等的规律在做这一道题目，这就是错误的思路，因为我们是解决实际问题，而不是去做数字游戏，所以我们要按照场次进行分配，就是分配给该给的组别

当我们在排场次的时候，我们排完1之后，由于我们是5场，间隔是要为1，2的，所以不可以再把2排到第一行和第二行了

要把2放到第二行的下面

然后我们只需要根据这个思路进行编程就好了

2 代码思路

代码示例

global mymap found n;
mymap = zeros(20,20);
found = false;function printf()global mymap nfor i = 1:nfor j = 1:nif i == jfprintf('X\t');elsefprintf('%d\t', mymap(i,j));endendfprintf('\n');end
endfunction valid = isvalue(idx, m, w)global mymap nmatches = [];for j = 1:nif idx ~= j && mymap(idx, j) > 0matches = [matches, mymap(idx, j)];endendif length(matches) < 2valid = true;return;endmatches = sort(matches);for i = 1:length(matches)-1diff = matches(i+1) - matches(i) - 1;if diff ~= m && diff ~= wvalid = false;return;endendvalid = true;
endfunction fillMap(m, w, current)global mymap found n;if foundreturn;end% 如果所有比赛都安排完毕，打印结果并返回if current > (n * (n - 1)) / 2found = true;printf();return;end% 计算当前各队伍的最大比赛编号currentmax = max(mymap, [], 2);% 优先尝试与 currentmax 相关的队伍for i = 1:n% 如果 currentmax(i) 不为 0，检查间隔是否合法if currentmax(i) > 0interval = current - currentmax(i) - 1;if interval ~= m && interval ~= wcontinue;  % 不合法，跳过endend% 遍历所有可能的对手 jfor j = i+1:nif mymap(i,j) == 0  % 如果这个位置还没填% 尝试填入 currentmymap(i,j) = current;mymap(j,i) = current;% 检查是否满足约束if isvalue(i, m, w) && isvalue(j, m, w)fillMap(m, w, current + 1);  % 递归填下一个数end% 如果找到解，直接返回if foundreturn;end% 否则回溯，恢复 mymapmymap(i,j) = 0;mymap(j,i) = 0;endendend
end% 主程序
n = input('篮球队伍的个数: ');
m = input('间隔1: ');
w = input('间隔2: ');mymap = zeros(n,n);
for i = 1:nmymap(i,i) = -1;
endfillMap(m,w,1);

代码1

function printf()global mymap nfor i = 1:nfor j = 1:nif i == jfprintf('X\t');elsefprintf('%d\t', mymap(i,j));endendfprintf('\n');end
end

这个是打印函数
就是我们按照我们表格那种进行打印这个球队的分组
然后利用fprintf进行格式化处理，如果用dist的话用不了'\t'，这样就格式化不了了
这个函数十分的简单，就是简答的for循环而已

代码2

function valid = isvalue(idx, m, w)global mymap nmatches = [];for j = 1:nif idx ~= j && mymap(idx, j) > 0matches = [matches, mymap(idx, j)];endendif length(matches) < 2valid = true;return;endmatches = sort(matches);for i = 1:length(matches)-1diff = matches(i+1) - matches(i) - 1;if diff ~= m && diff ~= wvalid = false;return;endendvalid = true;
end

这个是检查函数，就是判断是否满足我们的间隔为
首先我们声明一下这两个全局变量，然后就是不断地把这个元素放到一个数组里面，然后进行排序，然后不断地进行相减得到之间地间隔，然后就进行判断就可以了，只要有一个不过，那么后面的就直接return

代码3

function fillMap(m, w, current)global mymap found n;if foundreturn;end% 如果所有比赛都安排完毕，打印结果并返回if current > (n * (n - 1)) / 2found = true;printf();return;end% 计算当前各队伍的最大比赛编号currentmax = max(mymap, [], 2);% 优先尝试与 currentmax 相关的队伍for i = 1:n% 如果 currentmax(i) 不为 0，检查间隔是否合法if currentmax(i) > 0interval = current - currentmax(i) - 1;if interval ~= m && interval ~= wcontinue;  % 不合法，跳过endend% 遍历所有可能的对手 jfor j = i+1:nif mymap(i,j) == 0  % 如果这个位置还没填% 尝试填入 currentmymap(i,j) = current;mymap(j,i) = current;% 检查是否满足约束if isvalue(i, m, w) && isvalue(j, m, w)fillMap(m, w, current + 1);  % 递归填下一个数end% 如果找到解，直接返回if foundreturn;end% 否则回溯，恢复 mymapmymap(i,j) = 0;mymap(j,i) = 0;endendend
end

% 如果所有比赛都安排完毕，打印结果并返回if current > (n * (n - 1)) / 2found = true;printf();return;end

这个上面的公式是怎么推算出来的呢？

我们来看这个五角星的部分，1+2+3+4，这就是一个典型的等差数列，然后我们只需要用等差数列的求和公式就可以计算出这个结果是多少，然后就得出了这个公式，n代表的是有几个队伍

1. 参数情况：

• • 第一个参数mymap代表输入的矩阵。
  • 第二个参数[]是 MATLAB 里的惯用写法，意思是不进行比较操作。
  • 第三个参数2表明按行方向（也就是按列）来计算最大值。

我们获取每一个队伍的最大值之后，就进行循环，因为我们可以根据间隔来进行填数字了

然后我们就进行判断

 if currentmax(i) > 0interval = current - currentmax(i) - 1;if interval ~= m && interval ~= wcontinue;  % 不合法，跳过endend

这个是判断这个如果放入这个数字之后，在当前队伍的间隔满不满足，然后不合法的就直接跳过

 % 遍历所有可能的对手 jfor j = i+1:nif mymap(i,j) == 0  % 如果这个位置还没填% 尝试填入 currentmymap(i,j) = current;mymap(j,i) = current;% 检查是否满足约束if isvalue(i, m, w) && isvalue(j, m, w)fillMap(m, w, current + 1);  % 递归填下一个数end% 如果找到解，直接返回if foundreturn;end% 否则回溯，恢复 mymapmymap(i,j) = 0;mymap(j,i) = 0;endendend

然后我们再继续遍历每一个对手把当前按值填到对应的map里面，然后判断是否满足约束条件，然后满足就递归到下一个，没有就回溯