递推—递归算法练习.ppt

递推--递归算法 递归的概念与基本思想 递归过程是借助于一个递归工作栈来实现的 问题向一极推进，这一过程叫做递推； 而问题逐一解决，最后回到原问题，这一过程叫做回归。 递归的过程正是由递推和回归两个过程组成。 递归定义必须是有确切含义的，即一步比一步简单，最终是有终结的，决不能无限循环下去。 递归与递推既有相似点又有不同点，相同点是数据元素间的关系可以用抽象的、严格的公式表示出来，且不论是递推还是递归，都具有边界条件。不同点是递推是从边界条件出发，通过递推关系求f(n)的值，从边界到目标解的过程清楚直观；而递归是从函数自身出发来达到边界条件，在通往边界的递归过程中，系统要用推栈把每次调用的中间结果保存下来，供递归返回时使用（出栈），而编写出来的程序却是高度概括的，这一复杂的过程由操作系统来完成。 一个递归算法，本质上是将较复杂的处理归结为较简单的处理，……直到最简单的处理。从实际问题中抽象出递归定义和边界条件地过程是一种归纳， 通过这种归纳方式能使一个蕴含递归关系且结果复杂的程序变得简洁精炼。特别是在难于找到从边界到解的全过程的情况下，如果把问题推进一步，其结果仍维持原问题的关系，只是规模减小了，则采用递归算法比较适合。但递归算法也有其致命的缺点：执行的效率低，尤其在边界条件设置不当的情况下，极有可能陷入死循环或内存溢出的情况。 一、直线的交点数 [问题]平面上有n条直线，且无三线共点，问这些直线能有多少种不同的交点数。 输入：n(n=20). 输出：若干行，列出所有相交方案，其中每一行为一个可能的交点数。 [问题分析] 我们将n条直线排成一个序列。直线2与直线1最多有一个交点；直线3与直线1和直线2最多有2个交点，……，直线n与其它n-1条直线最多有n-1个交点。由此得出n条直线互不平行且无三线共点的最多交点数max=1+2+……+(n-1)= ,但本题远没有这么简单。 设数组g[1..max]，g[i]=0表示交点数i不存在，g[i]=1表示交点数i存在（0≤i≤max） 容易列举出i=1,2,3的情形，下面分析n=4的情况： (1)四条直线全部平行，无交点，g[0]=1; (2)三条直线平行，交点数为(n-1)×1+0=3 g[3]=1; (3)二条直线平行。这两条直线与另外两条直线间的交点数为(n-2)×2=4。而另外两条直线既能平行亦能相交，因此交点数分别为： (n-2)×2+0=4 g[4]=1 (n-2)×2+1=5 g[5]=1 (4)四条直线互不平行。交点数为(n-1)×1+3条直线的相交情况： (n-1) ×1+0=3 g[3]=1 (n-1)×1+2=5 g[5]=1 (n-1)×1+3=6 g[6]=1 即n=4时，有0、3、4、5、6个不同的交点数。 问题：设有一块正方形的钢板，现需将它分成n个小正方形。例如，当： n=2 不可能有解。 n=3 不可能有解。 n=4 可分成4个小正方形钢板。 n=5 不可能有解。 n=6 即一个大的加五个小的。 n=7 即三个较大的加四个小的。 n=8 即一个大的加七个小的。 问题：任给n，求出分成n个小正方形的方法。 四、递推的应用（博弈问题） 走直线棋。有如下所示的一个编号为１到ｎ的方格： 现由计算机和人进行人机对奕，从１到ｎ，每次可以走ｋ个方格，其中ｋ为集ｓ={a1,a2, a3,....am}中的元素(m=4)，规定谁最先走到第n格为胜，试设计一个人机对奕方案，摸拟整个游戏过程的情况并力求计算机尽量不败。 * * 递归的应用 解决搜索问题 处理递归定义或解决方法为递归方式的问题 实现分治思想 用于输出动态规划的中间过程 递归不仅可用于计算、计数，而且还可用于枚举，即把所有具有某种特性的对象完全枚举出来，关键是如何从输入参数与输出结果之间的对应关系中归纳出递归公式和边界条件。与递推一样，归纳探究出递归公式是解决此类问题的关键。 从以上分析中，得到： m条直线的交点方案=(m-r)条平行线与r条直线交叉的交点数+r条直线本身的交点方案=(m-r)×r+r条直线本身的交点方案 (1≤r≤m) 上式说明：计算不同交点方案的问题是递归的，描述成如下递归算法： procedure try(m,j) {m为直线，j为交点数} begin if m0 {若直线存在，则递归计算所有的交叉情况} then for r:=m downto 1 do try(m-r,j+r*(m-r)) else g[j]=1 {否则确定m条直线存在j个交点}