资源描述:
《C++函数、递推、递归.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、《C++语言程序设计》第九讲函数、递推、递归第九讲——函数、递推、递归递推递推是计算机数值计算中的一个重要算法。大连理工大学盘锦校区基础教学部2思路:通过数学推导,将复杂的运算化解为若干重复的简单运算,以充分发挥计算机长于重复运算的特点;递推法特点:从一个已知的事实出发,按一定规律推出下一个事实,再从这个新的已知事实出发,再向下推出一个新的事实。第九讲——函数、递推、递归递推举例(1)大连理工大学盘锦校区基础教学部3例:(猴子吃桃问题)猴子第1天摘下若干桃子,当即吃了一半,还不过瘾,又多吃了一个。第2天早上又将剩下的桃子吃掉一半
2、,又多吃了一个。以后每天早上都吃了前一天剩下的一半另加一个。到第10天早上想再吃时,就只剩下一个桃子了。问第1天猴子共摘了多少桃子?第九讲——函数、递推、递归解题思路:大连理工大学盘锦校区基础教学部4假设用S(i)表示第i天没吃之前的桃子数目;则S(1)即为第1天所摘的桃子数;S(10)=S(9)*1/2–1第10天没吃之前的桃子数S(2)=S(1)*1/2–1第2天没吃之前的桃子数S(3)=S(2)*1/2-1第3天没吃之前的桃子数……S(9)=S(8)*1/2-1第9天没吃之前的桃子数第九讲——函数、递推、递归一般形式:S(
3、i)=S(i-1)*1/2–1,大连理工大学盘锦校区基础教学部5i=2,3,…,10;这个公式可用于知第1天没吃之前的桃子数推算第2天没吃之前的,再推算第3天没吃之前的,…….。现在要求的是第1天没吃之前的。能否倒过来,先知第10天没吃之前的的再反推第9天没吃之的,……,直到第1天没吃之前的。为此将上式改写为:S(i-1)=2*(S(i)+1),i=10,9,8,…,2第九讲——函数、递推、递归程序:大连理工大学盘锦校区基础教学部6第九讲——函数、递推、递归分析:一般形式:S(i-1)=2*(S(i)+1),i=10,9,8,…
4、,2;初始:s2=1;//S(10)=1大连理工大学盘锦校区基础教学部7i=9s1=2*(s2+1);s2=s1;s1=2*(s2+1);s2=s1;s1=2*(s2+1);s2=s1;//S(9)=2*(S(10)+1)//s2=s1=S(9)//S(8)=2*(S(9)+1)//s2=s1=S(8)//S(7)=2*(S(8)+1)//s2=s1=S(7)i=8i=7i=6s1=2*(s2+1);s2=s1;//S(6)=2*(S(7)+1)//s2=s1=S(6)第九讲——函数、递推、递归i=5大连理工大学盘锦校区基础教学
5、部8s1=2*(s2+1);s2=s1;//S(5)=2*(S(6)+1)//s2=s1=S(5)//S(4)=2*(S(5)+1)//s2=s1=S(4)//S(3)=2*(S(4)+1)//s2=s1=S(3)//S(2)=2*(S(3)+1)//s2=s1=S(2)//S(1)=2*(S(2)+1)//s2=s1=S(1)i=4s1=2*(s2+1);s2=s1;s1=2*(s2+1);s2=s1;s1=2*(s2+1);s2=s1;s1=2*(s2+1);s2=s1;i=3i=2i=1第九讲——函数、递推、递归递推举例(
6、2)大连理工大学盘锦校区基础教学部9递推数列一个数列从某一项起,它的任何一项都可以用它前面的若干项来确定,这样的数列称为递推数列,表示某项与其前面的若干项的关系就称为递推公式。例如自然数1,2,…,n的阶乘就可以形成如下数列:1!,2!,3!,…,(n-1)!,n!另fact(n)为n阶乘,依据后项与前项的关系可以写出递推公式:fact(n)=n*fact(n-1)(通项公式)fact(1)=1(边界条件)第九讲——函数、递推、递归递推算例(3)大连理工大学盘锦校区基础教学部10递推算法程序实现:有了通项公式和边界条件后,采用循
7、环结构,从边界条件出发,利用通项公式通过若干步递推过程就可以求出结果;例:王小二自称刀工不错,有人放一张大的煎饼在砧板上,问他:“饼不许离开砧板,切100刀最多能分成多少块?”第九讲——函数、递推、递归分析:切一刀大连理工大学盘锦校区基础教学部11切二刀切三刀切四刀令q(n)表示切n刀能分成的块数,由上图可知q(1)=1+1=2q(2)=1+1+2=4q(3)=1+1+2+3=7q(4)=1+1+2+3+4=11第九讲——函数、递推、递归分析:切一刀大连理工大学盘锦校区基础教学部12切二刀切三刀切四刀在切法上是让每两条线都有交点
8、。用归纳法可得出q(n)=q(n-1)+nq(0)=1(边界条件)第九讲——函数、递推、递归递推算例(3)参考程序:大连理工大学盘锦校区基础教学部13第九讲——函数、递推、递归递归递归算法在可计算理论中占有重要地位,它是算法设计的有力工具,对于拓展编程思路非常有