下载文档原格式
算法课件第⼀章1-Introduction10（3）若不是常系数线性递归⽅程，则需要⽤⽣成函数法。
⽣成函数法应⽤举例：先看⼀下A(x)*A(x)即A 2(x)的展开式形状。
设A(x)=0nn n a x∞=∑，则A 2(x)=0nn n a x∞=∑*0nn n a x∞=∑=(a 0+a 1x+a 2x 2+a 3x 3+…+a n x n+…)* (a 0+a 1x+a 2x 2+a 3x 3+…+a n x n+…)= a 02+(a 0a 1+a 1a 0)x+(a 0a 2+a 1a 1+a 2a 0)x2+(a 0a 3+a 1a 2+a 2a 1+a 3a 0)x 3+…+ (a 0a n +a 1a n-1+…+a n-1a 1+a n a 0)x n+…。
求解下列⾮线性递归⽅程已知a n =a 1a n-1+a 2a n-2+ …+a n-1a 1 (n ≥2)且a 1=1，a 2=1，a 3=2，a 4=5，求a n 。
令a 0=0，则上述⽅程可写为：a n = a 0a n +a 1a n-1+ … +a n-1a 1+a n a 0 从2开始对等式两边分别求级数，则有∑∞=2n nn x a =∑∞=2n (a 0a n +a 1a n-1+ … +a n-1a 1+a n a 0)*x n设A(x)=∑∞=0n nnxa 是数列{a 0, a 1,a 2,…,a n ,…}的⽣成函数（幂函数形式），则有A(x)-a 1x-a 0=(A(x))2-(a 1a 0+a 0a 1)x-a 20 ，整理得(A(x))2-A(x)+x=0。
令z=A(x)，则有z 2-z+x=0 求解此关于z 的⼀元⼆次⽅程式，得A(x)= z=(1x 41-±)/2即A(x)应为1/2x 41-±/2 ∵x 41-=∑∞=---1122)2(n nn n xC n，即x 41-的幂级数展开式通项系数为b n=-n2Cn n 122--，a n =±b n/2，⽽a n为正数，∴x 41-±中符号取为负，于是有A(x)=1/2-x 41-/2，a n=C n n n1221--（C 00定义为1）。
算法导论讲解一、课题算法导论讲解二、教学目标1. 让学生对算法有一个基本的概念理解，知道算法在计算机科学以及日常生活中的广泛应用。
2. 能够理解算法的基本特性，如确定性、有穷性等。
3. 激发学生对算法学习的兴趣，为后续深入学习算法相关知识打下基础。
三、教学重点&难点1. 教学重点算法的概念和基本特性的理解。
一些简单算法的示例讲解，如排序算法中的冒泡排序原理。
2. 教学难点如何让学生理解算法的有穷性在复杂算法中的体现。
引导学生从生活中发现算法的影子，将抽象的算法概念与实际联系起来。
四、教学方法1. 讲授法：直接讲解算法的概念、特性等基础知识。
2. 实例演示法：通过一些简单的算法实例，如计算1到100的和的算法，在黑板上或者借助PPT演示算法的步骤，让学生更直观地看到算法是如何工作的。
3. 讨论法：提出一些与算法相关的生活场景，如安排课程表的算法，让学生分组讨论，激发他们的思考能力。
五、教学过程1. 算法概念导入同学们，咱今天开始学习一个超级有趣又超级重要的东西，那就是算法。
你们知道吗？算法就像是一个超级聪明的小秘书，它知道怎么一步一步地把一件事情做好。
比如说，你们早上起床穿衣服，先穿什么后穿什么，这其实就是一个小算法。
如果顺序错了，可能就会很别扭。
算法呢，简单说就是为了解决一个问题而采取的一系列步骤。
就像做数学题，有解题的步骤一样。
我来举个更具体的例子。
假如你要计算1+2+3+…+100，你会怎么算呢？有的同学可能会一个一个加，那这就是一种算法，不过这是比较笨的算法。
还有一种聪明的算法，就是用等差数列求和公式，这也是一种算法。
2. 算法特性讲解那算法有啥特性呢？首先是确定性。
这就好比你按照菜谱做菜，菜谱上写得明明白白，放多少盐，炒多久，不能含糊。
算法的每一步都得是确定的，不能一会儿这样一会儿那样。
再说说有穷性。
你们想啊，如果一个算法永远都算不完，那就没有意义了。
就像你数星星，要是一直数下去没个头，那就不叫算法了。
