第九章 递归.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《第九章 递归.ppt》由会员分享,可在线阅读,更多相关《第九章 递归.ppt(48页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第九章递归第九章递归9.1递归的基本思想递归的基本思想9.2例题:菲波那契数列例题:菲波那契数列9.3例题:二叉树例题:二叉树9.4例题:逆波兰表达式例题:逆波兰表达式9.5例题:放苹果例题:放苹果9.6例题:红与黑例题:红与黑9.7例题:八皇后问题例题:八皇后问题9.8例题:木棍问题例题:木棍问题递归的基本思想l总体思想:将总体思想:将待待求解问题的解看作输入变量求解问题的解看作输入变量x的函数的函数f(x),通过寻找函数通过寻找函数g,使得,使得f(x)=g(f(x-1),并且已知并且已知f(0)的值,通过的值,通过f(0)和和g求出求出f(x)的的值。值。l这种思想可以推广到多个输入变量
2、这种思想可以推广到多个输入变量x,y,z等,等,x-1也可以推广到也可以推广到 x-x1,只要递归朝着出口的方向,只要递归朝着出口的方向走就可以了。走就可以了。int Factorial(int n)if(n=0)return 1;else return n*Factorial(n-1);求阶乘n!的递归程序#include void main()printf(“4!=%dn”,Factorial(4);阶乘的栈 主程序主程序参数参数4 4*Factorial(3)参数参数3 3*Factorial(2)参数参数2 2*Factorial(1)参数参数1 1*Factorial(0)参数参数0
3、 Factorial(0)1 1 2 6 24递归解决问题的关键1)找出递推公式找出递推公式2)找到递归终止条件找到递归终止条件注意事项:注意事项:由于函数的局部变量是存在栈上的,如果有由于函数的局部变量是存在栈上的,如果有体积大的局部变量,比如数组,而递归层次又可能很深体积大的局部变量,比如数组,而递归层次又可能很深的情况下,也许会导致栈溢出,因此可以考虑使用全局的情况下,也许会导致栈溢出,因此可以考虑使用全局数组或动态分配数组数组或动态分配数组汉诺塔问题A B以以C柱为中转,将盘从柱为中转,将盘从A柱移动到柱移动到B柱上,一次只柱上,一次只能移动一个盘,而且大盘不能压在小盘上面能移动一个盘
4、,而且大盘不能压在小盘上面 C汉诺塔问题将将N N个盘子从个盘子从A A柱移动到柱移动到B B柱,用柱,用C C柱做中转,柱做中转,按以下步骤:按以下步骤:1)1)先将先将N-1N-1个盘子,以个盘子,以B B为中转,从为中转,从A A柱移动到柱移动到C C柱,柱,2)2)将最后一个盘子从将最后一个盘子从A A移动到移动到B B3)3)将将C C柱上的柱上的N-1N-1个盘子,以个盘子,以A A为中转,移动到为中转,移动到B B柱柱A BC终止条件?终止条件?N=1N=1时,直接移动盘子即可,不用递归时,直接移动盘子即可,不用递归#include using namespace std;/将将
5、n n个盘子从个盘子从a a柱移动到柱移动到b b柱,用柱,用c c柱做中转柱做中转void Hanoi(int n,char a,char b,char c)if(n=1)cout a b endl;return;/先将先将n-1n-1个盘子,以个盘子,以b b为中转,从为中转,从a a柱移动到柱移动到c c柱,柱,Hanoi(n-1,a,c,b);/将一个盘子从将一个盘子从a a移动到移动到b b cout a b endl;/将将c c柱上的柱上的n-1n-1个盘子,以个盘子,以a a为中转,移动到为中转,移动到b b柱柱 Hanoi(n-1,c,b,a);汉诺塔问题void main(
6、)int N;cout Please input disc number:N;cout The solution is:BA-CB-CA-BC-AC-BA-B汉诺塔问题菲波那契数列菲波那契数列l问题描述问题描述 菲波那契数列是指这样的数列:数列的第一个和第二个数菲波那契数列是指这样的数列:数列的第一个和第二个数都为都为1 1,接下来每个数都等于前面,接下来每个数都等于前面2 2个数之和。给出一个正个数之和。给出一个正整数整数a a,要求菲波那契数列中第,要求菲波那契数列中第a a个数是多少。个数是多少。递归公式:递归公式:f(i)=f(i-1)+f(i-2)初值:初值:f(0)=1,f(1)=
7、1 l输入数据输入数据 第第1 1行是测试数据的组数行是测试数据的组数n n,后面跟着,后面跟着n n行输入。每组测试数行输入。每组测试数据占据占1 1行,包括一个正整数行,包括一个正整数a(1=a=20)a(1=a=20)。l输出要求输出要求 n n行,每行输出对应一个输入。输出应是一个正整数,为菲行,每行输出对应一个输入。输出应是一个正整数,为菲波那契数列中第波那契数列中第a a个数的大小。个数的大小。菲波那契数列菲波那契数列#include int f(int a)if(a=1|a=2)return 1;return f(a-1)+f(a-2);void main()int n;scan
8、f(%d,&n);for(int i=1;i=n;i+)int a;scanf(%d,&a);printf(%dn,f(a);二叉树二叉树二叉树二叉树l问题描述问题描述由正整数由正整数 1,2,3,.组成了一棵无限大的二叉树。从组成了一棵无限大的二叉树。从某一个结点到根结点(编号某一个结点到根结点(编号1)都有一条唯一的路)都有一条唯一的路径,比如从径,比如从10 到根结点是到根结点是(10,5,2,1),从,从4 到根结到根结点是点是(4,2,1),从结点,从结点 1 到根结点是到根结点是(1)。对于两个。对于两个结点结点x 和和y,假设他们到根结点的路径分别是,假设他们到根结点的路径分别是
9、(x1,x2,.,1)和和(y1,y2,.,1)(显然有(显然有x=x1,y=y1),则存在两个正整数),则存在两个正整数i 和和j,使得从,使得从xi和和 yj开始,开始,有有xi=yj,x i+1=yj+1,x i+2=yj+2,.现在的问题是现在的问题是给定给定x和和y,求,求xi(yj)二叉树二叉树l输入数据输入数据 输入两个正整数输入两个正整数x x和和y y,x1000,y1000 x1000,y1000。l输出要求输出要求 输出只有一个正整数输出只有一个正整数x xi i。l解题思路(求树上任意两个节点的最近公共子节点)解题思路(求树上任意两个节点的最近公共子节点)分析树的结构,
10、对每个数做整除分析树的结构,对每个数做整除2 2,就走到它的上层结点。,就走到它的上层结点。每次让较大的一个数向上走,直到两个结点相遇。每次让较大的一个数向上走,直到两个结点相遇。设设common(x,ycommon(x,y)表示整数表示整数x x和和y y的最近公共子节点,根据的最近公共子节点,根据x x和和y y的值,有:的值,有:(1)x(1)x与与y y相等,则相等,则common(x,ycommon(x,y)等于等于x x并且等于并且等于y y;(2)x(2)x大于大于y y,common(x,ycommon(x,y)等于等于common(x/2,y)common(x/2,y);(3
11、)x(3)x小于小于y y,则,则common(x,ycommon(x,y)等于等于common(xcommon(x y/2)y/2);二叉树二叉树#include int common(int x,int y)if(x=y)return x;if(x y)return common(x/2,y);return common(x,y/2);void main()int m,n,result;scanf(%d%d,&m,&n);printf(%dn,common(m,n);逆波兰表达式逆波兰表达式l问题描述问题描述 逆波兰表达式是一种把运算符前置的算术表达式,例如逆波兰表达式是一种把运算符前置的
12、算术表达式,例如2+32+3的逆波兰表示法为的逆波兰表示法为+2 3+2 3。逆波兰表达式的优点是运算符之间不必有优先级关系,也逆波兰表达式的优点是运算符之间不必有优先级关系,也不须用括号,例如不须用括号,例如(2+3)*4(2+3)*4的逆波兰表示法为的逆波兰表示法为*+2 3 4+2 3 4。输入并求解逆波兰表达式的值,其中运算符包括输入并求解逆波兰表达式的值,其中运算符包括+-*/+-*/。l输入数据输入数据 运算符和运算数之间用空格分隔,运算数是浮点数运算符和运算数之间用空格分隔,运算数是浮点数 l输出要求输出要求 输出为表达式的值。输出为表达式的值。表达式表达式表达式表达式-数字数字
13、+*/表达式表达式逆波兰表达式的递归定义在递归函数中,针对当前的输入,有五种情况:在递归函数中,针对当前的输入,有五种情况:1 1)输入是常数,则表达式的值就是这个常数;)输入是常数,则表达式的值就是这个常数;2 2)输入是)输入是+,则表达式的值是再读入两个表达式并计算,然,则表达式的值是再读入两个表达式并计算,然后将它们相加;后将它们相加;3 3)输入是)输入是-;4 4)输入是)输入是*;5 5)输入是)输入是/;逆波兰表达式逆波兰表达式#include#include double exp()char a10;scanf(%s,a);switch(a0)case+:return exp
14、()+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);常规表达式计算常规表达式计算输入为四则运算表达式,仅由数字、输入为四则运算表达式,仅由数字、+、*、/、(、)组成,没有空格,要求求其值组成,没有空格,要求求其值表达式表达式项项+解题思想:表达式是个递归的定义:项项*/因子因子因子因子表达式()数字因此对于表达式可以进行递归分析处理#inc
15、lude#include#include double factor_value();double term_value();double expression_value();main()printf(Enter an expression:n);cout The result is expression_value()endl;double expression_value()/求一个表达式的值求一个表达式的值 double result=term_value();/求第一项的值求第一项的值 bool more=true;while(more)char op=cin.peek();/从从c
16、in流中看一个字符,但不取流中看一个字符,但不取出出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
17、=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;放苹果放苹果l问题描述
18、问题描述 把把 M个同样的苹果放在个同样的苹果放在N个同样的盘子里,允许有个同样的盘子里,允许有的盘子空着,问共有多少种不同的分法?的盘子空着,问共有多少种不同的分法?(用用K 表表示示)注意:注意:5,1,1 和和 1,5,1 是同一种分法。是同一种分法。l输入数据输入数据 第一行是测试数据的数目第一行是测试数据的数目t(0=t=20)。以下每)。以下每行包含两个整数行包含两个整数M 和和N,以空格分开。,以空格分开。1=M,Na,至少有至少有d-a个盘子是空的,去掉这些空盘子对摆放苹果方法数目个盘子是空的,去掉这些空盘子对摆放苹果方法数目不产生影响;即不产生影响;即if(da)f(a,d)
19、=f(a,a)当当da)f(a,d)=f(a,a);else f(a,d)=f(a,d-1)+f(a-d,d);出口条件:当出口条件:当d=1时,所有苹果都必须放在一个盘子里,所以返时,所有苹果都必须放在一个盘子里,所以返回回1;当;当a=0没有苹果可放时,所有盘子都是空的,这当然是一种没有苹果可放时,所有盘子都是空的,这当然是一种放法,所以也返回放法,所以也返回1;递归的两条路,第一条;递归的两条路,第一条d会逐渐减少,终会会逐渐减少,终会到达出口到达出口d=1;第二条第二条a会逐渐减少,因为会逐渐减少,因为da时,我们会时,我们会return f(a,a)。所以终会到达出口。所以终会到达出
20、口a=0int 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);放苹果放苹果#include int count(int x,int y)if(y=1|x=0)return 1;if(x y)return count(x,x);return count(x,y-1)+count(x-y,y);void main()int t,m,n;scanf(%d,&t);for(int i=0;i t;i+)scanf(%d%d,&m,&n);printf(%dn,count(m,n);红与黑红
21、与黑 l问题描述问题描述 有一间长方形的房子,地上铺了红色、黑色两种颜色的正有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上,只能向相邻的方形瓷砖。你站在其中一块黑色的瓷砖上,只能向相邻的黑色瓷砖移动。请写一个程序,计算你总共能够到达多少黑色瓷砖移动。请写一个程序,计算你总共能够到达多少块黑色的瓷砖。块黑色的瓷砖。l输入数据输入数据 输入两个整数输入两个整数W 和和H,分别表示,分别表示x 方向和方向和y方向瓷砖的数量。方向瓷砖的数量。W和和H都不超过都不超过20。在接下来的。在接下来的H行中,每行包括行中,每行包括W个字符。个字符。每个字符表示一块瓷砖颜
22、色。每个字符表示一块瓷砖颜色。1).黑色的瓷砖;黑色的瓷砖;2)#白白色的瓷砖;色的瓷砖;3)当前黑色的瓷砖。当在一行中读入的是当前黑色的瓷砖。当在一行中读入的是两个零时,表示输入结束。两个零时,表示输入结束。l输出要求输出要求 输出从初始位置出发到达的瓷砖数输出从初始位置出发到达的瓷砖数(记数时包括初始位置记数时包括初始位置)。红与黑红与黑 l解题思路解题思路这个题目可描述成给定一点,计算它所在连通区这个题目可描述成给定一点,计算它所在连通区域的面积。需要考虑的问题包括矩阵的大小,以域的面积。需要考虑的问题包括矩阵的大小,以及从某一点出发向上下左右行走时,可能遇到的及从某一点出发向上下左右行
23、走时,可能遇到的三种情况:出了矩阵边界、遇到三种情况:出了矩阵边界、遇到.、遇到、遇到#。设设f(x,y)为从为从(x,y)出发能够走过的黑瓷砖总数,则出发能够走过的黑瓷砖总数,则(1)当出了矩阵边界或遇到当出了矩阵边界或遇到#时时 f(x,y)=0 (2)当遇到当遇到.时时 f(x,y)=1+f(x-1,y)+f(x+1,y)+f(x,y-1)+f(x,y+1)要注意,凡是走过的瓷砖不能够被重复走过。可要注意,凡是走过的瓷砖不能够被重复走过。可以通过每走过一块瓷砖就将它作标记的方法保证以通过每走过一块瓷砖就将它作标记的方法保证不重复计算任何瓷砖。不重复计算任何瓷砖。红与黑红与黑#includ
24、e 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;while(scanf(%d%d,&H,&W)&W!=0&H!=0)for(i=0;i W;i+)scanf(%s,zi);/读入矩阵读入矩阵 for(i=0;i W;i+)for(j=0;j H;j+)i
25、f(zij=)printf(%dn,f(i,j);八皇后问题八皇后问题 l问题描述问题描述国际象棋中皇后可以在横、竖、斜线上不限步数地吃掉其他国际象棋中皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将棋子。如何将8个皇后放在棋盘上(个皇后放在棋盘上(8*8个方格),使它们谁个方格),使它们谁也不能被吃掉!这就是八皇后问题。对于某个满足要求的也不能被吃掉!这就是八皇后问题。对于某个满足要求的8皇后的摆放方法,定义一个皇后串皇后的摆放方法,定义一个皇后串a与之对应,即与之对应,即a=b1b2.b8,其中,其中bi为相应摆法中第为相应摆法中第i行皇后所处的列数。已行皇后所处的列数。已知知8皇后
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第九章 递归 第九
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内