文档介绍：递推关系的建立及在信息学竞赛中的应用
Recurrence relations and the establishment of the information science contest application
【摘 要】
世，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn-1+1+hn-1个盘次。
∴hn=2hn-1+1 边界条件：hn-1=1
递推关系的求解方法
求解递推关系最简单易行的方法是递推，递推是迭代算法中一种用若干步可重复的简单运算来描述复杂数学问题的方法，以便于计算机进行处理。它与递推关系的思想完全一致，由边界条件开始往后逐个推算，在一般情况下，效率较高，编程也非常的方便。但是，我们一般只需要求递推关系的第n项，而边界条件与第n项前面之间的若干项的信息是我们不需要的，如果采用递推的方法来求解的话，第n项之前的每一项都必须计算出来，最后才能得到所需要的第n项的值。这是递推无法避免的，从而在一定程度上影响了程序的效率。当然在大多数情况下，采用递推的方法还是可行的，在竞赛中，使用递推的方法编程，通常会在时限内出解。
当然，更好的求解方法还有母函数法、迭代归纳法等等，这里就不再一一展开论述了。
例如同样是对于Fibonacci数列问题：递推的方法要从F1，F2开始逐个推算出F3，F4……Fn，而利用母函数的方法，则可以得出公式，则可直接求出所需要的任意一项。
递推关系的应用
递推关系的应用十分的广泛，其中一个非常重要的应用就是著名的杨辉三角(又称“Pascal三角”，见图5)。杨辉三角是根据组合公式[3]画出来的。很显然，组合公式、杨辉三角都属于递推关系的范围。
1
1
1
1
1
1
1
1
1
1
1
2
3
3
4
6
4
5
10
10
5
n=1
n=2
n=3
n=4
n=5
r=0
r=1
r=2
r=3
r=4
图5
在今天的信息学竞赛中，递推关系的应用也日趋广泛，下面就让我们从近年来的两道竞赛题中体会递推关系的应用。
3
5
7
9
11
13
4
6
8
10
12
14
……
……
图6
『例1』(1998蚌埠市竞赛复试第一题)有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。试求出蜜蜂从蜂房a爬到蜂房b的可能路线数。
解：这是一道很典型的Fibonacci数列类题目，其中的递推关系很明显。由于“蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行”的限制，决定了蜜蜂到b点的路径只能是从b-1点或b-2点到达的，故fn=fn-1+fn-2 (a+2nb)，边界条件fa=1，fa+1=1。()
『例2』(1998合肥市竞赛复试第二题)同一平面内的n(n500)条直线，已知有p(p2)条直线相交于同一点，则这n条直线最多能将平面分割成多少个不同的区域？
解：这道题目与第一部分中的平面分割问题十分相似，不同之处就在于线条的曲直以及是否存在共点线条。由于共点直线的特殊性，我们决定先考虑p条相交于一点的直线，然后再考虑剩下的
n-p条直线。首先可以直接求出p条相交于一点的直线将平面划分成的区域数为2p