递推关系的建立及其求解方法.ppt

递推关系的建立及其求解方法 王桐林 一 递推式的建立0 Fibonacci数列1 Hanoi塔问题问题 三柱问题问题 四柱问题问题 m柱问题2 平面分割问题问题 封闭曲线分割平面问题 Z 分割平面问题 M 分割平面3 Catalan数问题一 凸n边形的三角形剖分问题二 二叉树数目问题三 出栈序列4 第二类Stirling数问题一 放置小球问题二 集合划分问题5 其他问题一 集合取数问题问题二 整数划分问题 二 递推式的求解方法 1 递归函数 用数组实现 求递推式的通项表达式 3 1 迭加法3 2 待定系数法3 3 特征方程法3 4 生成函数法 三 递推的形式 顺推法和倒推法 Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的 兔子繁殖问题 又称 Fibonacci问题 问题 一个数列的第0项为0 第1项为1 以后每一项都是前两项的和 这个数列就是著名的裴波那契数列 求裴波那契数列的第N项 1 Fibonacci数列 解答 由问题 可写出递推方程 算法 F 0 1 F 1 2 FORi 2TONDOF I F I 1 F I 2 总结 从这个问题可以看出 在计算裴波那契数列的每一项目时 都可以由前两项推出 这样 相邻两项之间的变化有一定的规律性 我们可以将这种规律归纳成如下简捷的递推关系式 Fn g Fn 1 这就在数的序列中 建立起后项和前项之间的关系 然后从初始条件 或是最终结果 入手 按递推关系式递推 直至求出最终结果 或初始值 很多问题就是这样逐步求解的 对一个试题 我们要是能找到后一项与前一项的关系并清楚其起始条件 或最终结果 问题就可以递推了 接下来便是让计算机一步步了 让高速的计算机从事这种重复运算 真正起到 物尽其用 的效果 递推概念 给定一个数的序列H0 H1 Hn 若存在整数n0 使当n n0时 可以用等号 或大于号 小于号 将Hn与其前面的某些项Hn 0i n 联系起来 这样的式子就叫做递推关系 如何建立递推关系递推关系有何性质如何求解递推关系 1 Hanoi塔问题问题的提出 Hanoi塔由n个大小不同的圆盘和m根木柱1 2 3 m组成 开始时 这n个圆盘由大到小依次套在1柱上 如图所示 现在要求把1柱上n个圆盘按下述规则移到m柱上 1 一次只能移一个圆盘 2 圆盘只能在m个柱上存放 3 在移动过程中 不允许大盘压小盘 求将这n个盘子从1柱移动到m柱上所需要移动盘子的最少次数 问题 三柱问题 设f n 为n个盘子从1柱移到3柱所需移动的最少盘次 当n 1时 f 1 1 当n 2时 f 2 3 以此类推 当1柱上有n n 2 个盘子时 我们可以利用下列步骤 第一步 先借助3柱把1柱上面的n 1个盘子移动到2柱上 所需的移动次数为f n 1 第二步 然后再把1柱最下面的一个盘子移动到3柱上 只需要1次盘子 第三步 再借助1柱把2柱上的n 1个盘子移动到3上 所需的移动次数为f n 1 由以上3步得出总共移动盘子的次数为 f n 1 1 f n 1 所以 f n 2f n 1 1 f n 2n 1 问题 四柱问题 问题分析 令f i 表示四个柱子时 把i个盘子从原柱移动到目标柱所需的最少移动次数 j 第一步 先把1柱上的前j个盘子移动到另外其中一个非目标柱 2或3柱均可 假设移到2柱 上 此时3和4柱可以作为中间柱 移动次数为 f j 第二步 再把原1柱上剩下的i j个盘子在3根柱子 1 3 4 之间移动 最后移动到目标柱4上 因为此时2柱不能作为中间柱子使用 根据三柱问题可知 移动次数为 2 i j 1 第三步 最后把非目标柱2柱上的j个盘子移动到目标柱上 次数为 f j 通过以上步骤我们可以初步得出 f i 2 f j 2 i j 1 j可取的范围是1 j I 所以对于不同的j 得到的f i 可能是不同的 本题要求最少的移动次数 f i min 2 f j 2 i j 1 其中1 j I constMaxNum 1000 varn integer F3 F4 array 1 MaxNum ofdouble procedureInit vari integer beginfillChar F3 sizeOf F3 0 fillChar F4 sizeOf F4 0 readln n F3 1 1 F4 1 1 F3 n 为Hanoi塔中3根柱子 n个盘子的最少移动次数F3 n 2 n 1 F4 n 为Hanoi塔中4根柱子 n个盘子的最少移动次数 fori 2tondoF3 i 2 F3 i 1 1 end procedureRun vari j integer minF4i temp double beginfori 2tondobeginminF4i 1e 100 forj 1toi 1dobegintemp 2 F4 j F3 i j if temp minF4i thenminF4i temp end F4 i min 2 F4 j F3 i j 1 j i 1 F4 i minF4i end writeln F4 n 0 0 end beginInit Run end 问题 m柱问题 问题分析 设F m n 为m根柱子 n个盘子时移动的最少次数 1 先把1柱上的前j个盘子移动到另外其中一个除m柱以外的非目标柱上 移动次数为 f m j 2 再把原1柱上剩下的n j个盘子在m 1根柱子之间移动 最后移动到目标柱m上 移动次数为 f m 1 n j 3 最后把非目标柱上的j个盘子移动到目标柱没柱上 移动次数为 f m j F m n min 2 F m j F m 1 n j 1 j n 2 平面分割问题问题 问题的提出 设有n条封闭曲线画在平面上 而任何两条封闭曲线恰好相交于两点 且任何三条封闭曲线不相交于同一点 求这些封闭曲线把平面分割成的区域个数 问题分析 设f n 为n条封闭曲线把平面分割成的区域个数 由图4很容易得出 f 1 2 f 2 4 假设当前平面上已有的n 1条曲线将平面分割成f n 1 个区域 现在加入第n条封闭曲线 第n条曲线每与已有的n 1条曲线相交共有2 n 1 个交点 也就是说第n条曲线被前n 1条曲线分割成2 n 1 段弧线 而每一条弧线就会把原来的区域一分为二 即增加一个区域 所以共增加2 n 1 个区域 F n f n 1 2 n 1 问题 问题的提出 一个 z 形曲线可以把一个平面分割成2部分 如图所示 求n个 z 形曲线最多能把平面分割成多少部分 写出递推式f n 问题分析 根据上图容易得出 f 1 2 f 2 12 假设平面上已有n 1个 z 图形把平面分成了f n 1 个区域 加入第n个 z 后 单独考虑第n个 z 的3条边 每一条边和前面的n 1个 z 共有3 n 1 个交点 即这条边被分成3 n 1 1部分 所以增加3 n 1 1个区域 3条边共增加3 3 n 1 1 个区域 但是第n个 z 本身有2个交点 故少了2个区域 所以实际增加了3 3 n 1 1 2个区域 由以上得出 f n f n 1 3 3 n 1 1 2即 f n f n 1 9n 8初始条件 f 1 2 问题 M 分割平面问题二的扩展 在问题二的基础上进一步考虑 如果 z 图形扩展为m边的下列图形 看一下问题的解 通过上面的分析我们很容易知道 n个上述图形可以将平面划分的区域的递推关系 f n f n 1 m m n 1 1 m 1 初始条件 f 1 2 3 Catalan数问题一 凸n边形的三角形剖分在一个凸n边形中 通过不相交于n边形内部的对角线 把n边形拆分成若干三角形 不同的拆分数目用f n 表之 f n 即为Catalan数 例如五边形有如下五种拆分方案 故f 5 5 求对于一个任意的凸n边形相应的f n 区域 是一个凸k边形 区域 是一个凸n k 1边形 区域 的拆分方案总数是f k 区域 的拆分方案数为f n k 1 故包含 P1PkPn的n边形的拆分方案数为f k f n k 1 种 F n 问题二 二叉树数目问题描述 求n个结点能构成不同二叉数的数目 问题分析 设F n 为n个结点组成二叉树的数目 容易知道 f 1 1 f 2 2 f 3 5 选定1个结点为根 左子树结点的个数为i 二叉树数目f i 种 右子树结点数目为n i 1 二叉树数目f n i 1 种 I的可取范围 0 n 1 所以有 F n 为了计算的方便 约定f 0 1 问题三 出栈序列问题描述 N个不同元素按一定的顺序入栈 求不同的出栈序列数目 问题分析 设f n 为n个元素的不同出栈序列数目 容易得出 f 1 1 f 2 2 第n个元素可以第i 1 i n 个出栈 前面已出栈有i 1个元素 出栈方法 f i 1 后面出栈n I个元素 出栈方法为 f n i 所以有 F n 约定 F 0 1 4 第二类Stirling数问题一 放置小球 n个有区别的球放到m个相同的盒子中 要求无一空盒 其不同的方案数用S n m 表示 称为第二类Stirling数 设有n个不同的球 分别用b1 b2 bn表示 从中取出一个球bn bn的放法有以下两种 bn独自占一个盒子 那么剩下的球只能放在m 1个盒子中 方案数为 S n 1 m 1 bn与别的球共占一个盒子 那么可以事先将b1 b2 bn 1这n 1个球放入m个盒子中 然后再将球bn可以放入其中一个盒子中 方案数为 mS n 1 m S n m mS n 1 m S n 1 m 1 n 1 m1 问题二 集合划分问题 设S是一个包含n个元素的集合 S b1 b2 b3 bn 现需要将S集合划分为m个满足如下条件的集合S1 S2 Sm Si Si Sj S1 S2 Sm S 1 I j m 则称S1 S2 Sm是S的一个划分 编程 输入n和m的值 输出不同的划分方案数 要求 输入数据有一行 第一个数是n 第二个数m 样例 输入 43输出 6 不同的方案数用S n m 表示从中取出bn bn的放法有以下两种 bn独自占一个集合 那么剩下的数只能放在m 1个集合中 方案数为 bn与别的数共占一个集合 那么我们可以先将b1 b2 bn 1这n 1个数划分为m个集合 然后再将bn可以任意放入其中一个集合中 方案数为综合以上两种情况可以得出 S n 1 m 1 m S n 1 m S n m m S n 1 m S n 1 m 1 n 1 m1 边界条件 S2 n 1 1 S2 n n 1 S2 n k 0 k n 5 其他 集合取数问题设f n k 是从集合 1 2 n 中能够选择的没有两个连续整数的k个元素子集的数目 求递归式f n k 问题分析 N有两种情况 当n在子集时 则n 1一定不在子集中 即在 1 2 n 2 中选k 1个元素 数目为f n 2 k 1 当n不在子集中时 则在 1 2 n 1 中选k个元素 数目为f n 1 k 所以 f n k f n 2 k 1 f n 1 k 边界条件 F n 1 n f n k 0 n k 整数划分问题将整数n分成k份 且每份不能为空 任意两种分法不能相同 不考虑顺序 例如 n 7 k 3 下面三种分法被认为是相同的 1 1 5 1 5 1 5 1 1 问有多少种不同的分法 输入 n k 6 n 200 2 k 6 输出 一个整数 即不同的分法 样例输入 73输出 4 四种分法为 1 1 5 1 2 4 1 3 3 2 2 3 问题分析 用f I j 表示将整数I分成j分的分法 可以划分为两类 第一类 j分中不包含1的分法 为保证每份都 2 可以先那出j个1分到每一份 然后再把剩下的I j分成j份即可 分法有 f I j j 第二类 j份中至少有一份为1的分法 可以先那出一个1作为单独的1份 剩下的I 1再分成j 1份即可 分法有 f I 1 j 1 所以 f I j f I j j f I 1 j 1 边界条件 f i 1 1 f i j 0 I j 二 递推式的求解方法 1 递归函数 用数组实现 求递推式的通项表达式 3 1 迭加法3 2 待定系数法3 3 特征方程法3 4 生成函数法 1 递归函数用递归函数来实现递推式是初学选手们采用最多的求解方法 只要设置正确的边界条件 相对来说比较容易实现 如 集合取数问题f n k f n 2 k 1 f n 1 k 边界条件 F n 1 n f n k 0 n k functionf n k integer integer beginifk 1thenf nelseifn kthenf 0elsef f n 2 k 1 f n 1 k end 2用数组实现 集合划分问题 S n m m S n 1 m S n 1 m 1 n 1 m1 边界条件 S2 n 1 1 S2 n n 1 S2 n k 0 k n vars array 1 100 1 100 oflongint n m i j integer beginread n m fillchar s sizeof s 0 fori 1tondos i 1 1 fori 1tomdos i i 1 fori 2tomdoforj itondos j i i s j 1 i s j 1 i 1 writeln s n m end 3求递推式的通项表达式 3 1 迭加法一般符合下列形式的递推式可以使用迭代法 F n f n 1 g n 其中 g n 是关于n的线性表达式 F 2 f 1 9 2 8F 3 f 2 9 3 8F 4 f 3 9 4 8 F n f n 1 9 n 8 以上n 1个等式相加得到 f n f 1 9 2 3 4 n 8 n即 f n 9 n n 2 7 n 2 1 如 平面分割问题二 f n f n 1 9n 8初始条件 f 1 2 3 2 待定系数法 适合下列格式的递推式 F n a f n 1 g n a 1 例1 Hanoi塔三柱问题 f n 2f n 1 1 边界条件 f 1 1 令 f n A 2 f n 1 A A为待定系数求得A 1 即 f n 1 2 f n 1 1 由等比数列性质得出 f n 1 2n 1 f 1 1 2n所以 f n 2n 1 例2 求F n 3f n 1 n2 n 2的通项 令 f n An2 Bn c 3 f n 1 A n 1 2 B n 1 c A B C为待定系数 由于上述恒等成立 得 2A 12B 6A 03 3B 2C 0求出 A B C后 从而得出f n 的通项 3 3 特征方程法如果a1 ak是常数 且ak 0 n k 则递推关系F n a1f n 1 a2f n 2 akf n k 称为k阶常系数线性齐次递推关系 它的特征方程是 Xk a1Xk 1 a2Xk 2 ak 0只要求出特征方程的根 再由初始条件表达式中的待定系数 便可以得到原递推关系的解 如果特征方程有k个互不相同的解X1 X2 Xk 则通解为 F n c1X1n c2X2n ckXknc1 c2 ck待定 例 Fibonacci数列F n f n 2 f n 1 f 1 1 f 2 1 解 特征方程 X2 X 1 0 则 f n C1 X1n C2 X2n 又因为 f 1 1f 2 1所以 C1 X1 C2 X2 1C1 X12 C2 X22 1得出 C1 C2 3 4 生成函数法这种方法的基本思想原理 已知数列 a0 a1 a2 an 构造函数 g x a0 a1x a2x2 aixi anxn g x 称为数列a0 a1 a2 an 的生成函数 因此 我们要想求系数an 只要求出g x 然后把g x 展开成幂级数 f x f x0 f1 x0 x x0 f2 x0 x x0 2 2 f n x0 x x0 n n 展开式中xn的系数就是an的表达式 an f n x0 n 如 g x 1 x n a0 a1x a2x2 aixi anxn 展开成幂级数 1 x n Cn0 Cn1X Cn2X2 CniXi CnnXn比较系数得 ai Cni 现在的问题是1 由已有的递推关系怎样构造求出g x 2 把g x 展开成幂级数 例 二叉树数目F n f 0 1 f 1 1求f n