递归递推测试题分析讲解.ppt

1,逆波兰表达式,问题描述： 逆波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2+3的逆波兰表示法为+23。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如（2+3）*4的逆波兰表示法为*+234。本题求解逆波兰表达式的值，其中运算符包括+- * / 四个。 输入数据: 输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。 输出要求： 输出为一行，表达式的值 输入样例： * + 11.0 12.0 + 24.0 35.0 输出样例： 1357.000000,2,分析,解题思路： 这个问题看上去有些复杂，如果只是简单地模拟计算步骤不太容易想清楚，但是如果用递归的思想就非常容易想清楚，让我们根据逆波兰表达式的定义进行递归求解。在这个递归函数中，针对当前的输入，有五种情况： 1、输入是常数，则表达式的值就是这个常数 2、输入的是 + ，则表达式的值是再继续读入两个表达式并计算出它们的值 3、输入的是 - ； 4、输入的是 * ； 5、输入的是 / ; 后面几种情况与2相同，只是计算从 + 变成 - * / 。,3,#include #include double exp() char a10; scanf(“%s”,a); switch(a0) case+:return exp()+exp(); case-:return exp()-exp(); case*:return exp()*exp(); case/:return exp()/exp(); default:return atof(a); void main() double ans; ans=exp(); printf(“%f”,ans); ,4,实现中常见的问题,问题一： 不适应递归的思路，直接分析输入的字符串，试图自己写进栈出栈的程序，写得逻辑复杂，因考虑不周出错。 问题二： 不会使用atof（）函数，自己处理浮点数的读入，逻辑复杂出错。,5,放苹果,问题描述： 把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,6,解题思路： 1、所有不同的摆放方法可以分为两类：至少有一个盘子空着和所有的盘子都不空。我们可以分别计算这两类摆放方法的数目，然后把它们加起来。对于至少空着一个盘子的情况，则N个盘子摆放M个苹果的摆放数目与N-1个盘子摆放M个苹果的摆放方法数目相同。对于所有盘子都不空的情况，则N个盘子摆放M个苹果的摆放方法数目等于N个盘子摆放M-N个苹果的摆放方法数目。我们可以据此来用递归的方法求解这个问题。 2、设f（m,n）为m个苹果，n个盘子的放法数目，则先对n作讨论，如果nm,必定有n-m个盘子永远空着，去掉它们对摆放苹果放法数目不产生影响；即if(nm)f(m,n)=fm,m。当nm)return f(m,m); return f(m,n-1)+f(m-n,n) 3、出口条件说明：当n=1是，所有苹果都必须放到一个盘子里，所有返回1，当没有苹果可放时，定义为1种放法。递归的两条路，第一条n会逐渐减少，终会达到出口n=1；第二条m会逐渐减少，因为nm时，我们会return f(m,m)所以终会到达出口m=0.,7,#include int count(int x,int y) if (y=1|x=0)return 1; if (xy) return count(x,x); return count(x,y-1)+count(x-y,y); void main() int t,m,n; scanf(“%d”, ,8,实现中常见的问题,问题一： 没有想清楚如何递归，用循环模拟逐一枚举的做法时考虑不周出错。 问题二： 出口条件判断有偏差，或者没有分析出当盘子大于苹果时要处理的情况。,9,白与黑 问题描述： 有一间长方形的房子，地上铺了白色、黑色两种颜色的正方形瓷砖，你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够达到多少块黑色的瓷砖。 输入数据： 包括多个数据集合，每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下： 1）.:黑色的瓷砖 2）#:白色的瓷砖 3）:黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次 当在一行中读入的是两个零时，表示输入结束。 输出要求：对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数（记数时包括初始位置的瓷砖）。 输入样例： 6 9 .#. # #.# .#. 0 0 输出样例： 45,10,分析,解题思路： 这个题目可以描述成给定一点，计算它所在的连通区域的面积。需要考虑的问题包括矩阵的大小，以及从某一点出发向上下左右行走时，可能遇到的三种:出了矩阵边界、遇到.、遇到#。 设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) 这里需要注意，凡是走过的瓷砖不能够被重复走过。可以通过每走过一块瓷砖就将其作标记的方法保证不重复计算任何瓷砖。,11,#include int 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) void main() int i,j,num; while(scanf(“%d%d”, ,12,实现中常见的问题,问题一： 走过某块瓷砖后没有把它标记，导致重复计算或无限递归。 问题二： 在递归出口条件判断时，先判断该网格点是否是#，再判断是否出边界，导致数组越界。 问题三： 读入数据时，用scanf一个字符一个字符读入，没有去掉数据中的行尾标记，导致数据读入出错。,13,八皇后问题,问题描述： 会下国际象棋的人都很清楚：皇后可以在横竖斜线上不限步数地吃掉其他棋子，如何将8个皇后放在棋盘上（有8*8个方格），使他们谁也不能被吃掉！这就是著名的八皇后问题。对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个、不同的皇后串）。给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。 输入数据： 第一行是测试数据的组数n，后面跟着n行输入，每组测试数据占1行，包括一个正整数b（1=b=92）。 输出要求： n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。 输入样例： 2 1 92 输出样例： 15863724,14,解题思路： 1、因为要求出92中不同的摆放方法中的任意一种，所有我们不妨把92中不同的摆放方法一次性求出来，存放在一个数组里。为求解这道题我们需要一个矩阵仿真棋盘，每次试放一个棋子时只能放在尚未被控制的格子上，一旦放置了一个新棋子，就在它所能控制的所有位置上设置标记，如此下去把八个棋子放好。完成一种摆放时，就要尝试下一种。若要按照字典序将可行摆放方法记录下来，就要按照一定的顺序进行尝试。也就是将第一个棋子按照从小到大的顺序尝试，对于第一个棋子的位置，将第二个棋子从可行的位置从小到大的顺序尝试；在第一和第二个棋子固定的情况下，将第三个棋子从可行的位置从小到大的顺序尝试；以此类推。 2、首先，我们有一个8*8的矩阵仿真棋盘标识当前已经摆好的棋子所控制的区域。用一个92行每行8个元素的二维数组记录可行的摆放方法。用一个递归程序实现尝试摆放的过程。基本思想就是假设我们将第一个棋子摆好，并设置它的控制区域，则这个问题就变成了一个7皇后问题，用与8皇后同样的方法可以获得问题的求解。那我们就把重心放在如何摆放一个皇后棋子上，摆放的基本步骤是：从第1到第8个位置，顺序地尝试将棋子放置在每一个未被控制的位置，设置该棋子所控制的格子，将问题变成更小规模的问题向下递归，需要注意的是每次尝试一个新的未被控制的位置前，要将上一次尝试的位置所控制的格子复原。,15,#include #include int queenPlaces928; int count=0; int board88; void putQueen(int ithQueen);/递归函数 void main() int n,i,j; for(i=0;i8;i+) for(j=0;i8;j+) boardij=-1; for(j=0;j92;j+) queenPlacesji=0; putQueen(0);/从第0个棋子开始摆放 scanf(“%d”, ,16,void putQueen(int ithQueen) int i,k,r; if (ithQueen=8) count+; return; for(i=0;i8;i+) if(bo