组合数学递推关系公开课一等奖优质课大赛微课获奖课件.pptVIP

第2章递推关系与母函数2.1递推关系2.2母函数(生成函数)2.3Fibonacci数列×2.4优选法与Fibonacci序列应用2.5母函数性质(一)2.6线性常系数齐次递推关系(二)2.7关于常系数齐次递推关系(三)2.8整数拆分(四)2.9ferrers图像×2.10拆分数预计2.11指数型母函数(五)2.12广义二项式定理2.13应用举例(六)2.14非线性递推关系举例2.15递推关系解法补充1第1页第1页

2.1递推关系例一.Hanoi塔问题:N个半径各不相同圆盘，三根圆柱A,B,C;算法:n=1时，直接把A柱盘移到C上。n1时,先把A柱最上面n-1张盘通过C柱移到B上;然后再将A柱上最下面盘移到C盘上;最后将B盘上盘通过A盘移到C盘上。递归是子程序或函数重复地调用自己2第2页第2页

2.1递推关系voidhanoi(charA,charB,charC,intn){if(n==1)printf(“movedisk1from%cto%c”A,C)else{hanoi(A,C,B,n-1);printf(“movedisk%dfrom%cto%c”,n,A,C)hanoi(B,A,C,n-1);}}3第3页第3页

2.1递推关系例一.Hanoi塔问题:N个半径各不相同圆盘，三根圆柱A,B,C;算法:n=1时，1次n1时,hn=2hn-1+1求总共需要移动多少次？设分别为h1,h2,…,hn4第4页第4页

2.1递推关系递推关系定义:对于数列a1,a2,…,an,除了前面若干数外,其余各项an与它前面若干个数关联起来方程叫做递推关系。边界条件(初始条件):在求解递推关系时，前面必须知道若干个数，这若干个已知数称为初始条件，或边界条件。常系数递推关系。线性递推关系。5第5页第5页

2.1递推关系用迭代法求解递推关系6第6页第6页

例一、求解盘片为n汉诺塔算法下列:hanoi(intn,charA,charB,charC){if(n==1)printf(“Movedisk%dfromAtoC”,n);elsehanoi(n-1,A,C,B);printf(“Movedisk%dfromAtoC”,n);hanoi(n-1,B,A,C);}求时间复杂性7第7页第7页

解:设n张盘需执行h(n)次h(n)=2h(n-1)+2h(n-1)=2h(n-2)+2h(n-2)=2h(n-3)+2……………h(3)=2h(2)+2h(2)=2h(1)+2h(1)=2h(2)=22+2h(3)=23+22+2…………h(n-1)=2n-1+2n-2+…+2h(n)=2n+2n-1+…+22+2h(n)=2n+1-2O(2n)***例题8第8页第8页

例2-2Fibonacci(费卜拉契）数列问题：设有初生雌、雄小兔一对，但第2个月过后便每月繁殖雌、雄各一小兔一对，试问第n个月有雌、雄兔子多少对？2.1递推关系1,1,2,3,5,8,13,21Fn=Fn-1+Fn-29第9页第9页

算法:intfibonacci(intn){if(n=1||n=2)return(1);elsereturn(fibonacci(n-1)+fibonacci(n-2));}2.1递推关系**时间复杂性:f(n)=f(n-1)+f(n-2)+110第10页第10页

2.2母函数例2-3:有红球两个，白球、黄球各一个，试求有多少种不同组合方案，假设两个红球没有区分。共有1+3+4+3+1=12种组合方案。解:一、用组合办法来解:一个都不选:1种方案选1个球,3种方案选2个球,4种方案选3个球,3种方案选4个球,1种方案11第11页第11页

二、用函数办法解:设r，w，y分别代表红球，白球，黄球；单独红球组合方式为1，1，1:结构函数:1+r+r2单独白球与单独黄球组合方式分别为:1,1和