gw6_recursion.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,程序设计实习,第六讲 递归,=g(f(x-1),，,并且已知,f(0),的值，就可以通过,f(0),和,g,求出,f(x),的值,这样一个思想也可以推广到多个输入变量,x,y,z,等，,x-1,也可以推广到,x-x1,只要递归朝着出口的方向走就可以了,#,include,int,Factorial,(int,n,),if(,n,=,0,),return,1,;,else,return,n,*,Factorial,(,n,-,1,);,求阶乘的递归程序,阶乘的栈,主程序,参数,4,4*Factorial(3),参数,3,3*Factorial(2),参数,2,2*Factorial(1),参数,1,1*Factorial(0),参数,0,Factorial(0),1,1,2,6,24,递归解决问题的关键,找出递推公式,2),找到递归终止条件,注意事项：,由于函数的局部变量是存在栈上的，如果有体积大的局部变量，比如数组，而递归层次又可能很深的情况下，也许会导致栈溢出，因此可以考虑使用全局数组或动态分配数组,汉诺塔问题,A,B,以,C,柱为中转，将盘从,A,柱移动到,B,柱上，一次只能移动一个盘，而且大盘不能压在小盘上面,C,Please input disc number:,3,The solution is:,A-B,A-C,B-C,A-B,C-A,C-B,A-B,汉诺塔问题,汉诺塔问题,将,n,个盘子从,a,柱移动到,b,柱，用,c,柱做中转,可以分以下,3,步实现：,1),先将,n-1,个盘子，以,b,为中转，从,a,柱移动到,c,柱，,2),将一个盘子从,a,移动到,b,将,c,柱上的,n-1,个盘子，以,a,为中转，移动到,b,柱,终止条件？,A,B,CC,n=1,时，直接移动盘子即可，不用递归,#include,using namespace std;,/,将,n,个盘子从,a,柱移动到,b,柱，用,c,柱做中转,void,Hanoi(int,n,char,a,char,b,char,c),if(n=1),cout,b,endl,;,return;,/,先将,n-1,个盘子，以,b,为中转，从,a,柱移动到,c,柱，,Hanoi(n-1,a,c,b);,/,将一个盘子从,a,移动到,b,cout,b,endl,;,/,将,c,柱上的,n-1,个盘子，以,a,为中转，移动到,b,柱,Hanoi(n-1,c,b,a);,汉诺塔问题,main(),int,N;,cout,Please input disc number:N;,cout,The solution is:a,必定至少有,d-a,个盘子是空的，去掉这些空盘子对摆放苹果方法数目不产生影响；即,if(d,a),f(a,d,)=,f(a,a,),例题,：,POJ1664,放苹果,当,da),f(a,d,)=,f(a,a,);,else,f(a,d,)=f(a,d-1)+f(a-d,d);,出口条件是什么呢？,例题,：,POJ1664,放苹果,出口条件说明：当,d=,时，所有苹果都必须放在一个盘子里，所以返回；当没有苹果可放时，所有盘子都是空的，这当然是一种放法，所以也返回,1,；递归的两条路，第一条会逐渐减少，终会到达出口,d=1;,第二条,a,会逐渐减少，因为,da,时，我们会,return,f(a,a,),所以终会到达出口,a=0,int,f(int,a,int,d),if(d=1|a=0),return 1;,if(d,a),return,f(a,a,);,return f(a,d-1)+f(a-d,d);,例题：,ai2755,神奇口袋,给出小于的正整数,a1,，,a2,an,，问凑出和为有多少种方法,算法：设,f(a1,，,a2,an,40,),为用,a1,，,a2,an,凑出的方法数，考虑凑数的方法分为两类，用到,a1,和用不到,a1,则有,f(a1,，,a2,an,40)=,f(a2,an,40-a1)+f(a2,an,40),例题：,ai2755,神奇口袋,这里考虑到在实现上函数的参数个数要统一，所以把,a1,，,a2,an,放到一个数组中，用,numbers,存放所有的整数，,n,表示数组中整数的个数，,ith,表示从数组中第,ith,个数开始凑数,(,ith,前面的不用），,sum,表示要凑出的总数，则,f(numbers,n,ith,sum,)=,f(numbers,n,ith+1,sum-numbersith)/,用到,ith,+f(numbers,n,ith+1,sum),/,不用,ith,出口条件是什么呢？,例题：,ai2755,神奇口袋,f(numbers,n,ith,sum,)=,f(numbers,n,ith+1,sum-numbersith)/,用到,ith,+f(numbers,n,ith+1,sum),/,不用,ith,出口条件,1,）如果,sum=0,则应该返回,1,（一个数都不取，也是一种取法）,2,）如果,sum 0,则应该返回,0,（没法凑出负数）,3),如果,ith,=n,则应该返回,0(,所有的数都用完了，和还没有凑够）,思考：,1),3),的判断先后次序是不是无所谓的？,在实现上有两种考虑：,因为,numbers,n,与递归没有太大关系，可以考虑使用全局量；,如果不使用全局量，而通过参数传递,numbers,n,，,可以增强递归函数的独立性,程序（,将,numbers,n,设为,全局量,）,int,numbers50,n;,int,count(int,ith,int,sum),if(sum=0),return 1;,if(ith,=n|sum 0),return 0;,return count(ith+1,sum-numbersith),+count(ith+1,sum);,将,n,个数放入数组,numbers,后，,count(0,40);,就能求出结果,例题：,ai2755,神奇口袋,会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将,8,个皇后放在棋盘上（有,8*8,个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。,对于某个满足要求的,8,皇后的摆放方法，定义一个皇后串,a,与之对应，即,a=b,1,b,2,.b,8,，其中,b,i,为相应摆法中第,i,行皇后所处的列数。,已经知道,8,皇后问题一共有,92,组解（即,92,个不同的皇后串）。给出一个数,b,，要求输出第,b,个串。串的比较是这样的：皇后串,x,置于皇后串,y,之前，当且仅当将,x,视为整数时比,y,小。,例题：,ai2754,八皇后问题,Input,第,1,行是测试数据的组数,n,，后面跟着,n,行输入。每组测试数据占,1,行，包括一个正整数,b(1=b=92),Output,输出有,n,行，每行输出对应一个输入。输出应是一个正整数，是对应于,b,的皇后串。,Sample Input,2,1,92,Sample Output,15863724,84136275,例题：,ai2754,八皇后问题,八皇后问题可用八重循环解决。但是,N,皇后问题呢,?,递归可以用来实现任意多重循环如果有多个变量，每个变量有各自的取值范围，要覆盖这些变量值的全部组合，可以用递归实现,例题：,ai2754,八皇后问题,此题没有什么直接的递推关系，写递归就是为了起到多重循环的作用,#include,#include,#include,const,int,QueenNum,=8;,int,anResult92QueenNum,;/,存放找到的摆法,int,anQueenQueenNum,;,/,纪录当前正在尝试的摆法,int,nFoundNum,=0;,/,当前已经找到多少种摆法,void Queen(,int,n);,/,摆放第,n,行以及以后的皇后,(,行号从,0,开始算,),int,main(),int,n,b,;,Queen(0);,scanf(%d,&n,);,while(n-),scanf(%d,&b,);,for(,int,i=0;i,QueenNum;i,+),printf(%d,anResultb-1i+1);,printf(n,);,return 0;,/,摆放第,n,行以及以后的皇后,(,行号从,0,开始算,),void Queen(,int,n),if(n=,QueenNum,),/,前,QueenNum,行都成功摆好了，记下摆法,memcpy(anResultnFoundNum+,anQueen,sizeof(anQueen,);,return;,for(,int,i=0;i,QueenNum,;i+),/,尝试第,n,行所有位置,int,j;,for(j=0;j n;j+),/,对每个位置，判断是否和已经摆好的皇后冲突,if(i=,anQueenj,|,abs(i-,anQueenj,)=,abs(n,-j),break;,if(j=n),/,如果没有冲突，则第,n,行摆好了，记下来，再摆第,n+1,行,anQueenn,=i;,Queen(n+1);,例题：,ai2754,八皇后问题,递归能起到多重循环的作用，关键在于栈里保存了不同层次的循环控制变量,i,的值（对应于不同行），棋盘有几行，,i,就有几个,例题,ai1979,黑瓷砖上行走,问题描述：有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。,输入：包括多个数据集合。每个数据集合的第一行是两个整数,W,和,H,，,分别表示,x,方向和,y,方向瓷砖的数量。,W,和,H,都不超过,20,。在接下来的,H,行中，每行包括,W,个字符。每个字符表示一块瓷砖的颜色，规则如下,.,：黑色的瓷砖,#,：红色的瓷砖,：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次,当在一行中读入的是两个零时，表示输入结束。,输出：对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数,(,记数时包括初始位置的瓷砖,),例题,ai1979,黑瓷砖上行走,样例输入：,6 9,.#.,.#,.,.,.,.,.,#.#,.#.#.,0 0,样例输出：,45,例题,ai1979,黑瓷砖上行走,算法：设,f(x,y),为从点,(x,y),出发能够走过的黑瓷砖总数，而且,(,x,y,),是黑瓷砖,f(x,y)=1+f(x-1,y)+f(x+1,y),+f(x,y-1)+f(x,y+1),这里需要注意，凡是走过的瓷砖不能够被重复走过。,递归终止条件：,例题,ai1979,黑瓷砖上行走,如果,(,x,y,),是红瓷砖，则返回,0,#include,using namespace std;,const,int,MAX 22,/,方块四周加红色块，去掉边界判断，,/,使得递归统一终止于红色块,char,rectMAXMAX,;,/,返回从某点出发能走到的格子数,int,walkFrom(int,currentRow,int,currentCol,);,void main(),int,col,row,;,while(cin,col,row,col,!=0&row!=0),int,i,j,startRow,startCol,;,for(i=0;iMAX;i+),for(j,=0;j,MAX;j,+),rectij,=#;,for(i=1;i=row;i+),for(j,=1;j,rectij,;,if(rectij,=),startRow,=i;,startCol,=j;,rectij,=.;,/,人站立处是黑砖,cout,walkFrom(startRow,startCol,),endl,;,/while,int,walkFrom(int,currentRow,int,currentCol,),if(rectcurrentRowcurrentCol,=#),return 0;,else,/,本瓷砖算走过，以后不能再走了,rectcurrentRowcurrentCol,=#;,return,1+walkFrom(currentRow+1,currentCol),+walkFrom(currentRow-1,currentCol),+walkFrom(currentRow,currentCol+1),+walkFrom(currentRow,currentCol-1);,例题：,ai2694,逆波兰表达式,逆波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式,2+3,的逆波兰表示法为,+2 3,。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如,(2+3)*4,的逆波兰表示法为,*,+2 3 4,。本题求解逆波兰表达式的值，其中运算符包括,+-*/,四个。,输入数据,输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数,输出要求,输出为一行，表达式的值。,输入样例,*,+11.0 12.0+24.0 35.0,输出样例,1357.000000,表达式,表达式,-,数字,+,*,/,表达式,逆波兰表达式的递归定义,1.,#include,2.,#include,3.,double exp(),4.,char a10;,5.,scanf(%s,a);,6.,switch(a0),7.,case+:return exp()+exp();,8.,case-:return exp()-exp();,9.,case*:return exp()*exp();,10.,case/:return exp()/exp();,11.,default:return,atof(a,);,/,字符串转浮点数,12.,13.,14.,void main(),15.,16.,double,ans,;,17.,ans,=exp();,18.,printf(%f,ans,);,19.,思考题,改写此程序，要求将逆波兰表达式转换成常规表达式输出。可以包含多余的括号。,#include,#include,void exp(),char a10;,scanf(%s,a);,switch(a0),case+:,exp();,printf,(+);exp();,break;,case-:,exp();,printf,(-);exp();,break;,case*:,printf,();exp();,printf,();,printf,(*);,printf,();exp();,printf,();,break;,case/:,printf,();exp();,printf,();,printf,(/);,printf,();exp();,printf,();,break;,default:,printf(%s,a,);,return;,void main()exp();,常规表达式计算,输入为四则运算表达式，仅由数字、,+,、*、,/,、,(,、,),组成，没有空格，要求求其值,解题思想,：,表达式是个递归的定义：,表达式,项,+,项,*,/,因子,因子,表达式,(,),数字,因此对于表达式可以进行递归分析处理,#include,#include,#include,double,factor_value,();,double,term_value,();,double,expression_value,();,main(),cout,Enter an expression:;,cout,The result is ,expression_value,(),endl,;,double,expression_value,()/,求一个表达式的值,double result=,term_value,();/,求第一项的值,bool,more=true;,while(more),char op=,cin.peek,();/,从,cin,流中看一个,/,字符，但不取出,if(op=+|op=-),cin.get,();,int,value=,term_value,();,if(op=+)result+=value;,else result-=value;,else more=false;,return result;,double,term_value,()/,求一个项的值,double result=,factor_value,();/,求第一个因子的值,bool,more=true;,while(more,),char op=,cin.peek,();,if(op=*|op=/),cin.get,();,int,value=,factor_value,();,if(op=*)result*=value;,elseresult/=value;,else more=false;,return result;,double,factor_value,()/,求一个因子的值,double result=0;,char c=,cin.peek,();,if(c=(),cin.get,();,result=,expression_value,();,cin.get,();,else,while(isdigit(c,),result=10*result+c-0;,cin.get,();,c=,cin.peek,();,return result;,作业,ai2815,城堡问题,ai2790,迷宫,ai2775,文件结构图,