算法设计与分析实用教程-电子教案-杨克昌 第3章 递推

教学要求 了解递推算法的概念与各类递推设计要领 应用递推算法求解典型的数列与数阵案例 本章重点 对某些实际问题设计多种递推算法 对某些递推算法进行改进与优化,第 3 章 递 推,3.1 递推概述,1. 递推的概念 (1) 递推是利用问题本身所具有的递推关系求解问题的一种方法 ，是在命题归纳时，可以由nk,n1的情形推得 n 的情形。 (2) 递推算法的基本思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法充分利用了计算机的运算速度快和不知疲倦的特点，从头开始一步步地推出问题最终的结果。 (3) 一个有规律的序列的相邻位置上的项之间通常存在着一定的关系，可以借助已知的项，利用特定的关系逐项推算出它的后继项的值，直到找到所需的那一项为止。,2. 递推关系,递推算法的首要问题是得到相邻的数据项之间的关系，即递推关系。 递推关系是一种高效的数学模型，是递推应用的核心。 递推关系不仅在各数学分支中发挥着重要的作用，由它所体现出来的递推思想在各学科领域中更是显示出其独特的魅力。,3. 递推的实施步骤,（1）确定递推变量 递推变量可以是简单变量，也可以是一维或多维数组。 （2）建立递推关系 递推关系是递推的依据，是解决递推问题的关键。 （3）确定初始（边界）条件 根据问题最简单情形的数据确定递推变量的初始（边界）值，这是递推的基础。 （4）对递推过程进行控制 递推过程控制：递推在什么时候结束，满足什么条件结束。,4. 递推算法框架描述,（1） 简单顺推算法 顺推即从前往后推，从已求得的规模为1,2,i-1的一系列解，推出问题规模为i的解，直至得到规模为n的解： f(1i-1)=； / 确定初始值 for(k=i;k； / 根据递推关系实施顺推 print(f(n)； / 输出n规模的解f(n),（2） 简单逆推算法 逆推即从后往前推，从已求得的规模为n,n1,i+1的一系列解，推出问题规模为i的解，直至得到规模为1的解： f(ni+1)=； / 确定初始值 for(k=i;k=1;k-) f(k)=； / 实施逆推 print(f(1)； （3）较复杂的递推问题需设置多重循环递推。,（4） 多关系分级递推算法 当递推关系包含两个或两个以上关系式时，通常应用多关系分级递推算法求解。 f(1：i-1)=； / 赋初始值 for(k=i;k) f(k)=； / 根据关系1递推 if() f(k)=； / 根据关系m递推 print(f(n)； / 输出n规模的解f(n),3.2 递推数列,3.2.1 双关系递推数列 设集合M定义如下: (1) 1M (2) xM = 2x+1M,5x-1M (3) 再无其它的数属于M。 试求集合M元素从小到大排列所得序列的第n（n10000）项与前n项之和。,1. 递推设计要点,该题有2x+1,5x-1两个递推关系，设置数组m(i)存储M元素从小到大排列序列的第i项，显然m(1)=1，这是递推的初始条件。 同时设置两个队列： 2*m(p2)+1, p2=1,2,3, 5*m(p5)-1, p5=1,2,3, 这里用p2表示2x+1这一队列的下标，用p5表示5x-1这一队列的下标。 从两队列中选一排头，通过比较选数值较小者送入数组m中。所谓“排头”就是队列中尚未选入m的最小的下标。 若2*m(p2)+15*m(p5)-1, 则m(i)=5*m(p5)-1;下标p5增1； 若2*m(p2)+1=5*m(p5)-1, 则m(i)=5*m(p5)-1;下标p2与p5同时增1。,2. 递推设计描述,scanf(“%ld“,3.2.2 振动数列 （1） 递推产生各项 根据递推式，在i循环中据项序号i(2n)为奇或偶作不同递推: mod(i,2)=0(即i为偶数)时,a(i)=a(i/2)+2 mod(i,2)=1(即i为奇数)时,a(i)=a(i+1)/2)-a(i-1)/2) （2） 统计平台数与波峰数 在对项ai（m+1in-1）操作时标记j=i,在条件(ai=ai+1)循环中项号i实施增1： 若ij，表明存在i-j+12项相等，应用p+统计平台数。 若ai同时大于其前项aj-1与后项ai+1，即为一波峰，应用k+统计波峰数。,3.2.3 分数数列 设置数组c(i)表第i项的分子,d(i)表第i项的分母(均为整数)。 (1) 初始值为: c(1)=1，d(1)=2；c(2)=3，d(2)=5。 (2) 置k在区间(c(i-1),d(i-1)取值，k分别与d(1),d(2), .d(i-1)比较，若存在相同，则k增1后再比较；若没有相同的，则产生第i项，作赋值: c(i)=k，d(i)=k+i。 (3) 比较求最大项： c(i)/d(i)c(kmax)/d(kmax) c(i)*d(kmax)c(kmax)*d(i) 把分数比较转化为整数比较是适宜的.,3.3 超级素数搜索,定义m位超级素数： (1) m（m1）位整数x为素数； (2) 从高位开始，去掉1位后为m-1位素数；去掉2位后为m-2位素数；去掉m-1位后为1位素数。 例如素数137是一个3位超级素数，因去高1位得37，去高2位得7都是素数。而素数107不是超级素数，因去高1位得7不是一个2位素数。 输入m(1m10)，统计m位超级素数的个数，并输出其中最大的m位超级素数。,根据超级素数的定义， m（m1）位超级素数去掉高位数字后是m-1位超级素数。一般地k(k=2,3,m)位超级素数去掉高位数字后是k-1位超级素数。 在已求得g个k-1位超级素数ai(i=1,2,g)时，在ai的高位加上一个数字j(j=1,2,9)，得到9*g个k位候选数f=j*ek+ai,(ek=10k-1),只要对这9*g个k位候选数检测即可。这就是从k-1递推到k的递推关系。 注意到超级m（m1）位素数的个位数字必然是3或7，则得初始（边界）条件： a1=3,a2=7,g=2；,1. 递推设计要点,2. 递推设计描述,scanf(“%d“,3.4 数阵与网格,3.4.2 方格网交通线路 某城区的方格交通网如图所示，城区中一座山占据了交通网中(3,2)、(4,2)与(4,3)这三个交叉点尚未开通，另有（2,3）至（2,4）与（6,4）至（7,4）的两条打“×”路段正在维护，禁止通行。 试统计从始点(0,0)到终点(m,n)的不同最短路线(路线中各段只能从左至右、从下至上)的条数。,设f(x,y)(0xm,0yn) 为从始点(0,0)到点(x,y)的不同最短路线的条数。 （1） 递推关系: f(x,y)=f(x-1,y)+f(x,y-1) （2） 边界条件 f(x,0)=1 (0xm); f(0,y)=1 (0yn) （3） 障碍处理 城区的一座山所占据网中的(3,2)、(4,2)、(4,3)三个交叉点，可令f(3,2)= f(4,2)= f(4,3)=0; 从（2,3）至（2,4）段禁止通行，则对f(2,4)的赋值只有f(1,4)，即 f24=f14; 同理 f74=f73;,1. 递推设计要点,2. 递推设计描述,scanf(“%d,%d“,3.5 六六顺数组,应用二项式定理证明以下的递推性质: 1) 当k为奇数时 = (1) 2) 当k为偶数时 = (2),3.6 猴子爬山,1. 问题提出 一个顽猴在一座有30级台阶的小山上爬山跳跃，猴子上山一步可跳1级，或跳3级，试求上山的30级台阶有多少种不同的爬法。 设爬k级台阶的不同爬法为f(k)种。 2. 初始条件 f(1)=1；即1=1 f(2)=1；即2=1+1 f(3)=2；即3=1+1+1；3=3 3. 递推关系 f(k)=f(k-1)+f(k-3) （k3）,4递推描述 scanf(“%d“,3.7 整数划分,正整数s（简称为和数）的划分（又称分划）是把s分成为若干个正整数（简称为零数或部分）之和，划分式中允许零数重复，且不记零数的次序。 例如，s=5有7个不同的划分式： 1+1+1+1+1；1+1+1+2；1+1+3；1+2+2；1+4；2+3；5。 对给定的正整数s，试求s的不同的划分式个数？并展示出所有这些划分式。,设n的“最大零数不超过m”的划分式个数为q(n,m)。 递推关系： q(n,m)=q(n,m-1)+q(n-m,m) (1mns) 其中 q(n-m,m)=q(n-m,n-m) （若n-mm） 注意到n等于n本身也为一个划分式，则有 q(n,n)=1+q(n,n-1) 递推初始条件： q(n,1)=1 q(1,m)=1 (m=1,2,s，因整数1只有一个划分),3.7.1 整数划分式的个数,难点在于展示出所有这些划分式，为避免重复，约定划分式中零数按不降排列。 先对和数k较小时的划分式作观察归纳： k=2：1+1；2 k=3：1+1+1；1+2；3 k=4：1+1+1+1；1+1+2；1+3；2+2；4 k=5：1+1+1+1+1；1+1+1+2；1+1+3；1+2+2；1+4；2+3；5 由以上各划分看到，除和数本身k=k这一特殊划分式外，其它每一个划分式至少为两项之和。,3.7.2 整数划分式的实现,递推设计要点： 设置三维数组a，a(k,j,i)为和数k的第j式的第i个数。 初始条件： a(2,1,1)=1；a(2,1,2)=1; a(2,2,1)=2。 递推关系： （1）在所有和数k-1的划分式前加一个零数“1”都是和数k的划分式。 （2）和数k-1的划分式的前两个零数作比较，如果第1个零数x1小于第2个零数x2，则把第1个零数加1后成为和数k的划分式。,把三维数组a(k,j,i)改进为二维数组a(j,i)。二维数组a(j,i)表示和数是k-1的已有划分式。 (1) 把所有a(j,i)依次存储到a(j,i+1)，加上第一项a(j,1)=1；这样完成在k-1的所有划分式前加1的操作，转化为k的划分式。 (2) 对已转化的u个划分式逐个检验，若其第2个数小于第3个数（相当于k-1时的第1个数小于第2个数），则把第2个数加1，去除第一个数后，作为k时增加的一个划分式，为第t（t从u开始，每增加一个划分式，t增1）划分式。,3.7.3 实现整数划分式的优化,3.8 递推与迭代 迭代是一种不断用变量的旧值推出新值的过程，在数学中出现过各种各样技巧性很强的迭代法。 在迭代过程中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。如何从变量的前一个值推出下一个值的公式(或关系)称为迭代关系式。 在前面许多案例求解的算法设计中常用到的计数n=n+1(或n+;)，对k的求和s=s+k(或s+=k;)，这些都是用变量n、s的新值取代旧值的过程，这些操作都是迭代。 从以上“杨辉三角”与“水手分椰子”的求解可见,递推常使用数组来完成，而传统迭代使用简单变量来完成。,递推也是根据递推关系式不断推出新值的过程。我们知道，数组是由具有同名同属性的数据组成的，从这个意义上说，递推的实质就是迭代，或者说递推可归纳为一种广义的迭代,而传统迭代则是一种应用简单变量的递推。 在实际案例处理中，很多迭代过程可以应用递推来解决，反过来，很多递推过程也可以应用迭代来解决。 比较递推与迭代，两者的时间复杂度是相同的。所不同的是，递推往往设置数组，而传统迭代只要设置迭代的简单变量即可。 递推过程中数组变量带有下标，比传统迭代更为清晰。 因为递推中应用了数组，因而保留了递推过程中的中间数据。而传统迭代求解中并不保留迭代过程中的中间数据。,第3章作业,习题3: 1, 2, 3, 4, 7,第3章上机,