分
治法
的
应
用
——
网
球
循
环
赛
2018211302
班
2018210074
熊
宇
指导教师：王晓茹
2020年10月22日
一、问题描述
二、问题分析
1.暴力算法
(1)外循环遍历每一个选手，然后内循环遍历每一天；
(2)记录每一个选手已经比过的选手，然后分配给他没有比过的选手，同时在对手那里也
要进行相应记录。
2.分治法
(1)基于分治法“分而治之”的思想，我们先算出n/2的结果，然后将其合并，得出n的结
果；
(2)我们设置数组APPi表示i号选手在第j天所要对战的选手；
(3)假设halfN=n/2是偶数。这时我们的已知是前halfN个选手在前dayOfPast天的对战情
况。我们这样进行构造
a.先根据前halfN个选手在前dayOfPast天的对战情况来构造后halfN个选手在前
dayOfPast天的对战情况。我们想一下，在n=2的时候，很简单让1号和2号打，2号
和1号打，一天完成。所以只要采取递增的构造方式，对于我们理解起来更简单
些。因此我们让后halfN个选手在前dayOfPast天的对战情况与前halfN个选手在前
dayOfPast天的对战情况形成一种联系。也就是说：第i+halfN号选手的对手是同一
天第i号的对战选手+halfN号选手，即——APP[i+halfN] [j]=APP[i] [j]+halfN。
这样我们就让前dayOfPast天所有队员都有了不冲突的对战选手。
b.因为选手们一共比赛dayOfRace天，下面我们进行n个选手在后(dayOfRace-
dayOfPast)天的对战情况，这里我们需要知道，每当我们确定i号选手在第j天的对
战选手是APP[i] [j]号，那么APP[i] [j]号选手在第j天的对战选手也就是APP[APP[i]
[j]] [j]就要等于i（a部分没有提及是因为如果n/2满足了此条件，都是递增形成自然
也就满足该条件）。
同样，为了保证同一天的不重复，我们同样采用增量构造；此外，为了让每一个选
手都和其他每一位选手都赛一场，我们设置count增量，每构造好一天，就让他
+1。也就是
(4)假设halfN是奇数。因为我们仍然是按照偶数进行构造，所以其实，我们多加了一
列，所以我们如果构造出了与halfN+1列的选手进行对决，要将其置0（就是说这一天没
有比赛），并且将多余的第halfN+1列删去。
因为每次构造都涉及到根据前halfN个选手在前dayOfPast天的对战情况来构造后halfN
个选手在前dayOfPast天的对战情况，如果我们遇到了APP[i] [j]=0（没有比赛），我们
就直接让i和i+halfN比赛，也就是说
但
是
！！！
这样做会导致一个新的问题：那就是在根据前halfN个选手在前dayOfPast天
的对战情况来构造后halfN个选手在前dayOfPast天的对战情况之后，我们要进行n个选
手在后(dayOfRace-dayOfPast)天的对战情况，这个时候由于之前在APP[i] [j]=0的位置填
入了i+halfN，我们可能会重复构造APP[1] [dayOfPast]，所以如果是奇数，我们标记一
下oddFlag，然后将oddFlag加入增量构造，使得APP[1] [j]与APP[1] [j+1]不重复，那么
后面由于增量构造必不可能重复。也就是说：
这样我们就构造完成啦！！
三、实验源代码
1.暴力算法
2.分治法
(1)C++
(2)Qt
main.cpp
mainwindow.h
mainwindow.cpp
result.h
result.cpp
评论0