第五讲--递推与递归ppt课件.ppt

《第五讲--递推与递归ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五讲递推与递归主要内容递推及其应用递归及其应用第五讲递推与递归递推是通过数学推导，将复杂的运算化解为若干重复的简单运算，以充分发挥计算机擅长重复处理的特点。递归是将复杂的操作分解为简单操作的多次重复，一般用函数调用完成。递推关系是一种简洁高效的常见数学模型。如：Fibonacci数列问题。递推特点：在递推问题中，每个数据项都和它前面的若干个数据项（或后面的若干个数据项）有一定的关联，这种关联一般通过“递推关系式”表示。11.1递推递推过程：从初始的一个或若干个数据项出发，通过递推关系式逐步推进，从而得到最终结果。其中：初始的若干数据项称为“边界”。11.1递推11.

2、1递推例如：Fibonacci数列问题已知：F(1)=0，F(2)=1，若：n>2，则F(n)=F(n-1)+F(n-2)注意：1）每个数据项都和它前面的若干个数据项（或后面的若干个数据项）有一定的关联-----递推关系式。2）从初始的一个或若干数据项出发，通过递推关系式逐步推进，从而得到最终结果。11.1递推注意：3）递推必须有“边界”。4）解决递推类型问题有三个重点：如何建立正确的递推关系式；递推关系有何性质；递推关系式如何求解。基础，重点11.1递推按照推导问题的方向，递推分为：顺推法：从初始数据开始推理。例如：n=0时，n!=1；n>1时，n!=n*(n-1)

3、!倒推法：从结果数据开始推理。例如：n!=n*(n-1)!；边界：n=0，n!=1例1：猴子第1天摘下若干个桃子，当即吃了一半又一个。第2天又把剩下的桃吃了一半又一个，以后每天都吃前一天剩下的桃子的一半又一个，到第10天猴子想吃时，只剩下一个桃子。问：猴子第1天一共摘了多少桃子?分析：已知条件：第10天剩下1个桃子；隐含条件：每一次前一天的桃子个数等于后一天桃子的个数加1的2倍。逆向思维：从后往前推，可用倒推法求解。#includevoidmain(){inti,a=1;for(i=9;i>=1;i--)a=(a+1)*2;printf("a=%d

4、n",a);}例1：逆推法---求解猴子吃桃子例2：猴子分食桃子1)五只猴子采得一堆桃子，猴子彼此约定隔天早起后再分食。2)半夜里，一只猴子偷偷起来，把桃子均分成五堆后，发现还多一个，它吃掉这桃子，并拿走了其中一堆。3)第二只猴子醒来，又把桃子均分成五堆后，还是多了一个，它也吃掉这个桃子，并拿走了其中一堆。第三只，第四只，第五只猴子都依次如此分食桃子。问：五只猴子采得一堆桃子数最少应该有几个呢？逆推法算法分析：先要找第N只猴子和其面前桃子数的关系。如果从第1只开始往第5只找，不好找，但如果思路一变，从第N到第1去，可得出下面的推导式：第N只猴  第N只猴前桃子数目5 

5、    s5=x4         s4=s5*5/4+13         s3=s4*5/4+12         s2=s3*5/4+11         s1=s2*5/4+1通过递推，求出s1即可例2：猴子分食桃子---逆推法注意：其中的s1、s2、s3、s4、s5必须是整数//例2：猴子分食桃子---逆推法#includevoidmain(){intx,s,k,i;x=6;//最少的初值k=0;//整除标志while(k!=4){s=x;k=0;for(i=4;i>=1;i--){if(s%4==0)k++;elsebreak;s=s*5

6、/4+1;}x=x+5;}printf("s=%d",s);}11.1.2递推设计实例例11.1：母牛的故事问题描述：有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。编程实现：在第n年的时候，共有多少头母牛？例11.1：母牛的故事---顺推法设数组f(i)表示第i年的母牛总数，则第n年的母牛总数为f(n)。f(n)与两个值有关在本年之前就已经出生的母牛数目在本年新出生的小母牛数目。1）本年之前就已经出生的母牛数目，实际上就是前一年的母牛总数----f（n-1）。2）由于每一头母牛每年只生育一头小母牛，所以在本年新出生的小母牛

7、数目，实际上是到今年可以生育的母牛的数目。3)而每头小母牛从第四个年头才开始生育，所以今年可以生育的母牛的数实际上就是三年前的母牛总数，即为f（n-3）。例11.1：母牛的故事---顺推法递推公式：f(n)=f(n-1)+f(n-3)（n>=4）第一、二、三年的母牛总数是直接可知的:f(1)=1；f(2)=2;f(3)=3；递推边界｝也可以从最简单开始，找规律：若数组f(i)表示第i年的母牛总数，则第n年的母牛总数为f(n)。n=1f(n)=1n=2f(n)=2n=3f(n)=3n=4f(n)=3+1=f[3]+f[1]=4n=5f(n)=f(4)+