递推算法 递推是一种重要的数学方法，在数学和计算机领域都有广泛应用。这种算法的特点是：一个问题的求解需要一系列的计算，在已知条件和所求问题之间总存在某种相互联系的关系。在计算时，可以找到前后过程间的数量关系，即递推。递推算法包括顺推和逆推。 递推算法的关键在于找到相邻数据项之间的关系，即递推关系，建立递推关系式。我们有时将递推算法看成一种特殊的迭代算法。

Presentation on theme: "递推算法 递推是一种重要的数学方法，在数学和计算机领域都有广泛应用。这种算法的特点是：一个问题的求解需要一系列的计算，在已知条件和所求问题之间总存在某种相互联系的关系。在计算时，可以找到前后过程间的数量关系，即递推。递推算法包括顺推和逆推。 递推算法的关键在于找到相邻数据项之间的关系，即递推关系，建立递推关系式。我们有时将递推算法看成一种特殊的迭代算法。"— Presentation transcript:

1 递推算法 递推是一种重要的数学方法，在数学和计算机领域都有广泛应用。这种算法的特点是：一个问题的求解需要一系列的计算，在已知条件和所求问题之间总存在某种相互联系的关系。在计算时，可以找到前后过程间的数量关系，即递推。递推算法包括顺推和逆推。 递推算法的关键在于找到相邻数据项之间的关系，即递推关系，建立递推关系式。我们有时将递推算法看成一种特殊的迭代算法。

2 算法分析： 1、顺推 由已知推结果 当n=1时，只能有一种铺法，即x1=1； 例题一
1、顺推 由已知推结果 算法分析： 当n=1时，只能有一种铺法，即x1=1； 当n=2时，骨牌可以两个并列竖放或横放，再无他法，即x2=2； 当n=3时，骨牌可以全部竖放；也可以一竖两横或两横一竖，即x3=3； 由此可以看出n=3的骨牌排列方法数是n=1和n=2的排列方法数之和。即xn=xn-1+xn-2；(n>2) 算法：procedure gp(n:int); begin x:=0;y:=1； for i:=1 to n do [z:=x+y; 输出(z);x:=y; y:=z;] end； 例题一 有2*n的长方形方格，用n个1*2的骨牌铺满方格。编一程序，试对给出的任意一个n(n>0), 输出铺法总数。

3 基本分析： 2、逆推 由结果推已知 例题二 算法：procedure sj(n:int); begin for i:=1 to n do
2、逆推 由结果推已知 基本分析： 此题解法有多种，从逆推的思想出发，设想当从顶层沿某条路径走到第i层，向第i+1层前进时，我们的选择一定是沿其下两条路径中最大数字方向前进。为此我们可以采用倒推的手法，设a [i,j]存放从i，j出发到达n层的最大值，即 a[i,j]=max{a[i,j]+a[i+1,j],a[i,j]+a[i+1,j+1]} 最后a[1,1] 即为所求数字总和最大值。 算法：procedure sj(n:int); begin for i:=1 to n do for j:=1 to i do read(a[i,j]); for i:=n-1 downto 1 do for j:=1 to i do if a[i+1,j]>=a[i+1,j+1] then a[i,j]:=a[i,j]+ a[i+1,j] else a[i,j]:=a[i,j]+ a[i+1,j+1] ; writeln(a[1,1]; end； 例题二 数字三角形。编写一个程序计算从顶到底的一条路径，使得该路径所经过的数字总和最大，输出数字总和的最大值。 5 7 3 8

4 上机练习 1、棋盘格数； 【问题描述】设有一个n*m的方格棋盘（1=<n,m<=100）。求出该棋盘中包含的正方形、长方形的个数。 【输入】 {n，m} 【输出】 2、储油点； 【问题描述】一辆卡车欲穿过1000公里的沙漠 ，卡车油耗1升/公里，卡车总载油量为500公升。显然卡车想装一次油穿过沙漠那是痴心妄想。因此司机必须沿途建立临时储油点，使卡车能顺利穿过沙漠。试问司机应如何建立这些储油点？每一储油点应储备多少汽油，才能使得卡车以消耗最少汽油的代价通过沙漠？ （结果保留10位小数） 【输入】本题无输入 【输出】等待结果中。。。 

5 3、走楼梯； 【问题描述】楼梯有n级，上楼可以一步上一个台阶，也可以一步上两个台阶。编写一个递归程序，计算共有多少不同走法。 【输入】3 【输出】3 4、兔子繁殖； 【问题描述】有一种兔子，出生一个月就可以长大，然后再过一个月一对长大的兔子就可以生育一对小兔子且以后每个月都能生育 一对。现在我们有一对刚出生的这种兔子，那么n个月后，我们会有多少对兔子呢？ 【输入】5 【输出】5

6 【奖学金】数据输入样式： 8 04 aaa 03 bbb 01 ccc 05 ddd 02 eee 06 fff 08 ggg 07 hhh 5、平面分隔； 【问题描述】同一平面内有n（n<=500）条直线，已知其中p(p>=2)条直线相交于同一个点，则这n条直线最多能将平面分隔成多少个不同区域。 【输入】 {n，p} 【输出】73 6、骨牌铺法； 【问题描述】有1*n的一个长方形方格，用若干个1*1、1*2、1*3的骨牌铺满方格。例如当n=3时，用1*1、1*2、1*3的骨牌铺满方格，共有四种铺法。 【输入】3 {n} 【输出】4

7 7、蜜蜂路线； 【问题描述】一只蜜蜂在下图所示的数字蜂房上爬动，已知它只能从标号小的蜂房爬到相邻的标号大的蜂房。现在问你：蜜蜂从蜂房m开始爬到蜂房n，(m<n)，有多少种爬行路线。 【输入】 【输出】377 8、数塔问题； 【问题描述】设有一个三角形的数塔，顶点为根结点，每一个结点有一个整数值。从顶点出发，可以向左下或右下走，如图。编程找一条路径，使得路径之和最小，只输出最小值。（n行，1<n<=10） 【输入】左图 【输出】86 1 3 5 7 9 11 2 4 6 8 10 12 n n 5 13 8 7 26

8 【问题描述】已知m，n为整数，且满足下列条件： 1、m，n属于[1，2，..k]，即1=<m,n<=k;
9、极值问题； 【问题描述】已知m，n为整数，且满足下列条件： 1、m，n属于[1，2，..k]，即1=<m,n<=k; 2、(n^2-m*n-m^2)^2=1. 编程输入正整数k(1=<k<=10^9) , 求一组满足上述条件的m，n，并且使得m^2+n^2的值最大。 【输入】1995 【输出】m=987 n=1597 经典问题，先要证明m,n是斐波那契数列中的相邻两项。首先证明斐波那契数列中的相邻两项是满足（2）式的，这个非常简单，用数学归纳法就可以了。再证明，如果两个正整数m、n满足（2）式，必有n>=m，且整数n-m、m也满足（2）式（这里的正整数对是有序的）。于是我们可以一直这样找下去：(m,n)=>(n-m,m)=>(2m-n,n-m)=>…… 直到括号里的两个数相等（如果一开始就有m=n的话，就不用找了）。很容易证明，如果两个相等的正整数满足(2)式，那么他们都是等于1的。我们可以倒着找回去：(1,1)<=(1,2)<=(2,3)<=……直到回到（m,n)为止。于是m、n为斐波那契数列中的相邻两项。 剩下的事情就简单了：找出比k小的最大的相邻两个斐波那契数就可以了。

9 10、过河卒； 【问题描述】棋盘上的A点有一个过河卒，需要走到目标B点。足行走的规则：可以向下或向右。同时在棋盘任意一点有对方一个马，对方马所能到达的点叫控制点。卒不能通过马的所有控制点。棋盘用坐标表示各点，如A(0,0)、B(n,m)。本题卒开始的出发点A坐标和目标点坐标给出，编程计算过河卒从A点能够到达B点的路径总条数。 【输入】 【输出】 A 1 2 3 4 马