递推算法分析.ppt

1、教学要求 了解递推算法的概念与各类递推设计要领 应用递推算法求解实际问题,第三章 递 推,1. 递推的概念 递推是计算机数值计算中的一个重要算法。思想是通过数学推导，将复杂的运算化解为若干个重复的简单运算，以充分发挥计算机善长重复处理的特点,一、递推概述,2. 递推关系,递推算法的首要问题是得到相邻的数据项之间的关系，即递推关系。 递推关系是一种高效的数学模型，是递推应用的核心。 递推关系不仅在各数学分支中发挥着重要的作用，由它所体现出来的递推思想在各学科领域中更是显示出其独特的魅力。,求解方法 找规律： a1=1 a2=1 a3=2=1+1=a1+a2 a4=3=1+2=a2+a3 a5=5

2、=2+3=a3+a4 a6=8=3+5=a4+a5 则有： an=an-2+an-1， a1=1,a2=1 有了这个递推方程，程序就很简单了。,例：求斐波那契数列：1、1、2、3、5、8、的第n项。,3. 递推的实施步骤,（1）确定递推变量 递推变量可以是简单变量，也可以是一维或多维数组。 （2）建立递推关系 递推关系是递推的依据，是解决递推问题的关键。 （3）确定初始（边界）条件 根据问题最简单情形的数据确定递推变量的初始（边界）值，这是递推的基础。 （4）对递推过程进行控制 递推过程控制：递推在什么时候结束，满足什么条件结束。,4. 递推算法框架描述,（1） 简单顺推算法 顺推即从前往后推

3、，从已求得的规模为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）较复杂的递推问题需设置多重循环递推。,例1：求斐波那契数列：1、1、2、3、5、8、的第n项。 问题分析： 斐波那契数

4、列具有下列递推关系 an=an-2+an-1， a1=1,a2=1，q且其中n=3 算法描述： int fib(int n) int i,f1=1,f2=1,f; for(i=3;i=n;i+) f=f1+f2; f1=f2; f2=f; if(n=1|n=2) return 1; else return f; ,二、递推算法实例,1、输出斐波那契数列：1、1、2、3、5、8、的前n项。 （ 每行输出10个数） 2、求斐波那契数列：1、1、2、3、5、8、的前n项的和。,思考：,二、递推算法实现实例,例2：求n！。 算法描述： int fact(int n) int i,s=1; for(i=

5、1;i=n;i+) s=s*i; return s; ,二、递推算法实现,例3：求n！。 算法描述： int fact(int n) int i,s=1; for(i=1;i=n;i+) s=s*i; return s; ,三、案例分析,3.1 猴子爬山,案例提出： 一个顽猴在一座有30级台阶的小山上爬山跳跃，猴子上山一步可跳1级，或跳3级，试求上山的30级台阶有多少种不同的爬法。,设爬k级台阶的不同爬法为f(k)种。 （1） 探求f(k)的递推关系。 上山最后一步到达第30级台阶，共有f(30)种不同的爬法；到第30级之前位于哪一级呢？无非是位于第29级（上跳1级即到），有f(29)种；或位

6、于第27级（上跳3级即到），有f(27)种；于是有 f(30)=f(29)+f(27) 一般地有递推关系：f(k)=f(k-1)+f(k-3) （k3） （2） 确定初始条件 f(1)=1；即1=1; f(2)=1；即2=1+1; f(3)=2；即3=1+1+1；3=3,1. 算法分析,2. 算法描述,printf(请输入台阶总数n:); scanf(%d,3.2 水手分椰子,案例提出 五个水手来到一个岛上，采了一堆椰子。一段时间后，第一个水手醒来，悄悄地将椰子等分成五份，多出一个椰子，便给了旁边的猴子，然后自己藏起一份，再将剩下的椰子重新合在一起。不久，第二名水手醒来，同样将椰子等分成五份，

7、恰好也多出一个，也给了猴子。然后自己也藏起一份，再将剩下的椰子重新合在一起。以后每个水手都如此分了一次并都藏起一份，也恰好都把多出的一个给了猴子。第二天，五个水手醒来，把剩下的椰子分成五份，恰好又多出一个，给了猴子。 问原来这堆椰子至少有多少个?,设置y数组，第i个水手藏椰子数为y(i)(i=1,2,5)个，第二天5个水手醒来后各分得椰子为y(6)个，依题意原来这堆椰子数为 x=5*y(1)+1 为了求取y(1)，实施递推。相邻两人所藏椰子数y(i)与y(i+1)之间的关系为 4*y(i)=5*y(i+1)+1 (i=1,2,5) （3） 习惯按时间顺序递推，从y(i)推出y(i+1)，即 y

8、(i+1)=(4*y(i)-1)/5 (i=1,2,5) （4）,1. 算法分析,第二个问题，递推何时结束？ 问题本身没有边界条件限制，只要求上面5个递推方程所涉及的6个量y(i)都是正整数。也就是说，若有6个整数y(i)满足5个方程4*y(i)=5*y(i+1)+1，(i=1,2,5)即为一个解。 首先y(1)赋初值k(取值从1开始递增)后推出y(2)，由y(2)推出y(3)，依此经5次递推得y(6)。如果某一次推出的不是整数，则中止继续往后推，返回k增1后赋值给y(1)，从头开始。如果5次递推都是整数，则输出原有椰子数5*y(1)+1后结束。,2. 算法描述,int i; double k,x,y7; i=1;k=1.0;y1=k; while(i=5) i+;yi=(4*yi-1-1)/5; if(yi!=（int）yi) k=k+1.0;y1=k;i=1; x=5*y1+1; printf(原有椰子至少有：%6.0