第九篇 递归.ppt

第九章递归 9.1递归的基本思想 9.2例题：菲波那契数列 9.3例题：二叉树 9.4例题：逆波兰表达式 9.5例题：放苹果 9.6例题：红与黑 9.7例题：八皇后问题 9.8例题：木棍问题 递归的基本思想 总体思想：将待求解问题的解看作输入变量x的函数f(x)，通过寻找函数g，使得f(x)=g(f(x-1))，并且已知f(0)的值，通过f(0)和g求出f(x)的值。 这种思想可以推广到多个输入变量x,y,z等，x-1也可以推广到 x-x1，只要递归朝着出口的方向走就可以了。 int Factorial(int n) { if (n == 0) return 1; else return n*Factorial(n-1);} 阶乘的栈 汉诺塔问题 菲波那契数列 问题描述 菲波那契数列是指这样的数列：数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。给出一个正整数a，要求菲波那契数列中第a个数是多少。 递归公式： f(i) =f(i-1)+f(i-2) 初值： f(0)=1，f(1)=1 输入数据 第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1=a=20)。 输出要求 n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数的大小。 菲波那契数列 #include stdio.h int f(int a) { if( a==1||a==2) return 1; return f(a-1)+f(a-2); } 二叉树 二叉树 问题描述 由正整数 1, 2, 3, ...组成了一棵无限大的二叉树。从某一个结点到根结点（编号1）都有一条唯一的路径，比如从10 到根结点是(10, 5, 2, 1)，从4 到根结点是(4, 2, 1)，从结点 1 到根结点是(1)。对于两个结点x 和y，假设他们到根结点的路径分别是(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) 二叉树 输入数据 输入两个正整数x和y，x≤1000,y≤1000。 输出要求 输出只有一个正整数xi。 解题思路（求树上任意两个节点的最近公共子节点） 分析树的结构，对每个数做整除2，就走到它的上层结点。 每次让较大的一个数向上走，直到两个结点相遇。 设common(x,y)表示整数x和y的最近公共子节点，根据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)； 二叉树 #include stdio.h 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(%d\n, common( m, n)); } 逆波兰表达式 问题描述 逆波兰表达式是一种把运算符前置的算术表达式，例如2+3的逆波兰表示法为+ 2 3。 逆波兰表达式的优点是运算符之间不必有优先级关系，也不须用括号，例如(2+3)*4的逆波兰表示法为* + 2 3 4。 输入并求解逆波兰表达式的值，其中运算符包括+ - * /。 输入数据 运算符和运算数之间用空格分隔，运算数是浮点数 输出要求 输出为表达式的值。 逆波兰表达式 #include stdio.h #includemath.h double exp( ) { char a[10]; scanf(%s, a); switch(a[0]) { case +: return exp( ) + exp( ); case -: return exp( ) - exp( ); case *: return exp( ) * exp( ); case /: return exp( ) / exp( ); default: return atof(a); }