《ACM递归与动态规划(一)》由会员分享，可在线阅读，更多相关《ACM递归与动态规划(一)（26页珍藏版）》请在金锄头文库上搜索。
1、第十二讲第十二讲递归与动态规划(一)ACMACM算法与程序设计算法与程序设计递归的基本思想递归的基本思想n先来看看先来看看n的阶乘，常见的有两种做法：的阶乘，常见的有两种做法：n第一种做法，利用循环，直接求出：第一种做法，利用循环，直接求出：nint n, m = 1;nfor(int i = 2; i = n; i+) m *= i;nprintf(“%d 的阶乘是的阶乘是%dn”, n, m);n这一种做法，需要了解这一种做法，需要了解n!的算法，它的优的算法，它的优点是运算速度快。点是运算速度快。2递归的基本思想递归的基本思想n第二种做法第二种做法，利用公式，利用公式n!=n*(n-1)
2、!，使用递归函数求出：，使用递归函数求出：nint factorial(int n)nnif(n 0) return(-1);nif(n = 1 | n =0) return 1;nelse return n*factorial(n - 1);nn该方法通过递推关系把原来问题缩小成一个更小规模的同类该方法通过递推关系把原来问题缩小成一个更小规模的同类问题，并延续这一缩小规模的过程，直到在某一规模上，问问题，并延续这一缩小规模的过程，直到在某一规模上，问题的解是已知的。这种解决问题的思想我们称为递归的思想。题的解是已知的。这种解决问题的思想我们称为递归的思想。n递归方法的总体思想是将待求解问题的
3、解看作输入变量递归方法的总体思想是将待求解问题的解看作输入变量x 的的函数函数f(x)，通过寻找函数，通过寻找函数g，使得，使得f(x) = g(f(x-1)，并且已，并且已知知f(0)的值，就可以通过的值，就可以通过f(0)和和g 求出求出f(x)的值。这种思想也的值。这种思想也可以推广到多个输入变量可以推广到多个输入变量x，y，z 等，等，x-1 也可以推广到也可以推广到 x - x1，只要递归朝着出口的方向走就可以了。，只要递归朝着出口的方向走就可以了。3二叉树二叉树1、链接地址、链接地址 http:/ 满二叉树满二叉树 4问题描述问题描述 如上图所示，由正整数如上图所示，由正整数1,
4、2, 3, .组成了一棵无限大的二叉组成了一棵无限大的二叉树。从某一个结点到根结点（编号是树。从某一个结点到根结点（编号是1的结点）都有一条唯一的结点）都有一条唯一的路径，比如从的路径，比如从10到根结点的路径是到根结点的路径是(10, 5, 2, 1)，从，从4到根到根结点的路径是结点的路径是(4, 2, 1)，从根结点，从根结点1到根结点的路径上只包含到根结点的路径上只包含一个结点一个结点1，因此路径就是，因此路径就是(1)。 对于两个结点对于两个结点x和和y，假设他们到根结点的路径分别是，假设他们到根结点的路径分别是(x1, x2, . ,1)和和(y1, y2, . ,1)（这里显然有
5、（这里显然有x = x1，y = y1），），那么必然存在两个正整数那么必然存在两个正整数i和和j，使得从，使得从xi 和和 yj开始，有开始，有xi = yj , xi + 1 = yj + 1, xi + 2 = yj + 2,. 现在的问题就是，给定现在的问题就是，给定x和和y，要求，要求xi（也就是（也就是yj）。）。5问题描述问题描述输入格式输入格式输入只有一行，包括两个正整数输入只有一行，包括两个正整数x 和和y，这两个正，这两个正整数都不大于整数都不大于1000。输出要求输出要求输出只有一个正整数输出只有一个正整数xi。输入样例输入样例10 4输出样例输出样例26n这个题目要求树
6、上任意两个节点的最近公共子节点。分析这这个题目要求树上任意两个节点的最近公共子节点。分析这棵树的结构不难看出，不论奇数偶数，每个数对棵树的结构不难看出，不论奇数偶数，每个数对2 做整数除法，做整数除法，就走到它的上层结点。就走到它的上层结点。n我们可以每次让较大的一个数（也就是在树上位于较低层次我们可以每次让较大的一个数（也就是在树上位于较低层次的节点）向上走一个结点，直到两个结点相遇。的节点）向上走一个结点，直到两个结点相遇。n如果两个节点位于同一层，并且它们不相等，可以让其中任如果两个节点位于同一层，并且它们不相等，可以让其中任何一个先往上走，然后另一个再往上走，直到它们相遇。何一个先往上
7、走，然后另一个再往上走，直到它们相遇。n设设common(x, y)表示整数表示整数x 和和y的最近公共子节点，那么，的最近公共子节点，那么，根据比较根据比较x 和和y 的值，我们得到三种情况：的值，我们得到三种情况：n(1) x 与与y 相等，则相等，则common(x, y)等于等于x 并且等于并且等于y；n(2) x 大于大于y，则，则common(x, y)等于等于common(x/2, y)；n(3) x 大于大于y，则，则common(x, y)等于等于common(x y/2)；3、解题思路、解题思路74、参考程序、参考程序n#include nint common(int x,
8、 int y)nn if(x = y)n return x;n if(x y)n return common(x / 2, y);n returnn common(x, y / 2);nnint main(void)nn int m, n;n scanf(%d%d, &m, &n);n printf(%dn, common(m, n);n return 0;n8逆波兰表达式逆波兰表达式1、链接地址、链接地址 http:/ 2、问题描述、问题描述 逆波兰表达式是一种把运算符前置的算术表达式，逆波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式例如普通的表达式2 + 3 的逆波兰表示法为的
9、逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如系，也不必用括号改变运算次序，例如(2 + 3) * 4 的逆波兰表示法为的逆波兰表示法为* + 2 3 4。本题求解逆波兰。本题求解逆波兰表达式的值，其中运算符包括表达式的值，其中运算符包括 + - * / 四个。四个。9问题描述问题描述n 输入数据输入数据 输入为一行，其中运算符和运算数之间都用空格分输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数隔，运算数是浮点数n 输出要求输出要求 输出为一行，表达式的值。输出为一行，表达式的
10、值。n 输入样例输入样例 * + 11.0 12.0 + 24.0 35.0n 输出样例输出样例 1357.00000010n这个问题看上去有些复杂，如果只是简单地模拟计算步骤不太这个问题看上去有些复杂，如果只是简单地模拟计算步骤不太容易想清楚，但是如果用递归的思想就非常容易想清楚。让我容易想清楚，但是如果用递归的思想就非常容易想清楚。让我们根据逆波兰表达式的定义进行递归求解。在递归函数中，针们根据逆波兰表达式的定义进行递归求解。在递归函数中，针对当前的输入，有五种情况：对当前的输入，有五种情况：n(1) 输入是常数，则表达式的值就是这个常数；输入是常数，则表达式的值就是这个常数；n(2) 输
11、入是输入是+，则表达式的值是再继续读入两个表达式并，则表达式的值是再继续读入两个表达式并计算出它们的值，然后将它们的值相加；计算出它们的值，然后将它们的值相加；n(3) 输入是输入是-；n(4) 输入是输入是*； n(5) 输入是输入是/；n后几种情况与后几种情况与2）相同，只是计算从）相同，只是计算从+变成变成-，*，/。3、解题思路、解题思路114、参考程序、参考程序n#include n#includendouble exp(void)nn char a10;n scanf(%s, a);n switch(a0)n n case+: return exp( ) + exp( );n ca
12、se-: return exp( ) - exp( );n case*: return exp( ) * exp( );n case/: return exp( ) / exp( );n default: return atof(a);n n124、参考程序、参考程序nint main(void)nn double ans;n ans = exp();n printf(%f, ans);n return 0;n13放苹果放苹果1、链接地址、链接地址 http:/ 2、问题描述、问题描述 把把 M 个同样的苹果放在个同样的苹果放在N 个同样的盘子个同样的盘子里，允许有的盘子空着不放，问共有多少种
13、里，允许有的盘子空着不放，问共有多少种不同的分法？（用不同的分法？（用K 表示）注意：表示）注意：5，1，1 和和1，5，1 是同一种分法。是同一种分法。 14问题描述问题描述n输入数据输入数据n第一行是测试数据的数目第一行是测试数据的数目t（0 = t = 20）。以下每）。以下每行均包含两个整数行均包含两个整数M 和和N，以空格分开。，以空格分开。1=M，Nm，必定有，必定有n-m 个盘子永远空着，去掉它们对摆放苹果方法个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响；即数目不产生影响；即if(nm) f(m,n) =f(m,m)。当。当n m) nreturn f (m, m);nr
14、eturnf (m , n-1)+f (m-n , n);nn由上在知：当由上在知：当n=时，所有苹果都必须放在一个盘子里，所以返回时，所有苹果都必须放在一个盘子里，所以返回；当没有苹果可放时，定义为种放法；递归的两条路，第一条；当没有苹果可放时，定义为种放法；递归的两条路，第一条n 会逐渐减少，终会到达出口会逐渐减少，终会到达出口n=1; 第二条第二条m 会逐渐减少，因为会逐渐减少，因为nm 时，我们会时，我们会return f(m , m) 所以终会到达出口所以终会到达出口m=0n注：苹果注：苹果(相同或不同相同或不同)放入盘子放入盘子(相同或不同相同或不同)的问题，在的问题，在组合数组合
15、数学学中有更多的论述，可参考卢开澄的中有更多的论述，可参考卢开澄的组合数学组合数学(第第2版版)第第2章中章中的的Stirling数。数。174、参考程序、参考程序n#include nint count(int x, int y)nn if(y = 1 | x = 0) n return 1;n if(x y)n return count(x, x);n return count(x, y - 1) + count(x - y, y);n184、参考程序、参考程序nint main(void)nn int t, m, n;n scanf(%d, &t);n for(int i = 0; i
16、t; i+)n n scanf(%d%d, &m, &n);n printf(%dn, count(m, n);n n return 0;n19红与黑红与黑1、链接地址、链接地址 http:/ 2、问题描述、问题描述 有一间长方形的房子，地上铺了红色、黑色两种有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。你总共能够到达多少块黑色的瓷砖。20问题描述问题描述n输入数据输入数据n包括多个数据集
17、合。每个数据集合的第一行是两个整数包括多个数据集合。每个数据集合的第一行是两个整数W 和和H，分别表示，分别表示x 方向和方向和y 方向瓷砖的数量。方向瓷砖的数量。W 和和H 都都不超过不超过20。在接下来的。在接下来的H 行中，每行包括行中，每行包括W 个字符。每个字符。每个字符表示一块瓷砖的颜色，规则如下个字符表示一块瓷砖的颜色，规则如下n(1).：黑色的瓷砖；：黑色的瓷砖；n(2)#：白色的瓷砖；：白色的瓷砖；n(3)：黑色的瓷砖，并且你站在这块瓷砖上。该字：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。符在每个数据集合中唯一出现一次。n当在一行中读入的是两个零时
18、，表示输入结束。当在一行中读入的是两个零时，表示输入结束。21问题描述问题描述n输出要求输出要求n对每个数据集合，分别输出一行，显示你从初始位对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数置出发能到达的瓷砖数(记数时包括初始位置的瓷砖记数时包括初始位置的瓷砖)。 输入样例输入样例输出样例输出样例6 9.#.#.#.#.#.#.0 04522n这个题目可以描述成给定一点，计算它所在的连通区域的面积。这个题目可以描述成给定一点，计算它所在的连通区域的面积。需要考虑的问题包括矩阵的大小，以及从某一点出发向上下左需要考虑的问题包括矩阵的大小，以及从某一点出发向上下左右行走时，可能遇到
19、的三种情况：出了矩阵边界、遇到右行走时，可能遇到的三种情况：出了矩阵边界、遇到.、遇到遇到#。n设设f(x, y)为从点为从点(x,y)出发能够走过的黑瓷砖总数，则出发能够走过的黑瓷砖总数，则n f(x, y) = 1 + f(x - 1, y) + f(x + 1, y) + f(x, y - 1) + f(x, y + 1)n这里需要注意，凡是走过的瓷砖不能够被重复走过。可以通过这里需要注意，凡是走过的瓷砖不能够被重复走过。可以通过每走过一块瓷砖就将它作标记的方法保证不重复计算任何瓷砖。每走过一块瓷砖就将它作标记的方法保证不重复计算任何瓷砖。3、解题思路、解题思路234、参考程序、参考程序
20、n#include nint W, H;nchar z2121;nint f(int x, int y)nn if(x = W | y = H) / 如果走出矩阵范围如果走出矩阵范围n return 0;n if(zxy = #)n return 0;n elsen n zxy = #; / 将走过的瓷砖做标记将走过的瓷砖做标记n return 1 + f(x - 1, y) + f(x + 1, y) + f(x, y - 1) + f(x, y + 1);n n244、参考程序、参考程序nint main(void)nn int i, j, num;n while(scanf(%d %d,
21、 &H, &W) & W != 0 & H != 0)n n num = 0;n for(i = 0; i W; i+) / 读入矩阵读入矩阵n scanf(%s, zi);n for(i = 0; i W; i+)n for(j = 0; j H; j+)n if(zij = ) printf(%dn, f (i , j);n n return 0;n25小结小结：n在上面放苹果的例题中可以看出，在寻找从在上面放苹果的例题中可以看出，在寻找从f(x) 向出口方向的递归向出口方向的递归方法时，我们是对可能的情况做了一步枚举，即将所有可能情况划分方法时，我们是对可能的情况做了一步枚举，即将所有可
22、能情况划分为至少有一个盘子空着和所有盘子至少有一个苹果两种情况。为至少有一个盘子空着和所有盘子至少有一个苹果两种情况。n这种通过一步枚举进行递归的方法是很常用的。例如在例题这种通过一步枚举进行递归的方法是很常用的。例如在例题“红与红与黑黑”中，我们枚举了在一个方格点上的四种可能的走法。中，我们枚举了在一个方格点上的四种可能的走法。n例题例题“红与黑红与黑”与前几个例题不同的地方在于，在该问题中有一个与前几个例题不同的地方在于，在该问题中有一个记录地图的全局量，在每一个格点行走时，我们会改变这个全局量的记录地图的全局量，在每一个格点行走时，我们会改变这个全局量的状态。我们在处理每个格点时按上下左右的顺序依次走向相邻格点，状态。我们在处理每个格点时按上下左右的顺序依次走向相邻格点，当我们走过左边的格点时，改变了全局量的状态，只是这种改变不影当我们走过左边的格点时，改变了全局量的状态，只是这种改变不影响我们继续走向右边的格点。响我们继续走向右边的格点。n但是对于另外一类问题，情况可能会不同，在我们尝试了前面的分但是对于另外一类问题，情况可能会不同，在我们尝试了前面的分支情况后，要将全局量恢复成进入分支前的状态，然后再尝试其它的支情况后，要将全局量恢复成进入分支前的状态，然后再尝试其它的分支情况。下面几个例题就是这种情况。分支情况。下面几个例题就是这种情况。26
