使用分治策略递归和非递归和递推算法解决循环赛日程表课程设计报告
补水保湿排行榜-
《算法设计与分析》
课程设计报告
题
目：
院
（系
）
：
专业班级：
学生姓名：
学
号：
指导教师：
2018
年
1
月
循环赛日程表
信息科学与工程学院
软工
日至
2018
年
1
月
19
8
日
算法设计与分析
课程设计任务书
一、设计题目
循环赛日程表
问题描述：
设有
n=2
k
个运动员要
进行网球循环赛。
现要设计一个满足一下要求的比
赛日程表。<
/p>
(1)
每个
选手必须与其他
n-1
个选手各赛一次。
(2)
每个选手一天只能参赛一次。
(3)
循环赛在
n-1
天内结束。
请按此要求将
比赛日程表设计成有
n
行和
n-1
列的一个表格。在表中的第
i
行，第
j
列处填入第
i
个选
手在第
j
天所遇到的选手，其中
1
≤
i
≤
n
，
1
≤
j
≤
n-1
。
例如：当
n=4
时，其比赛日程表如下：
1
2 3 (
天
)
1
2
3
4
<
/p>
当
n=8
时，其比赛日程表如下：
1 2
3 4 5 6 7
（天）
1
2
3
4
5
6
7
8
二、设计主要内容
具体要求如下：
(1)
使用分治策略递归算法实现。
(2)
使用分治策略非递归算法实现。
2
1
4
3
3
4
1
2
4
3
2
1
2
1
4
3
6
5
8
7
3
4
1
2
7
8
5
6
4
3
2
1
8
7
6
5
5
6
7
8
1
2
3
4
6
5
8
7
2
1
4
3
7
8
5
6
3
4
1
2
8
7
6
5
4
3
2
1
(3)
使用递推算法实现。
(4)
对各种算法的时间复杂度进行分析和比较。
(5)
设计出相应的菜单，通过菜单的选择实现各个功能
三、原始资料
无
四、要求的设计成果
(1)
实现该系统功能的程序代码
(2)
撰写符合规范要求的课程设计报告
五、进程安排
序号
1
2
3
4
5
分析与设计
模块实现
课程设计内容
选题与搜集资料
学时分配
1
天
1
天
4
天
2
天
2
天
备注
系统调试与测试
撰写课程设计报告
合计
10
天
六、主要参考资料
[1]
吕国英．算法设计与分析．第
2
版．北京：清华
大学出版社，
2011
．
[2]
王晓东．算法设计与分析．
北京，清华大学出版社，
2009
．<
/p>
[3]
徐士良．计算机常用算法．第
2
版．北京，清华大学出版社出版，
2
010
．
指导教师（签名）
：
20
年
月
日
目
录
1
常用算法
.
.....................................
..................................................
..................................................
.... 1
1.1
分治算法
.
....................................
..................................................
................................................
1
基本概念
:
.................................................
..................................................
.........................................
1
1.2
递推算法
.
....................................
..................................................
................................................
2
2
问题分析及算法设计
..................
..................................................
..................................................
.... 5
2.1
分治策略递归算法的设计
.
.............................
..................................................
............................ 5
2.2
分治策略非递归算法的设计
..................................................
..................................................
... 7
2.3
递推策略算法的设计
.
.............................................
..................................................
................... 8
3
算法实现
.
..................................................
..................................................
.........................................
9
3.1
分治策略递归算法的实现
.
.............................
..................................................
............................ 9
3.2
分治策略非递归算法的实现
..................................................
..................................................
. 10
3.3
递推策略算法的实现
.
.............................................
..................................................
................. 12
4
测试和分析
.
.................................................
..................................................
.................................... 15
4.1
分治策略递归算法测试
.
..............................
..................................................
............................. 15
4.2
分治策略递归算法时间复杂度的分析
.
..............................
..................................................
...... 16
4.3
分治策略非递归算法测试
................
..................................................
.......................................
16
4.4
分治策略非递归算法时间
复杂度的分析
.
.........
..................................................
....................... 17
时间复杂度为：
O(5^(n-1))
.
...........................
..................................................
............................... 17
4.5
递推策略算法测试
....
..................................................
..................................................
............ 17
4.6
递推策略算法时间复杂度的分析
.............
..................................................
.............................. 18
时间复杂度为：
O(5^(n-1))
.
...........................
..................................................
............................... 18
4.7
三种算法的比较
.....
..................................................
..................................................
............... 18
5
总结
.........................
..................................................
..................................................
...................... 19
参考文献
.......................
..................................................
..................................................
.................... 20
1
常用算法
1.1
分治算法
基本概念
:
< br>在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”
，就
是
把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问
题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧
是很多高效算法的基础，如排序算法
(
快速排序，归并排序
)
，傅立叶变换
(
快速傅立叶变
换
)
……
任何一个可以用
计算机求解的问题所需的计算时间都与其规模有关。问题的规模越
小，越容易直接求解，
解题所需的计算时间也越少。例如，对于
n
个元素的排序问题，
当
n=1
时，
不需任何计算。
n=2
时，
只要作一次比较即可排好序。
n=3
时只要作
3
次
比较即可，
…。
而当
n
较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相
当困难的。
基本思想及策略
:
分治法的设计思想是：将一个难以直接解决的大问题，分割
成一些规模较小的相同问
题，以便各个击破，分而治之。
分治策略是：对于一个规模为
n<
/p>
的问题，若该问题可以容易地解决（比如说规模
n
较
小）则直接解决，否则将其分解为
k
个规模较小的子问题，这些子问题互相独立且与原问
题形式相同，递归地解这些
子问题，然后将各子问题的解合并得到原问题的解。这种算法
设计策略叫做分治法。
如果原问题可分割成
k
个子问题，
的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题 的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以 使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其 解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计 之中，并由此产生许多高效算法。 an 计算机速度快和自动化的特点。 <
br>在所有的递推关系中， Fibonacci
1
≤<
/p>
n
，且这些子问题都可解并可利用这些子问题
分治法适用的情况
:
分治法所能解决的问题一般具有以下几个特征：
1)
该问题的规模缩小到一定的程度就可以容易地解决
2)
该问题可以分解为若干个规模较小的相同问题，即该问题
具有最优子结构性质。
3)
利用该问题分解出的子问题的解可以合并为该问题的解；
4)
该问题所分解出的各个子问题是相互独立的，即子问题之
间不包含公共的子子问题。
1
1.2
递推算法
递推算法是一种根据递推关系进行问题求解的方法。<
/p>
递推关系可以抽象为一个简单的数学模型，
即给定一个数的序列<
/p>
a0
，
a1...
，
an
若存在整数
n0
，使当
n>n0
时可以用等号将
与其前面的某些
项
ai
联系起来
,
这样的式子成为递推公式。递推算
法是一种简单的算法，通过已知条件利用特点的
递推关系可以得出中间推论，直至得到问
题的最终结果，递推算法分为顺推法和逆推法两种，顺推
法则是在不知道初始条件的情况
下，从问题的结果除非经递推关系逐步推算出问题的解，这个问题
的解也是问题的初始条
件。
递归法是从已知条件出发，一步步地递推出未知项，直
到问题的解。递归也是递推的一种，只
不过它是对待解问题的递推，知道把一个负责的问
题递推为简单的易解问题，然后再一步步返回，
从而得到原问题的解。严格来讲，递归不
仅仅是一种问题求解方法，更是一种编程技术，许多算法
可以通过递归技术来编程实现。
在计算机科学中，
人们把程序直接或间接调用自身的过程称为递
归。
过程或函数直接调用自身的递归成为直接递归，
间接调用自
身的递归称为间接递归。
在问题求解中，
采用递归算法有两个重
要的好处：一是容易证明算法有两个重要的好处，其次是代码实现简洁，代
码编程量少。
不足是程序运行效率较低。
递推算法的基本思想是把一个复杂庞大的计算过程转化为简单过程的多次重复。该算法利用了
而递归法的思想是从已知条件出发，一步步地递推出未
知项，直到问题的解。
五种典型的递推关系
:
cci
数列
Fibonacci
数列应该是最
为大家所熟悉的。在最基础的程序设计语言
Logo
语言中，就有很多这类的题目。而在较为复杂的
Basic
、
Pascal
、
C<
/p>
语言中，
Fibonacci
数列类
的题目因为解法相对容易一些，逐渐退出了竞赛的舞台。可是这不等于说
数列没有研究
价值，恰恰相反，一些此
类的题目还是能给我们一定的启发的。
Fibo
nacci
数列的代表问题是由意大利著名数学家
Fibona
cci
于
1202
年提出的
“兔子繁殖问题”
(
又称“
Fibonacci
问题”
)
。
问题的提出：有雌雄一对兔子
，假定过两个月便可繁殖雌雄各一的一对小兔子。问过
n
个月后
共有多少对兔子？
解：设满
< br>x
个月共有兔子
Fx
对，其中当
月新生的兔子数目为
Nx
对。第
x-1
个月留下的兔子数
目设为
Fx-1
对。则：
Fx=Nx+ Fx-1
Nx=Fx-2 (
即第
x-2
个月的
所有兔子到第
x
个月都有繁殖能力）
∴
Fx=Fx-1+Fx-2
边界
条件：
F0=0
，
F1=1
由上面的递推关系可依次得到：
F2=F1+F
0=1
，
F3=F2+F1=2
，
F4=F3+F2=3
，
F5=F4+F3
=5
，……。
Fabo
nacci
数列常出现在比较简单的组合计数问题中，例如以前的竞赛中出现的“骨牌覆
盖”
问题。在优选法中，
Fibonacci
< br>数列的用处也得到了较好的体现。
塔问题
问题的提出：
Hanoi
塔由
n
个大小不同的圆盘和三根木柱
a,b,c
组成。开始时，这
n
个圆盘由
大到小依次套在
a
柱上，如图
3-11
所示。
2
要求把
a
柱上
n
个圆盘按下述规则移到
c
柱上：
(1)
一次只能移一个圆盘；
(2)
圆盘只能在三个柱上存放；
(3)
在移动过程中，不允许大盘压小盘。
问将这
n
个盘子从
a
柱移动到
< br>c
柱上，总计需要移动多少个盘次？
解：设
hn
为
n
个盘子从
a
柱移到
c
柱所需移动的盘次。显然，当
n=1
时，只
需把
a
柱上的
盘子直接移动到
c
柱就可以了，故
h1=1
< br>。当
n=2
时，先将
a
柱上面的小盘子移动到
b
柱上去；然后
将大盘子从
a
柱移到
c
柱；最后，将
b
柱上的小盘子移到
c
柱上，共记
3
个
盘次，故
h2=3
。以此类
推，当
a
柱上有
n(n2)
个盘子时，总是先借助
c
柱把上面的
n-1
个盘子移动到
b
柱上，然后把<
/p>
a
柱
最下面的盘子移动到
c
柱上；
再借助
a
柱把
b
柱上的
n-1
个盘子移动到
c
柱上；
总共移动
hn-1+1+hn-1
个盘次。
∴
hn=2hn-1+1
边界条件：
h1=1
3.
平面分割问题
< br>问题的提出：设有
n
条封闭曲线画在平面上，而任何两条
封闭曲线恰好相交于两点，且任何三条封
闭曲线不相交于同一点，问这些封闭曲线把平面
分割成的区域个数。
解：
设
an
为
n<
/p>
条封闭曲线把平面分割成的区域个数。
由图
3-13
可以看出：
a2-a1=
2
；
a3-a2=4
；
a4-a3=6
。
从这些式子中可以看出
an-
an-1=2(n-1)
。当然，上面的式子只是我们通过观察
4
幅图后得出的
结论，它的正确性尚不能保证。下面不妨让我们
来试着证明一下。当平面上已有
n-1
条曲线将平面
分割成
an-1
个区域后，第
n-1
条曲线每与曲线相交一次，就会增加一个区域，因为平面上已有了
n-1
条封闭曲线，且第
n
条曲线与已有的每一条闭曲线恰好相交于两点，且不会与任两条曲线交于
同一点，故平
面上一共增加
2(n-1)
个区域，加上已有的
an-1
个区域，一共有
an-1+2(n-1)
个区域。
所以本题的递推关系是
an=an
-1+2(n-1)
，边界条件是
a1=1
。
n
数
3
Catalan
数首先是由
Euler
在精确计算对凸
n
边形的不同的对角三角形剖分的个数问题时得到
的，它经常出现在组合计数问题中。
问题的提出：在一个凸
n
边形中，通过不相交于
n
边形内部的对角线，把
n
边形拆分成若干三
角形，不同的拆分数目用
hn<
/p>
表示，
hn
即为
Catalan
数。例如五边形有如下五种拆分方案
(
图
3-14)
，
故
h5=5
。求对于一个任意的凸
n
边形相应的
hn
。
5.
第二
类
Stirling
数
n
个有区别的球放到
m
个相同的盒子中，要求无一空盒，其不同的方案数用
S(n,m)
表示，称为
第二类
Stirling
数。
根据定义来推导带两个参数的递推关系——第二类
Stirling
数。
解：
设有
n
个不同的球，
分别
用
b1,b2,
……
bn
表示。
从中取出一个球
bn
，
bn
的放法有以下两种：
①
bn
独自占一个盒子；那么剩下的球只能放在
m-1
个盒子中，方案数为
S2(n-1,m-1)<
/p>
；
②
bn
与别的球共占一个盒子；那么可以事先将
b1,b2,
……
bn-1
这
n-1
个球放入
m
个盒子中，然
后再将球
bn
可以放入其中一个盒子中，方案数为
m
S2(n-1,m)
。
综合以上两种情况，可以得出第二类
Stirling
数定理：
【定理】
< br>S2(n,m)=mS2(n-1,m)+S2(n-1,m-1) (n>1,m1)
边界条件可以由定义
2
推导出：
S2(n,0)=0
；
S2(n,1)=1
；
S2(n
,n)=1
；
S2(n,k)=0(k>n)
< br>。
4
2
问题分析及算法设计
2.1
分治策略递归算法的设计
从本问题的具体情况出发，根据分治算法思想，设计出本问题的分治递归算法
按分治策略，可将所有选手分成两组。
n
个选手的比赛日程表，可以通过
n/2
个选手
的比赛日程表，可以通过
n/4
个选手设计
日程表来决定；……；直到为
2
个选手的比赛日
程表。这样比赛日程表的设计就变得很简单，这时只要让两个选手互相比赛即可，这样可
以形成
n/2
组
2
个选手的比赛日程表（如表
1
、表
2
）
。然后再反过来在两个选手的日程表
上为
4
个选手设计比赛日程表（如表
3
）
。然后再类推到
8
个、
16
个、……、
2
k
个选手。
对所有运动员的赛程进行安排，并将其存入数组内
:
1
2
3
4
5
6
7
8
对于第一部分，将其划分为四
个小的单元，即对第二行进行如下划分
:
同理，对第二部分（即三四行）<
/p>
，划分为两部分，第三部分同理
由初始化的第一行填充第二行
:(
填充原则是对角线填充
)
1
2
2
1
3
4
4
3
5
6
6
5
7
8
8
7
由
s
控制的第一部分填完。然后是<
/p>
s++
，进行第二部分的填充
1
2
3
4
5
6
7
8
2
1
4
3
6
5
8
7
3
4
1
2
7
8
5
6
4
3
2
1
8
7
6
5
5
最后是第三部分的填充
1
2
3
4
5
6
7
8
2
1
4
3
6
5
8
7
3
4
1
2
7
8
5
6
4
3
2
1
8
7
6
5
5
6
7
8
1
2
3
4
6
5
8
7
2
1
4
3
7
8
5
6
3
4
1
2
8
7
6
5
4
3
2
1
这样循环，直到填充完毕
递归算法解：
6
2.2
分治策略非递归算法的设计
分治策略同上。
非递归算法解：
7
2.3
递推策略算法的设计
递推策略：
8