ACM暑期集训
1递推关系
组合数学（4）递推递归母函数
序列a
a0，a1，…，a
，…，把a
与某些aii
联系起来的等式叫做关于序列a
的递推方程。当给定递推方程和适当的初值就唯一确定了序列。递推关系分类：（1）按常量部分：齐次递推关系：指常量＝0，如F
F
1F
2非齐次递推关系：指常量≠0，如F
2F
11（2）按运算关系：线性关系，如上面的两个；非线性关系，如F
F
1F
2。（3）按系数：常系数递推关系，如（1）中的两个；变系数递推关系，如D
1D
1D
2。（4）按数列的多少一元递推关系，只涉及一个数列，上面的均为一元；多元递推关系，涉及多个数列，如
i
trecurre
cei
t
递推f12fori2i
if
f
1
retur
f
i
trecursio
i
t
递归：if
1retur
2递归终止条件elseretur
recursio
1
更快的方法是求出通项：F

121例2：HDOJ2050折线割平面问题在一个无限的平面上有N条折线，试问这些折线最多能将平面分割成多少区域？
a
7a
1b
1b
7b
1a
1
Fibo
acci数列为11235813lo
glo
gdata100data11data21fori
ti3i50idataidatai1datai2whileci
coutdata
e
dl例1：直线割平面问题。在一个无限的平面上有N条直线，试问这些直线最多能将平面分割成多少区域？F12F24F37F
F
1
1
F
F
14
3F
2
2
1例3：椭圆割平面问题。在一个无限的平面上有N个椭圆，试问这些椭圆最多能将平面分割成多少区域？F
F
14
1
f边的那个数。分析：7（7）3（10）8（15）8（18）1max1015116015220725420419424530227626524i
piji
pi1ji
pi1j1设
位八进制数中0出现偶数次的共有a
个，出现奇数次的共有b
个。a
和0求
b
满足的递推关系。
对0出现偶数次的
位八进制数分两种情况讨论：（1）最高位是0，则其余
－1位应该含有奇数个0，这类数共有b
1个。（2）最高位非0，则其余
－1位应该含有偶数个0，这类数共有7a
1个。因此有a
＝7a
1＋b
1。同理可得b
＝a
1＋7b
1，所以a
、b
满足
a
7a
1b
1b7ba
1
1
a17b11
例
＝20出现偶数次的数00，11，12，13，14，15，…，77，共50个0出现奇数次的数01，10，02，20，03，30，…，70，共14个数字三角形738810274445265给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和r