递推和递归思想ppt课件

1、递推是计算机数值计算中的一个重递推是计算机数值计算中的一个重要算法，可以将复杂的运算化为若干重复要算法，可以将复杂的运算化为若干重复的简单运算，充分发挥计算机长于重复处的简单运算，充分发挥计算机长于重复处理的特点，现举一例理的特点，现举一例6.2 递 推分析上式分析上式. 当当 i = 5 时，时，fish 5 表示表示 E 醒来所看到的鱼数，醒来所看到的鱼数，该数应满足被整除后余，即该数应满足被整除后余，即fish 5 % 5 = 1 2. 当当 i = 5 时，时，fish i-1 表示表示 D 醒来所看到的鱼数，醒来所看到的鱼数，这个数既要满足这个数既要满足fish 4 = fish 5

2、 * 5 / 4 + 1 又要满足又要满足fish 4 % 5 = 1显然，显然，fish 4 不能不是整数，这个结论同样可以用不能不是整数，这个结论同样可以用至至 fish 3 , fish 2 和和 fish 1 3 . 按题意要求按题意要求 5 人合伙捕到的最少鱼数，可以从人合伙捕到的最少鱼数，可以从小往大枚举，可以先让小往大枚举，可以先让 E 所看到的鱼数最少为所看到的鱼数最少为 6 条，即条，即 fish 5 初始化为初始化为 6 来试，之后每次增加来试，之后每次增加 5 再试，直至递推到再试，直至递推到 fish 1 得整数且除以得整数且除以 5 之后的之后的余数为余数为 1。根据

3、上述思路，我们可以构思如下的程序框图：根据上述思路，我们可以构思如下的程序框图： 定义数组 fish6，并初始化为 1； 定义循环控制变量 i，并初始化为 0。 输出计算结果 fish1至 fish5 do while(i=1); fish5=fish5+5; / .1 for ( i=4; i=1; i- ) / .2 fishi+1%4 != 0 true false break; /退出 for 循环 fishi = fishi+1*5/4+1; 该图可分为三部分该图可分为三部分(1) 是说明部分：包含定义数组是说明部分：包含定义数组 fish6，并初始化为，并初始化为 1 和定义循环控

4、制变量和定义循环控制变量 i，并初始化为，并初始化为 0。(2) 是是 do.while 直到型循环，其循环体又含两块：直到型循环，其循环体又含两块：(2).1 是枚举过程中的是枚举过程中的 fish5 的初值设置，一开始的初值设置，一开始 fish5=1+5; 以后每次增以后每次增 5。(2).2 是一个是一个 for 循环，循环，i的初值为的初值为 4，终值为，终值为 1，步长，步长为为 -1，该循环的循环体是一个分支语句，假设，该循环的循环体是一个分支语句，假设 fishi+1不能被不能被 4 整除，则跳出整除，则跳出 for 循环运用循环运用 break 语句语句;）否则，从）否则，从

5、 fishi+1 算出算出fishi。当由当由 break 语句让程序退出循环时，意味着某语句让程序退出循环时，意味着某人看到的鱼数不是整数，当然不是所求，必须令人看到的鱼数不是整数，当然不是所求，必须令fish 5 加加 5 后再试，即重新进入直到型循环后再试，即重新进入直到型循环 do while 的循环体。的循环体。当着正常退出当着正常退出 for 循环时，一定是控制变量循环时，一定是控制变量 i 从初值从初值 4，一步一步执行到终值，一步一步执行到终值 1，每一步的鱼数均，每一步的鱼数均为整数，最后为整数，最后 i = 0，表示计算完毕，且也达到了退，表示计算完毕，且也达到了退出直到型

6、循环的条件。出直到型循环的条件。(3) 输出计算结果输出计算结果/*/* 程程 序序 名：名：6_1.cpp五人合伙捕鱼）五人合伙捕鱼） */* 作作 者：者：wuwh */* 编制时间：编制时间：2019年年10月月2日日 */* 主要功能：递推算法的实现主要功能：递推算法的实现 */*#include / 预编译命令预编译命令using namespace std;int main() /主函数主函数 int fish6=1,1,1,1,1,1; / 整型数组，记录每人醒来后看到的鱼数整型数组，记录每人醒来后看到的鱼数 int i=0; do fish5=fish5+5; / 让让E看到的

7、鱼数增看到的鱼数增5。 for (i=4; i=1; i-) if ( fishi+1%4 !=0 )break; / 跳出跳出for循环循环elsefishi=fishi+1*5/4+1;/ 计算第计算第i人看到的鱼数人看到的鱼数 while( i=1 ); / 当当 i=1 继续做继续做do循环循环 / 输出计算结果输出计算结果 for (i=1; i=5; i+)cout fishi 1 时，时，A 的取值即的取值即 C 的值，而的值，而 C 的值即的值即 E 的值，为了求得的值，为了求得 E 的值，需要先求出的值，需要先求出 D 的值。的值。D 值值 fact( n-1 ) 乘以乘以

8、n 即为即为 E 的值。的值。A fact(n)Bfact(1)=1Cn1n=1Dfact(n-1)En*fact(n-1)与结点可能有多个相关联的点，这时可描述为下图与结点可能有多个相关联的点，这时可描述为下图A 结点的值最终为结点的值最终为 D 的值，但为了求的值，但为了求 D 需先求需先求 B 和和 C。从图上看。从图上看, 先求左边的点才能求最右边的点的先求左边的点才能求最右边的点的值，我们约定最右边值，我们约定最右边 D 点的值就是点的值就是 A 结点的值。结点的值。ABDC 下面我们以下面我们以 3！为例来画与或结点图，目的是体会！为例来画与或结点图，目的是体会 递归的含义。递归的

9、含义。C = 1D = 2*C = 2B = D = 2E = 3*B = 3*2 = 6A = E = 61=1131Bfact(2)3*fact(2)fact(3)Cfact(1)D2*fact(1)AE21下面画出了调用和返回的递归示意图下面画出了调用和返回的递归示意图 Bfact(2)fact(2)=2*fact(1)=2*fact(1)=2*1=2*1=2=2返回返回 DAfact(3)fact(3)=3*fact(2)=3*fact(2)=3*2=3*2=6=6E E返回返回 Cfact(1)=1调用调用调用调用从图可以想象：从图可以想象：欲求欲求 fact( 3 )，先要求，先要

10、求 fact( 2 )；要求；要求 fact( 2 ) 先求先求 fact( 1 )。就象剥一颗圆白菜，从外向里，一层层剥。就象剥一颗圆白菜，从外向里，一层层剥下来，到了菜心，遇到下来，到了菜心，遇到 1 的阶乘，其值为的阶乘，其值为1，到达了，到达了递归的边界。然后再用递归的边界。然后再用 fact( n )=n*fact( n-1 ) 这个普这个普遍公式，从里向外倒推回去得到遍公式，从里向外倒推回去得到 fact( n ) 的值。的值。为了把这个问题说得再透彻一点。我们画了如下的流为了把这个问题说得再透彻一点。我们画了如下的流程图：程图： 31 fact(3) 真真 假假 调调用用 fac

11、t(2) 计计算算 3*fact(2) fact(2) fact(1) 21 真真 假假 调调用用 fact(1) 计计算算 2*fact(1) 11 真真 假假 fact(1) 1 返返回回 返返回回 为了形象地描述递归过程，将上图改画成下图为了形象地描述递归过程，将上图改画成下图 fact(3) 真真 假假 3=1 调调用用 fact(2) 真真 假假 假假 真真 2=1 1=1 fact(2)=2*fact(1) 返返回回 fact(3)=3*fact(2) 返返回回 调调用用 fact(1) fact(1) =1 返返回回 在这个图中在这个图中“内层与内层与“外层有着相同的结构。它们外

12、层有着相同的结构。它们之间之间“你中有我，我中有你你中有我，我中有你”，呈现相互依存的关系。，呈现相互依存的关系。为了进一步讲清递归的概念，将递归与递推做一比较。为了进一步讲清递归的概念，将递归与递推做一比较。仍以求阶乘为例。仍以求阶乘为例。递推是从已知的初始条件出发，逐次去求所需要的阶递推是从已知的初始条件出发，逐次去求所需要的阶乘值。乘值。如求如求 3！初始条件初始条件 fact( 1 ) = 1fact( 2 ) = 2 * fact( 1 ) = 2fact( 3 ) = 3 * fact( 2 ) = 6这相当于从菜心这相当于从菜心“推到外层。推到外层。 递归算法的出发递归算法的出发

13、点不放在初始条件上，放在求解的目标上，从所求点不放在初始条件上，放在求解的目标上，从所求的未知项出发逐次调用本身的求解过程，直到递归的未知项出发逐次调用本身的求解过程，直到递归的边界即初始条件）。就本例而言，读者会认为的边界即初始条件）。就本例而言，读者会认为递归算法可能是多余的，费力而不讨好。但许多实递归算法可能是多余的，费力而不讨好。但许多实际问题不可能或不容易找到显而易见的递推关系，际问题不可能或不容易找到显而易见的递推关系，这时递归算法就表现出了明显的优越性。下面我们这时递归算法就表现出了明显的优越性。下面我们将会看到，递归算法比较符合人的思维方式，逻辑将会看到，递归算法比较符合人的思

14、维方式，逻辑性强，可将问题描述得简单扼要，具有良好的可读性强，可将问题描述得简单扼要，具有良好的可读性，易于理解性，易于理解. 许多看来相当复杂，或难以下手的许多看来相当复杂，或难以下手的问题，如果能够使用递归算法就会使问题变得易于问题，如果能够使用递归算法就会使问题变得易于处理。下面举一个尽人皆知的例子哈诺处理。下面举一个尽人皆知的例子哈诺Hanoi塔塔问题。问题。故事：故事：相传在古代印度的相传在古代印度的 Bramah 庙中，有位僧人整天把庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把三根柱子上的金盘倒来倒去，原来他是想把64个一个一个比一个小的金盘从一根柱子上移到另一根柱子

15、上个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中恪守下述规则：每次只允许移动一去。移动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得落在小盘上面。有人会觉得这很只盘，且大盘不得落在小盘上面。有人会觉得这很简单，真的动手移盘就会发现，如以每秒移动一只简单，真的动手移盘就会发现，如以每秒移动一只盘子的话，按照上述规则将盘子的话，按照上述规则将64只盘子从一个柱子移只盘子从一个柱子移至另一个柱子上，所需时间约为至另一个柱子上，所需时间约为5800亿年。亿年。 怎样编写这种程序？思路上还是先从最简单的情况分怎样编写这种程序？思路上还是先从最简单的情况分析起，搬一搬看，慢慢理出思路。析

16、起，搬一搬看，慢慢理出思路。1、在、在A柱上只有一只盘子，假定盘号为柱上只有一只盘子，假定盘号为 1，这时，这时只需将该盘从只需将该盘从 A 搬至搬至 C，一次完成，记为，一次完成，记为move 1# from A to C (演示演示)ABC12、在、在 A 柱上有二只盘子，柱上有二只盘子，1 为小盘，为小盘，2 为大盘。为大盘。第第1步将步将1号盘从号盘从A移至移至B，这是为了让，这是为了让 2号盘能动；号盘能动；第第2步将步将 2 号盘从号盘从A 移至移至 C；第第3步再将步再将 1 号盘从号盘从 B 移至移至 C；这三步记为演示）：这三步记为演示）：ABC21move 1# from

17、A to B;move 2# from A to C;move 1# form B to C;3、在、在A柱上有柱上有3只盘子，从小到大分别为只盘子，从小到大分别为1号，号，2号，号，3号号第第1步步 将将1号盘和号盘和2号盘视为一个整体；先将二者作号盘视为一个整体；先将二者作为整体从为整体从A移至移至B，给，给3号盘创造能够一次移至号盘创造能够一次移至C的机会。的机会。这一步记为这一步记为 move( 2, A, C, B) 意思是将上面的意思是将上面的2只盘子作为整体从只盘子作为整体从A借助借助C移至移至B。第第2步步 将将3号盘从号盘从A移至移至C，一次到位。记为，一次到位。记为 mov

18、e 3# from A to C第第3步步 处于处于B上的作为一个整体的上的作为一个整体的2只盘子，再移至只盘子，再移至C。这一步记为。这一步记为 move( 2, B, A, C)意思是将意思是将2只盘子作为整体从只盘子作为整体从B借助借助A移至移至C。所谓借助是什么意思，等这件事做完了不言自明。所谓借助是什么意思，等这件事做完了不言自明。move (3, A, B, C)move (2, A, C, B)move (1, A, B, C)move (2, B, A, C)ABC213演示：移动演示：移动3 3个盘子的分解个盘子的分解move (3, A, B, C)move (2, A,

19、C, B)move (1, A, B, C)move (1, A, C, B)move (1, C, A, B)move (1, A, B, C)move (2, B, A, C)move (1, B, C, A)move (1, B, A, C)move (1, A, B, C)ABC2134、从题目的约束条件看，大盘上可以随便摞小、从题目的约束条件看，大盘上可以随便摞小盘，相反则不允许。在将盘，相反则不允许。在将1号和号和2号盘当整体从号盘当整体从A移至移至B的过程中的过程中 move(2, A, C, B) 实际上是分实际上是分解为以下三步解为以下三步第第1）.1步：步：move 1#

20、form A to C;第第1）.2步：步：move 2# form A to B;第第1）.3步：步：move 1# form C to B;经过以上步骤，将经过以上步骤，将 1 号和号和 2 号盘作为整体号盘作为整体从从 A 移至移至 B，为，为 3 号盘从号盘从 A 移至移至 C 创造了条创造了条件。同样，件。同样，3号盘一旦到了号盘一旦到了 C，就要考虑如何，就要考虑如何实现将实现将 1 号和号和 2 号盘当整体从号盘当整体从 B 移至移至 C 的过的过程了。实际上程了。实际上 move( 2, B, A, C ) 也要分解为也要分解为三步：三步：第第3）.1步：步：move 1# f

21、orm B to A;第第3）.2步：步：move 2# form B to C;第第3）.3步：步：move 1# form A to C;5、看、看 move(2, A, C, B) 是说要将是说要将 2 只盘子从只盘子从 A 搬至搬至 B，但没有，但没有 C 是不行的，因为第是不行的，因为第1）.1步就要将步就要将 1# 盘从盘从 A 移到移到 C，给，给2 #盘创造条件盘创造条件从从 A 移至移至 B，然后再把，然后再把 1# 盘从盘从 C 移至移至 B。看。看到这里就能明白借助到这里就能明白借助 C 的含义了。因此，在的含义了。因此，在构思搬移过程的参量时，要把构思搬移过程的参量时，

22、要把 3 个柱子都用上。个柱子都用上。6、定义搬移函数、定义搬移函数 move(n, A, B, C)，物理意义是，物理意义是将将 n 只盘子从只盘子从 A 经经 B 搬到搬到 C输出n:A to Cmove(n-1,A,C,B)move(n-1,B,A,C)move(n,A,B,C)考虑到前面已考虑到前面已经研究过的经研究过的(1)(2)(3)步，可步，可以将搬移过程以将搬移过程用如下的与或用如下的与或结点图表示。结点图表示。这里用与或结点的含义是分解为这里用与或结点的含义是分解为(1)(2)(3)步。这步。这3步是相关的，相互依存的，而且是有序的，从左至步是相关的，相互依存的，而且是有序的

23、，从左至右执行。右执行。move(n, A, B, C) 分解为分解为3步步(1)move(n-1, A, C, B)理解为将上面的理解为将上面的n-1只盘子作为一只盘子作为一个整体从个整体从A经经C移至移至B；(2)输出输出n：A to C，理解为将，理解为将n号盘从号盘从A移至移至C，是直接，是直接可解结点；可解结点；(3)Move(n-1, B, A, C)理解为将上面的理解为将上面的n-1只盘子作为一只盘子作为一个整体从个整体从B经经A移至移至C。这里显然是一种递归定义，当着解这里显然是一种递归定义，当着解 move(n-1, A, C, B)时又可想到，将其分解为时又可想到，将其分解

24、为 3 步：步：第第1步：将上面的步：将上面的n-2只盘子作为一个整体从只盘子作为一个整体从A经经B到到C，move(n-2, A, B, C)；第第2步：第步：第n-1号盘子从号盘子从A直接移至直接移至B，即，即n-1:A to B；第第3步：再将上面的步：再将上面的n-2只盘子作为一个整体从只盘子作为一个整体从C经经A移移至至B，move(n-2, C, A, B)；下面，我们还是以下面，我们还是以3只盘子为例画出递归的与或图。只盘子为例画出递归的与或图。这个图很象一颗倒置着的树，结点这个图很象一颗倒置着的树，结点move(3, A, B, C)是树是树根，与结点是树的分枝，叶子都是直接可

25、解结点。根，与结点是树的分枝，叶子都是直接可解结点。输出1:A to C1:A to C输出3:A to Cmove(2,A,C,B)move(2,B,A,C)move(3,A,B,C)输出2:A to B2:A to B输出1:C to B1:C to B输出1:B to A1:B to A输出2:B to C2:B to C输出1:A to C1:A to Cmove(1,A,B,C) move(1,C,A,B) move(1,B,C,A) move(1,A,B,C) move(3,A,B,C) move(2,A,C,B) 输输出出 3: A to C move(2,B,A,C) move

26、(2,A,C,B) 调调用用 move(1,A,B,C) move(2,B,A,C) 调调用用 move(1,B,C,A) 返返回回 返返回回 调调用用 调调用用 返返回回 move(1,A,B,C) 输输出出 2: A to B move(1,C,A,B) move(1,B,C,A) 输输出出 2: B to C move(1,A,B,C) 输输出出 1: A to C 输输出出 1: B to A 输输出出 1: C to B 输输出出 1: A to C 4 1 3 2 5 7 6 调调用用 调调用用 返返回回 返返回回 调调用用 move (1,C,A,B) move (1,A,B,C) 输出输出 3: A to C 调用调用 move(1,C,A,B) 输出：输出：1: C to B 输出：输出：2: A to B move(1,C,A,B) 调用调用 move(1,A,B,C) 输出输出 1: A to C move(1,A,B,C) move(2,A,C,B) 调用调用 move(2,A,C,B) 调用调用 move(2,B,A,C) 调用调用 move(1,A