离散数学-newchap07(精品·公开课件).ppt

离散数学 第7章 递推关系 递归（推）关系 本章将对递归关系进行介绍。 递归关系可用于解决一些特定的计数问题。 递归关系是序列中第n 个元素与它前若干个元素之间的关系。 由于递归关系和递归算法密切相关，因此递归关系可以很自然地用于递归算法分析。 递推关系 建立序列中第n项与其前趋元素间的关系 递归算法的分析 7.1 简介 以5开始 给定了某一项，+3得到下一项 递推关系 an a1 =5 an = an-1 +3 n ? 2 a2 = a1 +3 = 5+3=8 a3 = a2 +3 = 8+3=11 递推关系是由数列第n项前的若干项确定第n项，并由此确定数列。 定义7.1.1 数列a0 , a1, . . .的递推关系是一个由a0 , a1, . . . ， an-1中的一些或全部确定an的等式。 数列a0 , a1, . . .的初始条件是对数列的有限个元素给定的确定值。 例 7.1.2 Fibonacci级数 递推关系fn = fn-1 + fn-2 n ? 3 初始条件 f1 =1 f2 =2 例 7.1.3 投资$1000, 利息12% An 第n年底的总金额， {An} An = An-1 + (0.12) An-1 = 1.12An-1 n ? 1 A0=1000 A3 = 1.12A2 = 1.12*1.12A1 = 1.12*1.12 *1.12 A0 = 1.12 3 (1000) An = 1.12An-1 = 1.12 n (1000) 通项公式 通项公式 递推关系 递归算法 数学归纳法 三者的共同点是 ：将处理当前情况时的先验示例看做是已知的。递归关系利用序列中的先验值计算当前项的值；递归算法利用当前输入的较小示例来处理当前的输入；用数学归纳法证明命题的归纳步，总先假设命题的先验示例成立，进而证明当前命题成立。 算法 7.1.4 Input: n Output:第n年底的总金额 procedure interest(n) if n =0 then return (1000) return(1.12 * interest(n-1)) end interest 例7.1.5 将n 元素集合的子集总数记为Sn。由于n 元素集合的子集总数是(n - 1)元素集合的子集总数的两倍故可得递归关系： Sn = 2Sn-1 初始条件为 S0 = 1 例7.1.6 Sn不含111的n位二进制字符串的个数，确定递推关系。 Answer 以0开始的 以10开始的 以110开始的 Sn= Sn-1+ Sn-2+ Sn-3 n ?4 S1=2， S2= 4， S3= 7 0，1 00，01， 10， 11 000，001，010， 011， 100， 101， 110 例7.1.7 Catalan数 从左下角走到右上角，只允许向右或向上走，路线只能经过但不能超越从左下角到右上角的对角线. Answer (0,0) ? (k, k) (k,k) ? (n,n) n Cn = ? Ck-1Cn-k k=1 Hanoi塔 Cn 移动次数 移动次数 Cn = 2Cn-1 +1 n ?2 C 1 = 1 最优？ 数学归纳法证明 设dn是最优解法的移动次数， dn =？Cn n=1 : dn =Cn =1 n-1: dn-1 =Cn-1 dn ? 2 dn-1 +1 = 2 Cn-1 +1=Cn Cn ? dn dn =Cn 经济学中的Wed 需求 p=a-bq p 价格， q数量 价格高，销量少 供给 p=kq 价格高，产量多， 对需求变化的 反应有一定的延迟 分析 n=0, 1, . . .离散时间点 pn= a-bqn pn= kqn+1 模型 k=tan ? =- tan ?=b k? b k=b b k b k Ackermann函数 A(m,0)= A(m-1,1), m=1,2, . . . A(m,n)=A(m-1, A(m,n-1)), m=1,2, . . . n= 1,2, . . . A(0,n)=n+1 n= 0, 1,2, . .. 7.2求解递推关系 数列a0 , a1, . . .的通项公式an 代入法 定常系数