12 递归与动态规划一

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

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

3、二叉树4/38问题描述如上图所示，由正整数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,. 现在

4、的问题就是，给定x和y，要求xi（也就是yj）。5/38问题描述输入格式输入只有一行，包括两个正整数x 和y，这两个正整数都不大于1000。输出要求输出只有一个正整数xi。输入样例10 4输出样例26/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)；7/383、解题思路4、参考程序#include int common(int x, int y)n if(x = y)n return x;n if(x y)n return common(x / 2, y);n returnn common(x, y / 2);int main(void)n int m, n;n sca

6、nf(%d%d, &m, &n);n printf(%dn, common(m, n);n return 0;8/38逆波兰表达式1、链接地址/problem?id=26942、问题描述逆波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3 的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2+ 3) * 4 的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值，其中运算符包括 + - * / 四个。9/38n 输入数据输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮

7、点数n 输出要求输出为一行，表达式的值。n 输入样例* + 11.0 12.0 + 24.0 35.0n 输出样例1357.00000010/38问题描述这个问题看上去有些复杂，如果只是简单地模拟计算步骤不太容易想清楚，但是如果用递归的思想就非常容易想清楚。让我们根据逆波兰表达式的定义进行递归求解。在递归函数中，针对当前的输入，有五种情况：(1) 输入是常数，则表达式的值就是这个常数；(2) 输入是+，则表达式的值是再继续读入两个表达式并计算出它们的值，然后将它们的值相加；(3) 输入是-；(4) 输入是*；(5) 输入是/；后几种情况与2）相同，只是计算从+变成-，*，/。11/383、解题

8、思路4、参考程序12/38#include #includedouble exp(void)n char a10;n scanf(%s, a);n switch(a0)n n case+: return exp( ) + exp( );n case-: return exp( ) - exp( );n case*: return exp( ) * exp( );n case/: return exp( ) / exp( );n default: return atof(a);n 13/384、参考程序int main(void)n double ans;n ans = exp();n prin

9、tf(%f, ans);n return 0;放苹果1、链接地址/problem?id=16642、问题描述把 M 个同样的苹果放在N 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K 表示）注意：5，1，1 和1，5，1 是同一种分法。14/38输入数据第一行是测试数据的数目t（0 = t = 20）。以下每行均包含两个整数M 和N，以空格分开。1=M， Nm，必定有n-m 个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响；即if(nm) f(m,n) =f(m,m)。当n m)n return f (m, m);n returnf

10、 (m , n-1)+f (m-n , n);由上在知：当n=时，所有苹果都必须放在一个盘子里，所以返回；当没有苹果可放时，定义为种放法；递归的两条路，第一条n 会逐渐减少，终会到达出口n=1; 第二条m 会逐渐减少，因为nm 时，我们会return f(m , m) 所以终会到达出口m=0注：苹果(相同或不同)放入盘子(相同或不同)的问题，在组合数学中有更多的论述，可参考卢开澄的组合数学(第2版)第2章中的Stirling数。4、参考程序18/38#include int count(int x, int y)n if(y = 1 | x = 0)n return 1;n if(x y)n

11、return count(x, x);n return count(x, y - 1) + count(x - y, y);4、参考程序19/38int main(void)n int t, m, n;n scanf(%d, &t);n for(int i = 0; i t; i+)n n scanf(%d%d, &m, &n);n printf(%dn, count(m, n);n n return 0;红与黑1、链接地址/problem?id=28162、问题描述有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能

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

13、样例6 9.#.#. #.#.#.#. 0 045这个题目可以描述成给定一点，计算它所在的连通区域的面积。需要考虑的问题包括矩阵的大小，以及从某一点出发向上下左右行走时，可能遇到的三种情况：出了矩阵边界、遇到.、遇 到#。设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)这里需要注意，凡是走过的瓷砖不能够被重复走过。可以通过每走过一块瓷砖就将它作标记的方法保证不重复计算任何瓷砖。23/383、解题思路4、参考程序24/38#include int W,

14、H;char z2121;int f(int x, int y)n 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 4、参考程序25/38int main(void)n int i, j, num;n while(scanf(%d %d, &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;26/38小结：在上面放苹果的例题中可以看出，在寻找从f(x) 向出口方向的递归方法时，我们是对可能的情况做了一步枚举，即将所有可能情况划分为至少有一个盘子空着和所有盘子至少有一个苹果两种情况。这种通过一步枚举进行递归的方法是很常用的。例如在例题“红与黑