第三章 递推算法.ppt

第三章 递推算法 【上机练习】 【问题探讨】 * * 递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。 递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。 【例1】数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。 　 1、 一步可沿左斜线向下或右斜线向下走； 　 2、 三角形行数小于等于100； 3、 三角形中的数字为0，1，…，99； 测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入： 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 【算法分析】 此题解法有多种，从递推的思想出发，设想，当从顶层沿某条路径走到第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] 即为所求的数字总和的最大值。 【参考程序】 program ex3_1; var n,j,i:integer; a:array[1..100,1..100] of integer; begin read(n); 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 begin 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]; 　 end; 　writeln(a[1,1]); end. 【例2】 有 2χn的一个长方形方格，用一个1*2的骨牌铺满方格。 编写一个程序，试对给出的任意一个 n(n0), 输出铺法总数。 【算法分析】 （1）面对上述问题，如果思考方法不恰当，要想获得问题的解答是相当困难的。可以用递推方法归纳出问题解的一般规律。 （2）当n=1时，只能是一种铺法，铺法总数有示为x1=1。 （3）当n=2时：骨牌可以两个并列竖排，也可以并列横排，再无其他方法，如下左图所示，因此，铺法总数表示为X2=2； （4）当N=3时：骨牌可以全部竖排，也可以认为在方格中已经有一个竖排骨牌，则需要在方格中排列两个横排骨牌（无重复方法），若已经在方格中排列两个横排骨牌，则必须在方格中排列一个竖排骨牌。如上右图，再无其他排列方法，因此铺法总数表示为x3=3. 由此可以看出，当n=3时的排列骨牌的方法数是n=1和n=2排列方法数的和。 ? （5）推出一般规律：对一般的n，要求Xn可以这样来考虑，若第一个骨牌是竖排列放置，剩下有n-1个骨牌需要排列，这时排列方法数为Xn-1；若第一个骨牌是横排列，整个方格至少有2个骨牌是横排列（1*2骨牌），因此剩下n-2个骨牌需要排列，这是骨牌排列方法数为Xn-2。从第一骨牌排列方法考虑，只有这两种可能，所以有： ???????????? Xn=Xn-1+Xn-2 （n2） ???????????? x1=1 ???????????? x2=2 Xn=Xn-1+Xn-2就是问题求解的递推公式。任给n都可以从中获得解答。 例如 n=5， ?????????? X3=X2+X1=3 ?????????? X4=X3+X2=5 ?????????? X5=X4+X3=8 下面是输入n，输出X1~Xn的Pascal程序： program