12.递归与动态规划(一).ppt

1、第十二讲,递归与动态规划(一),ACM算法与程序设计,2/38,递归的基本思想,先来看看n的阶乘，常见的有两种做法： 第一种做法，利用循环，直接求出： int n, m = 1; for(int i = 2; i = n; i+) m *= i; printf(“%d 的阶乘是%dn”, n, m); 这一种做法，需要了解n!的算法，它的优点是运算速度快。,3/38,递归的基本思想,第二种做法，利用公式n!=n*(n-1)!，使用递归函数求出： int factorial(int n) if(n 0) return(-1); if(n = 1 | n =0) return 1; else re

2、turn n*factorial(n - 1); 该方法通过递推关系把原来问题缩小成一个更小规模的同类问题，并延续这一缩小规模的过程，直到在某一规模上，问题的解是已知的。这种解决问题的思想我们称为递归的思想。 递归方法的总体思想是将待求解问题的解看作输入变量x 的函数f(x)，通过寻找函数g，使得f(x) = g(f(x-1)，并且已知f(0)的值，就可以通过f(0)和g 求出f(x)的值。这种思想也可以推广到多个输入变量x，y，z 等，x-1 也可以推广到 x - x1，只要递归朝着出口的方向走就可以了。,4/38,二叉树,1、链接地址 2、问题描述,图1 满二叉树,5/38,问题描述,如上

3、图所示，由正整数1, 2, 3, .组成了一棵无限大的二叉树。从某一个结点到根结点（编号是1的结点）都有一条唯一的路径，比如从10到根结点的路径是(10, 5, 2, 1)，从4到根结点的路径是(4, 2, 1)，从根结点1到根结点的路径上只包含一个结点1，因此路径就是(1)。 对于两个结点x和y，假设他们到根结点的路径分别是(x1, x2, . ,1)和(y1, y2, . ,1)（这里显然有x = x1，y = y1），那么必然存在两个正整数i和j，使得从xi 和 yj开始，有xi = yj , xi + 1 = yj + 1, xi + 2 = yj + 2,. 现在的问题就是，给定x和

4、y，要求xi（也就是yj）。,6/38,问题描述,输入格式 输入只有一行，包括两个正整数x 和y，这两个正整数都不大于1000。 输出要求 输出只有一个正整数xi。 输入样例 10 4 输出样例 2,7/38,这个题目要求树上任意两个节点的最近公共子节点。分析这棵树的结构不难看出，不论奇数偶数，每个数对2 做整数除法，就走到它的上层结点。 我们可以每次让较大的一个数（也就是在树上位于较低层次的节点）向上走一个结点，直到两个结点相遇。 如果两个节点位于同一层，并且它们不相等，可以让其中任何一个先往上走，然后另一个再往上走，直到它们相遇。 设common(x, y)表示整数x 和y的最近公共子节点

5、，那么，根据比较x 和y 的值，我们得到三种情况： (1) x 与y 相等，则common(x, y)等于x 并且等于y； (2) x 大于y，则common(x, y)等于common(x/2, y)； (3) x 大于y，则common(x, y)等于common(x, y/2)；,3、解题思路,8/38,4、参考程序,#include int common(int x, int y) if(x = y) return x; if(x y) return common(x / 2, y); return common(x, y / 2); int main(void) int m, n;

6、scanf(%d%d, ,9/38,逆波兰表达式,1、链接地址 2、问题描述 逆波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3 的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4 的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值，其中运算符包括 + - * / 四个。,10/38,问题描述,输入数据 输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数 输出要求 输出为一行，表达式的值。 输入样例 * + 11.0 12.0 + 24.0 35.0 输出样例 1357.00

7、0000,11/38,这个问题看上去有些复杂，如果只是简单地模拟计算步骤不太容易想清楚，但是如果用递归的思想就非常容易想清楚。让我们根据逆波兰表达式的定义进行递归求解。在递归函数中，针对当前的输入，有五种情况： (1) 输入是常数，则表达式的值就是这个常数； (2) 输入是+，则表达式的值是再继续读入两个表达式并计算出它们的值，然后将它们的值相加； (3) 输入是-； (4) 输入是*； (5) 输入是/； 后几种情况与2）相同，只是计算从+变成-，*，/。,3、解题思路,12/38,4、参考程序,#include #include double exp(void) char a10; sca

8、nf(%s, a); switch(a0) case+: return exp( ) + exp( ); case-: return exp( ) - exp( ); case*: return exp( ) * exp( ); case/: return exp( ) / exp( ); default: return atof(a); ,13/38,4、参考程序,int main(void) double ans; ans = exp(); printf(%f, ans); return 0; ,14/38,放苹果,1、链接地址 2、问题描述 把 M 个同样的苹果放在N 个同样的盘子里，允

9、许有的盘子空着不放，问共有多少种不同的分法？（用K 表示）注意：5，1，1 和1，5，1 是同一种分法。,15/38,问题描述,输入数据 第一行是测试数据的数目t（0 = t = 20）。以下每行均包含两个整数M 和N，以空格分开。1=M，N=10。 输出要求 对输入的每组数据M 和N，用一行输出相应的K。 输入样例 1 7 3 输出样例 8,16/38,所有不同的摆放方法可以分为两类：至少有一个盘子为空和所有盘子都不空。对于至少空着一个盘子的情况，则N 个盘子摆放M 个苹果的摆放方法数目与N-1 个盘子摆放M 个苹果的摆放方法数目相同。对于所有盘子都不空的情况，则N 个盘子摆放M 个苹果的摆

10、放方法数目等于N 个盘子摆放M-N 个苹果的摆放方法数目。我们可以据此来用递归的方法求解这个问题。 设f(m, n) 为m 个苹果，n 个盘子的放法数目，则先对n 作讨论，如果nm，必定有n-m 个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响；即if(nm) f(m,n) =f(m,m)。当n = m 时，不同的放法可以分成两类：即有至少一个盘子空着或者所有盘子都有苹果，前一种情况相当于f(m , n) = f(m , n-1); 后一种情况可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f(m , n) = f(m-n , n)。总的放苹果的放法数目等于两者的和，即 f(m,n)

11、 =f(m,n-1)+f(m-n,n) 。整个递归过程描述如下：,3、解题思路,17/38,3、解题思路,int f(int m , int n) if(n = 1 | m = 0) return 1; if(n m) return f (m, m); returnf (m , n-1)+f (m-n , n); 由上在知：当n=时，所有苹果都必须放在一个盘子里，所以返回；当没有苹果可放时，定义为种放法；递归的两条路，第一条n 会逐渐减少，终会到达出口n=1; 第二条m 会逐渐减少，因为nm 时，我们会return f(m , m) 所以终会到达出口m=0 注：苹果(相同或不同)放入盘子(相同

12、或不同)的问题，在组合数学中有更多的论述，可参考卢开澄的组合数学(第2版)第2章中的Stirling数。,18/38,4、参考程序,#include int count(int x, int y) if(y = 1 | x = 0) return 1; if(x y) return count(x, x); return count(x, y - 1) + count(x - y, y); ,19/38,4、参考程序,int main(void) int t, m, n; scanf(%d, ,20/38,红与黑,1、链接地址 2、问题描述 有一间长方形的房子，地上铺了红色、黑色两种颜色的正方

13、形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。,21/38,问题描述,输入数据 包括多个数据集合。每个数据集合的第一行是两个整数W 和H，分别表示x 方向和y 方向瓷砖的数量。W 和H 都不超过20。在接下来的H 行中，每行包括W 个字符。每个字符表示一块瓷砖的颜色，规则如下 (1).：黑色的瓷砖； (2)#：白色的瓷砖； (3)：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。 当在一行中读入的是两个零时，表示输入结束。,22/38,问题描述,输出要求 对每个数据集合，分别输出一行，显示你从初始位置出发能

14、到达的瓷砖数(记数时包括初始位置的瓷砖)。,23/38,这个题目可以描述成给定一点，计算它所在的连通区域的面积。需要考虑的问题包括矩阵的大小，以及从某一点出发向上下左右行走时，可能遇到的三种情况：出了矩阵边界、遇到.、遇到#。 设f(x, y)为从点(x,y)出发能够走过的黑瓷砖总数，则 f(x, y) = 1 + f(x - 1, y) + f(x + 1, y) + f(x, y - 1) + f(x, y + 1) 这里需要注意，凡是走过的瓷砖不能够被重复走过。可以通过每走过一块瓷砖就将它作标记的方法保证不重复计算任何瓷砖。,3、解题思路,24/38,4、参考程序,#include in

15、t W, H; char z2121; int f(int x, int y) if(x = W | y = H) / 如果走出矩阵范围 return 0; if(zxy = #) return 0; else zxy = #; / 将走过的瓷砖做标记 return 1 + f(x - 1, y) + f(x + 1, y) + f(x, y - 1) + f(x, y + 1); ,25/38,4、参考程序,int main(void) int i, j, num; while(scanf(%d %d, ,26/38,小结：,在上面放苹果的例题中可以看出，在寻找从f(x) 向出口方向的递归方法时，我们是对可能的情况做了一步枚举，即将所有可能情况划分为至少有一个盘子空着和所有盘子至少有一个苹果两种情况。 这种通过一步枚举进行递归的方法是很常用的。例如在例