第四讲递推关系的建立及其迭代解法

n!
n
x ＋ x － …＋(－1)n x ＋ …] [1－
1! 2! n!
1
1!
2
2!
n! n
＝xA(x)＋e-x
3.1.4 举例
所以A(x)＝ e
1 −x
1− x
2 n
＝[1－ x ＋ x － …＋(－1)n x ＋…] ×
1! 2! n!
Dn
∞
(1＋x＋x2＋x3＋ )
n
n 1 1 1 1 x ＝∑ − + − ⋯ + (−1) + ⋯n ! 1! 2! n! n = 0 0! n!
例3.1.6 做集合{1,2,…,n}的全排列，但 元素1不排在第1位，元素2不排在第2 位，…，元素n不排在第n位，这样的 全排列称为集合{1,2,…,n}的错排 错排，集 错排 合{1,2,…,n}的错排的个数简称为集合 {1,2,…,n}的错排数 错排数，记作Dn 错排数 解 集合{4,3,2,5,6,…,n,1}的错排?
随堂作业
3.1.4 举例
例3.1.5(Hanoi问题) 现有A,B,C三根立 柱以及n个大小不等的中空圆盘，这些 圆盘按上小下大套在A柱上，需要把圆 A 盘从A柱搬到C柱，并保持原来的顺序 不变，要求每次只能从一根柱上拿一个 圆盘放在另一根柱上，且不允许大盘放 在小盘上，求至少需要搬动的次数an
3.1.4 举例
3.1.4 举例
则A(x)＝D0＋D1 x ＋D2 x ＋…＋Dn x ＋ … D [D ( 1) [2D ( 1) ＝D0＋[D0＋(－1)1] x ＋[2D1＋(－1)2] x ＋ … ＋[nDn-1＋(－1)n] x ＋ …
1 2
1
2

递推算法典型例题一、教学目标1、由浅入深，了解递推算法2、掌握递推算法的经典例题二、重点难点分析1、重点：递推关系的建立2、难点：如何将所求问题转化为数学模型三、教具或课件微机四、主要教学过程(一)引入新课客观世界中的各个事物之间或者一个事物的内部各元素之间，往往存在(隐藏)着很多本质上的关联。

我们设计程序前．应该要通过细心的观察、丰富的联想、不断的尝试推理．尽可能先归纳总结出其内在规律，然后再把这种规律性的东西抽象成数学模型，最后再去编程实现。

递推关系和递归关系都是一种简洁高效的常见数学模型，我们今天先来深入研究一下递推算法如何实现。

(二)教学过程设计递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。

这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，这样的问题可以采用递推法来解决。

从已知条件出发，逐步推出要解决的问题，叫顺推；从问题出发逐步推到已知条件，此种方法叫逆推。

无论顺推还是逆推，其关键是要找到递推式。

这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。

递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。

递推算法避开了通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。

一般说来可以将递推算法看成是一种特殊的迭代算法。

（在解题时往往还把递推问题表现为迭代形式，用循环处理。

所谓“迭代”，就是在程序中用同一个变量来存放每一次推算出来的值，每一次循环都执行同一个语句，给同一变量赋以新的值，即用一个新值代替旧值，这种方法称为迭代。

）1．递推关系的定义和求解递推关系的方法有一类试题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成如下简捷的递推关系式：f n=g(f n-1)或者f n-1=g'(f n)这样就在数的序列中，建立起后项和前项之间的关系。

min{m , n}1 i 0
s 1=
(n i ) * (m i )
2.长方形和正方形的个数之和s 宽为1的长方形和正方形有m个，宽为2的长方形和正方形有 m-1个，┉┉，宽为m的长方形和正方形有1个； 长为1的长方形和正方形有n个，长为2的长方形和正方形有n1个，┉┉，长为n的长方形和正方形有1个； 根据乘法原理
【参考程序】 #include<iostream> using namespace std; int main() { int f[1001][2],n,i,x; cin>>n; f[1][1]=1;f[1][0]=9; for(i=2;i<=n;i++) { x=f[1][0]; if(i==n)x--; f[i][0]=(f[i-1][0]*x+f[i-1][1])%12345; f[i][1]=(f[i-1][1]*x+f[i-1][0])%12345; } cout<<f[n][0]; return 0; }
下面是输入n，输出x1~xn的c++程序： #include<iostream> using namespace std; int main() { int n,i,j,a[101]; cout<<"input n:"; //输入骨牌数 cin>>n; a[1]=1;a[2]=2; cout<<"x[1]="<<a[1]<<endl; cout<<"x[2]="<<a[2]<<endl; for (i=3;i<=n;i++) //递推过程 { a[i]=a[i-1]+a[i-2]; cout<<"x["<<i<<"]="<<a[i]<<endl; } } 下面是运行程序输入 n=30，输出的结果： input n: 30 x[1]=1 x[2]=2 x[3]=3 ........ x[29]=832040 x[30]=1346269

(6.2.4)
如果方程组（6.2.4）有唯一解b'1 , b'2 ,, b'k ，这说明可以找到 这k个常数，使得
解. 考察方程组（6.2.4），它的系数行列式为这是著名的 Vandermonde行列式.因为 q1 , q2 ,, qk 互不相等，所以该行 列式不等于零，这也就是说方程组（6.2.4）有唯一解.
求解递推关系的常用方法 （1）迭代归纳法； （2）特征根法； （3）生成函数法；
例6.1.1（爬楼梯问题）一个小孩要爬上n阶 楼梯，每次可上一阶或两阶，问上n阶有多 少种上法？ 解：
显然登上1阶台阶有1种方法，登上2台阶有2种方法， f(1）=1，f(2)=2 ,称为递推关系的初始条件。 设有f(n) 种方法，要登上这n阶台阶，最后迈上一个台 阶或两个台阶完成. （1）若最后是迈上一个台阶完成的，则前面登上了n1阶台阶，有f(n-1) 种方法； （2）若最后是迈上两个台阶完成的，则前面登上了n2阶台阶，有f(n-2) 种方法，根据加法原理有递推关系： f(n)=f(n-1)+f(n-2) .
n n 1 n 1 n
例6.2.2
f (n) 2 f (n 1) 3 f (n 2) f (0) 1, f (1) 1 先求通解，特征方程是： x 2x 3 0
•
关于微分方程求解的已知结论:
1. 对于4次以及4次以下的方程,目前已有代数解法.(在复数 域内求解) 2. 阿贝尔定理: 5次以及更高次的代数方程没有一般的代数解法.
例6.2.1 求Fibonacci数的递推关系
n2 f (n) f (n 1) f (n 2) f (0) 1, f (1) 1 解：特征方程为x 2 x 1 0, 1 5 1 5 两个特征根分别是：x1 , x2 , 2 2 1 5 n 1 5 n 因此通解f (n) c1 ( ) c2 ( ) 2 2