算法与程序实践2(递归2)(2)

) 出栈 ( 5 1 2 + 出栈并顺序输出运算符直到遇到第一个'(' * 入栈 ( * 5 1 2 + * 优先级< 栈顶元素 ( ,入栈 4 输出 ( * 5 1 2 + 4 当前运算符为'('，直接入栈

) 输出 空 5 1 2 + 4 * 出栈并顺序输出运算符直到遇到第一个'(' - 入栈 - 5 1 2 + 4 * 栈顶元素为空，不用比较，入栈 3 输出 - 5 1 2 + 4 * 3 当前字符是数字直接输出该数字 最后 输出 空 5 1 2 + 4 * 3 - 顺序出栈并输出运算符直到栈元素为空

解题思路：

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

参考程序：

#include #include #include

double exp() {

char a[10]; scanf(\ switch(a[0]) {

case '+': return exp()+exp(); case '-': return exp()-exp(); case '*': return exp()*exp(); case '/': return exp()/exp(); default: return atof(a); } }

int main() {

double ans; ans=exp();

printf(\ return 0; }

CS84：放苹果

（来源：poj.grids.cn 1664，程序设计导引及在线实践（李文新）例题9.5 P203） 问题描述：

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法（用K表示）？注意：5，1，1和1，5，1 是同一种分法。 输入：

第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。 输出：

对输入的每组数据M和N，用一行输出相应的K。 样例输入：

1 7 3 样例输出：

8

解题思路：

所有不同的摆放方法可以分为两类：至少有一个盘子空着和所有盘子都不空。我们可以分别计算这两类摆放方法的数目，然后把它们加起来。对于至少空着一个盘子的情况，则N个盘子摆放M个苹果的摆放方法数目与N-1个盘子摆放M个苹果的摆放方法数目相同。对于所有盘子都不空的情况，则N个盘子摆放M个苹果的摆放方法数目等于N个盘子摆放M-N个苹果的摆放方法数目。我们可以据此来用递归的方法求解这个问题。

设f(m, n)为m个苹果，n个盘子的放法数目，则先对n作讨论，如果n>m，必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响；即if(n>m) 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) =f(m,n-1)+f(m-n,n)。整个递归过程描述如下：

int f(int m , int n){

if(n == １ || m == 0) return 1; if(n > m) return f (m, m); return f (m , n-1)+f (m-n , n); }

出口条件说明：当n=１时，所有苹果都必须放在一个盘子里，所以返回１；当没有苹果可放时，定义为１种放法；递归的两条路，第一条n会逐渐减少，终会到达出口n==1; 第二条m会逐渐减少，因为n>m时，我们会return f(m , m) 所以终会到达出口m==0。

参考程序： #include

int count(int x,int y) { if(y==1 || x==0) return 1;

if(x

int main() { int t,m,n; int i; scanf(\ for(i=0;i

注意事项：

问题一：没有想清楚如何递归，用循环模拟逐一枚举的做法时考虑不周出错；

问题二：出口条件判断有偏差，或者没有分析出当盘子数大于苹果数时要处理的情况；

CS85：红与黑

（来源：poj.grids.cn 2816，程序设计导引及在线实践（李文新）例9.6 P204） 问题描述：

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入：

包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下

1）‘.’：黑色的瓷砖； 2）‘#’：白色的瓷砖；

3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

当在一行中读入的是两个零时，表示输入结束。 输出：

对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。 样例输入：

6 9 ....#. .....#

...... ...... ...... ...... ...... #@...# .#..#. 0 0 样例输出：

45

解题分析：

这个题目可以描述成给定一点，计算它所在的连通区域的面积。需要考虑的问题包括矩阵的大小，以及从某一点出发向上下左右行走时，可能遇到的三种情况：出了矩阵边界、遇到’.’、遇到’#’ 。

设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)

这里需要注意，凡是走过的瓷砖不能够被重复走过。可以通过每走过一块瓷砖就将它作标记的方法保证不重复计算任何瓷砖。

注意事项：

问题一：走过某块瓷砖后没有将它标记，导致重复计算或无限递归； 问题二：在递归出口条件判断时，先判断该网格点是否是’#’，再判断是否出边界，导致数组越界；

问题三：读入数据时，用scanf 一个字符一个字符读入，没有去掉数据中的行尾标记，导致数据读入出错。

在上面放苹果的例题中可以看出，在寻找从f(x) 向出口方向的递归方法时，我们是对可能的情况做了一步枚举，即将所有可能情况划分为至少有一个盘子空着和所有盘子至少有一个苹果两种情况。这种通过一步枚举进行递归的方法是很常用的。例如在例题“红与黑”中，我们枚举了在一个方格点上的四种可能的走法。例题“红与黑”与前几个例题不同的地方在于，在该问题中有一个记录地图的全局量，在每一个格点行走时，我们会改变这个全局量的状态。我们在处理每个格点时按上下左右的顺序依次走向相邻格点，当我们走过左边的格点时，改变了全局量的状态，只是这种改变不影响我们继续走向右边的格点。但是对于另外一类问题，情况可能会不同，在我们尝试了前面的分支情况后，要将全局量恢复成进入分支前的状态，然后再尝试其它的分支情况。下面几个例题就是这种情况。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法与程序实践2(递归2)(2)在线全文阅读。