第3章递推算法(C++版).ppt

Ⅴ.第二类Stirling数 　　 在五类典型的递推关系中，第二类Stirling是最不为大家所熟悉的。也正因为如此，我们有必要先解释一下什么是第二类Strling数。 　　　【定义2】n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling数。 　　　 下面就让我们根据定义来推导带两个参数的递推关系——第二类Stirling数。 解：设有n个不同的球，分别用b1,b2,……bn表示。从中取出一个球bn，bn的放法有以下两种： 　　 ①bn独自占一个盒子；那么剩下的球只能放在m-1个盒子中，方案数为S2(n-1,m-1)； 　　 ②bn与别的球共占一个盒子；那么可以事先将b1,b2,……bn-1这n-1个球放入m个盒子中，然后再将球bn可以放入其中一个盒子中，方案数为mS2(n-1,m)。 综合以上两种情况，可以得出第二类Stirling数定理： 　　　 【定理】S2(n,m)=mS2(n-1,m)+S2(n-1,m-1) (n1,m1) 边界条件可以由定义2推导出： 　　　 S2(n,0)=0；S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(kn)。 　　 第二类Stirling数在竞赛中较少出现，但在竞赛中也有一些题目与其类似，甚至更为复杂。读者不妨自己来试着建立其中的递推关系。 　　 小结：通过上面对五种典型的递推关系建立过程的探讨，可知对待递推类的题目，要具体情况具体分析，通过找到某状态与其前面状态的联系，建立相应的递推关系。 　　 【例7】(1998合肥市竞赛复试第二题)同一平面内的n(n500)条直线，已知有p(p2)条直线相交于同一点，则这n条直线最多能将平面分割成多少个不同的区域？ 　　 解：这道题目与第一部分中的平面分割问题十分相似，不同之处就在于线条的曲直以及是否存在共点线条。由于共点直线的特殊性，我们决定先考虑p条相交于一点的直线，然后再考虑剩下的n-p条直线。首先可以直接求出p条相交于一点的直线将平面划分成的区域数为2p个，然后在平面上已经有k(kp)条直线的基础上，加上一条直线，最多可以与k条直线相交，而每次相交都会增加一个区域，与最后一条直线相交后，由于直线可以无限延伸，还会再增加一个区域。所以fm=fm-1+m (mp)，边界条件在前面已经计算过了，是fp=2p。虽然这题看上去有两个参数，但是在实际做题中会发现，本题还是属于带一个参数的递推关系。 【上机练习】 1、走楼梯 楼梯有N级台阶，上楼可以一步上一阶，也可以一步上二阶。编一递归程序，计算共有多少种不同走法？ 【输入样例】Stairs.in 3 【输出样例】Stairs.out 3 2、兔子繁殖 有一种兔子，出生后一个月就可以长大，然后再过一个月一对长大的兔子就可以生育一对小兔子且以后每个月都能生育一对。现在，我们有一对刚出生的这种兔子，那么，n个月过后，我们会有多少对兔子呢？假设所有的兔子都不会死亡。 【输入格式】 输入文件仅一行，包含一个自然数n。 【输出格式】 输出文件仅一行，包含一个自然数，即n个月后兔子的对数。 【输入样例】Rabbit.in 5 【输出样例】Rabbit.out 5 3、平面分割 同一平面内有n（n≤500）条直线，已知其中p（p≥2）条直线相交于同一点，则这n条直线最多能将平面分割成多少个不同的区域？ 【输入格式】 两个整数n（n≤500）和p（2≤p≤n）。 【输出格式】 一个正整数，代表最多分割成的区域数目。 【输入样例】Surface.in 12 5 【输出样例】Surface.out 73 4、骨牌铺法 有1×n的一个长方形，用一个1×1、1×2和1×3的骨牌铺满方格。例如当n=3时为1×3的方格。此时用1×1、1×2和1×3的骨牌铺满方格，共有四种铺法。如下图： 【输入样例】Domino.in 3 【输出样例】Domino.out 4 5、蜜蜂路线 【问题描述】 一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你：蜜蜂从蜂房M开始爬到蜂房N，MN，有多少种爬行路线？ 【输入格式】 输入M，N的值。 【输出格式】 爬行有多少种路线。 【输入样例】bee.in 1 14 【输出样例】bee.out 377 6、数塔问题 【问题描述】 设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如图所示： 若要求从根结点开始，请找出一条路径，使路径之和最大，只要输出路