高级计数.pptVIP

4.6.2 另一种形式的容斥原理 设Ai是具有性质Pi的 元素的子集(i=1~n)。具有所有这些性质Pi1 Pi2 …Pik的元素数记作N(Pi1 Pi2 …Pik) 。即： |Ai1∩ Ai2∩…∩ Aik |= N(Pi1 Pi2 …Pik) 设不具有n个性质P1,P2,…,Pn中的任何一条的元素记作N(P1’ P2’ …Pn’) ，集合中的元素数记为N。那么： N(P1’ P2’ …Pn’) =N- |A1∪A2∪…∪An| 利用容斥原理求解。 * 例1：x1+x2+x3=11有多少个整数解？其中x1，x2，x3是非负整数，且x1≤3， x2≤4， x3 ≤6。 解： 令性质P1: x1＞3 , 性质P2：x2＞4 ，性质P3： x3 ＞6 满足不等式x1≤3， x2≤4， x3 ≤6的解是 N(P1’,P2’,P3’)=N-N(P1)-N(P2)-N(P3) +N(P1P2) +N(P1P3)+N(P2P3)-N(P1P2P3) 方程的所有非负整数解N=C(3+11-1,11)=78 N(P1)=C(3+7-1,7)=C(9,7)=36 N(P2)=C(3+6-1,6)=C(8,6,4)=28 N(P3)=C(3+4-1,4)=C(6,4)=15 N(P1P2)=C(3+2-1,2)=C(4,2)=6 N(P1P3)=C(3+0-1,0)=1 N(P2P3)=0 N(P1P2P3)=0 * * * 例 dn = 4(dn - 1 - dn - 2 ) d0 = d1 =1 解：t2 - 4t +4 = 0 r1 = r2 = r=2 dn = b 2 n+ d n 2 n d0 = d1 =1 d0 =1= b 2 0+ d 0 2 0 = b d1 =1= b 2 1+ d 1 2 1 = 2 b + 2 d =1 b =1， d = - ? dn = 2 n- n 2 n-1 例， an = 6an-1 -11 an-2 +6 an-3,其中a0=2,a1=5,a2=15 解：特征方程： r3-6r2+11r-6=0 特征根为：r1=1, r2=2, r3=3 则an = b*1n+d*2n+e*3n 根据初始条件： 2=b+d+e 5=b+2d+3e 15=b+4d+9e 得出b=1, d=-1, e=2 故而 an = 1-2n+2*3n * 定理3 * 设 c1，c2，…,ck是实数,特征方程 rk-c1rk-1-c2rk-2 -…-ck=0 有k个不同的根 r1,r2,…, rk 那么 an=b1r1n+b2r2n,+…+bkrkn 4.2.3 常系数线性非齐次递推关系 * 形如：an=c1an-1+c2an-2 +ckan-k+F(n) 设 c1，c2，…,ck是实数，F(n)是只依赖于n的函数 ——相伴的齐次递推关系 * 例： 非齐次递推关系 an=an-1+2n an=an-1+an-2 +n2+n+1 an=3an-1+n3n 相伴的线性齐次递推关系 an=an-1 an=an-1+an-2 an=3an-1 定理5 如果{an(p)}是常系数非齐次线性递推关系 an=c1an-1+c2an-2 +ckan-k+F(n)的一个特解， 那么每个解都是形如{an(p)+an(h)}的形式， 其中{an(h)}是相伴的齐次递推关系 an=c1an-1+c2an-2 +ckan-k 的解 * 例：求递推关系an=3an-1+2n的所有解。具有a1=3的解？ 解：相伴的齐次线性方程是an=3an-1, 它的解是an(h)=b*3n 找一个特解 * * 4.3 分治算法和递推关系 递归算法将一个给定输入的问题划分成一个或多个小问题。 如何用递推关系分析分治算法的计算复杂性。 用递推关系分析算法运行的时间 基本思想： an 表输入量为n时算法运行的时间 确定数列a0 a1 , . . .的递推关系和初始条件，通过求解递推关系，确定算法所需的时间。 4.3.2 分治递推关系 分治递推关系： 假设一个递归算法将规模为n的问题分解很a个子问题， 假设将子问题的解组合成原来问题的解的算法处理步中需要额外的运算量g(n) 则，如果f(n)表示求解规模为n的问题所需要的运算数，则得出f 满足递推关系 f(n)=af(n/b)+g(n) * * 排序例 选取最大的放在最后，在剩下的中选最大的放在倒数第二，. . . ,重复，直到排好。 * 算法7.3.1选择排序 Input: s1 , . . ., sn