循环赛日程表的递归和非递解

开篇：润墨网以专业的文秘视角，为您筛选了一篇循环赛日程表的递归和非递解范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：介绍了算法设计技术分治法的应用。使用分治法实现了循环赛日程表的递归和非递归解，并作了较为详细的说明，供《算法设计与分析》课程教学参考。

关键词：算法；数据结构；分治法；递归

中图分类号：TP301文献标识码：A文章编号：1009-3044(2008)25-1445-04

The Recursive and Non-recursive Solution for Calendar of Round Robin

WU Xiu-mei, JIANG Jing, WANG Shao-hua, WEN Jing-he

(School of Computer and Information, Shanghai Second Polytechnic University, Shanghai 201209, China)

Abstract: The application of a powerful algorithm design technique is introduced. The name oftechnique is "divide and conquer". The recursive and non-recursive solution for calendar of round robin is given by divide and conquer. The algorithm of solution is more detailed explanation. It can be used for teaching reference.

Key words: algorithm; data structure; divide and conquer; recursive

1 引言

分治法是一种重要的算法设计技术，它可以用来解决各类问题。分治顾名思义就是分而治之，分治法的基本思想是：将问题递归分成若干个子实例（多数情况下是分成2个），分别解决每个子实例，然后把子实例的解组合起来，得到原问题的解，比较典型的应用例子就是“归并排序法”和“快速排序法”。在大多数《算法设计与分析》教课书中，通常将“归并排序法”和“快速排序法”作为讲解分治法的例子[1-3]。然而，“归并排序法”和“快速排序法”早已成为《数据结构》课程的教学内容[4-5]，当然讲解的角度和重点与《算法设计与分析》课程不一样。若在《算法设计与分析》课程中，仍然并且仅仅使用这二个例子来讲解分治法的话，给学生有一种分治法应用实例贫乏的感觉。

实际上分治法不仅可以用来设计算法，而且在其它各方面也有广泛应用。例如，可以用分治法设计电路、构造数学证明、制定循环赛日程表、……等等。在参考文献[1]中，介绍了用分治解决制定循环赛日程表的问题，但算法描述过于简单，程序可理解性并不尽人意。在本文中，对参考文献[1]中的算法实现作了一些修改，对修改后的算法实现作了较为详细的说明。在此基础上，进一步提出了循环赛日程表的递归解，供《算法设计与分析》课程教学参考。

2 问题和算法基本思想

设有n=2k个运动员要进行网球比赛。设计一个满足以下要求的比赛日程表[1-2]：

1) 每个选手必须与其它n-1个选手各赛一次。

2) 每个选手一天只能赛一次。

3) 循环赛一共进行n-1天。

按此要求可将比赛日程表设计成有n行和n-1列的一个表。在表中第i行和第j列处填入第i个选手在第j天所遇到的选手。

设有8个运动员，这样共比赛7天，比赛日程表如下所示：

表1 循环赛日程表（8人）

■

按分治策略，可将所有选手分成二组。n个选手的比赛日程表，可以通过为n/2个选手设计日程表来决定；n/2个选手的比赛日程表，可以通过为n/4个选手设计日程表来决定； …… ；直到为2个选手设计比赛日程表。这样比赛日程表的设计就变得很简单，这时只要让二个选手相互比赛即可，这样形成4组2个选手的比赛日程表。详见表2、表3、表4和表5。

表2 表3 表4 表5

■

我们已经为2个选手的相互比赛设计了比赛日程表，在此基础上为4个选手相互比赛设计比赛日程表。参考表1，将表3抄至表2的右侧，将表2抄至表3的右侧；再将表5抄至表4的右侧，将表4抄至表5的右侧，这样就形成了2组4个选手的比赛日程表。详见表6、表7。

将表2和表3按水平方向 “表2左表3右” 拼接。由于表2中的运动员和表3中的运动员完全不同，拼接后在每一行中不可能存在二个相同号码，即拼接后不会产生一个运动员和另一个运动员比赛二次的情况。将表3和表2按水平方向“表3左表2右”拼接。同理，拼接后也不会产生一个运动员和另一个运动员比赛二次的情况。二次水平拼接后形成表6，让我们以垂直方向观察表6。在左半部分是“表2上表3下”，在右半部分是“表3上表2下”。由于表3中的运动员和表2中的运动员完全不同，在每一列中不可能存在二个相同号码，即拼接后不会产生一个运动员在同一天和不同选手比赛二场的情况。

表6 循环赛日程表（4人） 表6 循环赛日程表（4人）

■

我们已经为4个选手相互比赛设计了比赛日程表，在此基础上为8个选手相互比赛设计比赛日程表。参考表1，将表7抄至表6的右侧，将表6抄至表7的右侧。这样就形成了8个选手的比赛日程表，如表1所示。

3 循环赛日程表的非递归解

3.1 变量说明

1) 变量k

k表示每组运动员人数。假设n=8，k值范围为2、4、8。

2) 变量v

v表示目前处理（被抄）数据的起始行号。假设n=8，v值范围如下所示：

①当k=2时，v值范围为0、2、4、6；

②当k=4时，v值范围为0、4；

③当k=8时，v值为0。

(3) 变量i

i表示目前处理（被抄）数据的相对行号（绝对行号=起始行号+相对行号=v+i）。假设n=8，对应于k值，i值范围如下所示：

①当k=2时，i值范围为1..2。处理右下角时i=1（目标行号= v+i+k/2=v+i+1=v+2），处理右上角时i=2（目标行号=v+i-k/2=v+i-1=v+1） ；

②当k=4时，i值范围为1..4。处理右下角时i=1..2（目标行号= v+i+k/2=v+i+2），处理右上角时i=3..4（目标行号=v+i-k/2=v+i-2）；

③当k=8时，i值范围为1..8。处理右下角时i=1..4（目标行号= v+i+k/2=v+i+4），处理右上角时i=5..8（目标行号= v+i-k/2=v+i-4）。

4) 变量j

j表示目前处理（被抄）数据的列号。假设n=8，j的数值范围如下所示：

①当k=2时，j值为1。目标列号=j+k/2=j+1=2；

②当k=4时，j值范围为1..2。目标列号=j+k/2=j+2；

③当k=8时，j值范围为1..4。目标列号=j+k/2=j+4；

5) 二维数组A

二维数组A用于保存比赛日程表，其规模为n*n，其中n是运动员的人数。第1列按顺序从小到大记录运动员的编号，第2至第7列用以记录比赛对手的号码。

3.2 算法描述

输入：运动员人数n（假定n恰好为2的i次方）