第一讲递推与迭代.ppt

第 1 讲;主要内容;1.1 递推概述;1. 实施递推的步骤 (1) 确定递推变量 (2) 建立递推关系 (3) 确定初始（边界）条件 (4) 对递推过程进行控制 ; 2. 递推算法框架描述;（2） 简单逆推算法 逆推即从后往前推,从已得的规模为n，n-1， …，i+1的一系列解，推出问题规模为 i的解，直至得到规模为1的解。 简单逆推算法框架描述： f(n—i+1)=初始值； /* 确定初始值 */ for(k=i;k=1;k--) f(k)=递推关系式；/* 实施递推 */ printf(f(1))； /* 输出解f(1) */ ; 设递推的二维数组为f(k,j)，1≤k≤n,1≤j≤m。 二维数组顺推算法框架描述： f(1,1—m)=初始值； /* 赋初始值 */ for(k=2;k=n;k++) for(j=1;j=m;j++) f(k,j)=递推关系式； /* 实施递推 */ printf(f(n,m))； /* 输出解f(n,m) */; 当递推关系包含两个或两个以上关系式时，通常应用多关系分级递推算法求解。 （4） 多关系分级递推算法 f(1—i-1)=初始值； /* 赋初始值 */ for(k=i;k=n;k++) if(条件1) f(k)=递推关系式1； /* 据递推关系1递推 */ if(条件2) f(k)=递推关系式2； /* 据递推关系2递推 */ …… if(条件m) f(k)=递推关系式m； /* 据递推关系m递推 */ printf(f(n))； /* 输出解f(n) */;1.2 递推数列;递推过程描述： a=2;b=3; * 为递推变量a,b赋初值 */ for(k=1;k=n;k++) {if(ab) {f[k]=a;a=a*2;}/* 用a给f[k]赋值 */ else {f[k]=b;b=b*3;}/* 用b给f[k]赋值 */ } 在这一算法中，变量a,b是变化的，分别代表2的幂与3的幂。;1.2.2 双关系递推数列;if(2*m(p2)3*m(p3)) { m(i)=2*m(p2)+1;p2++;} if(2*m(p2)3*m(p3)) { m(i)=3*m(p3)+1;p3++;} 特别注意：两队列若出现相等时，给m数组赋值后，两排头都要增1。 if(2*m(p2)==3*m(p3)) { m(i)=2*m(p2)+1; p2++; p3++; /* 为避免重复项，P2，p3均须增1 */ } ;1.3.1 猴子爬山问题 【例1.4】 一个顽猴在一座有30级台阶的小山上爬山跳跃，猴子上山一步可跳1级，或跳3级，试求上山的30级台阶有多少种不同的爬法。 1. 递推算法设计 一般地有递推关系： f(k)=f(k-1)+f(k-3) （k3） 初始条件有: f(1)=1； 即1=1。 f(2)=1； 即2=1+1。 f(3)=2； 即3=1+1+1；3=3。; int k,n; long f[1000]; printf(请输入台阶总数n:); scanf(%d,n); f[1]=1;f[2]=1;f[3]=2; /* 数组元素赋初值 */ for(k=4;k=n;k++) f[k]=f[k-1]+f[k-3]; /* 按递推关系实施递推 */ printf(s=%ld,f[n]);;3. 问题引申 把问题引申为爬山n级，一步有m 种跨法，一步跨多少级均从键盘输入。 (1） 分级递推算法设计 设爬山t台阶级的不同爬法为f(t),设从键盘输入一步跨多少级的m个整数分别为x(1), x(2), …, x(m) (约定x(1)x(2)…x(m)n)。 这里的整数x(1), x(2), …, x(m)为键盘输入，事前并不知道，因此不能在设计时简单地确定f(x(1)),f(x(2)),…。 事实上，可以把初始条件放在分级递推中求取，应用多关系分级递推算法（6）完成递推。; (2) 探讨f(t)的递推关系 当tx(1)时，f(t)=0；f(x(1))=1。（初始条件） 当x(1)t≤x(2)时，第1级递推：f(t)=f(t-x(1))； 当x(2)t≤x(3)时，第2级递推：f(t)=f(t-x(1))+f(t-x(2))； …… 一般地，当x(k