第七讲递归精要.ppt

* 例5：2788二叉树 如图所示，由正整数1，2，3……组成了一颗二叉树。从某一个节点到根节点（编号为1）都有一条唯一的路径，例如从10到1的路径为(10,5,2,1)，从4到1的路径为(4,2,1)，从1到1的路径上只包括一个结点，路径为(1) 对两个结点x和y，假设它们到根结点1的路径分别是(x1,x2,…,1)和(y1,y2,…,1)，显然x=x1,y=y1，则必然存在两个正整数i和j，使得从xi和yj开始，有xi=yj， xi+1=yj+1，….。 问题，给定x和y，求xi(也就是yi) * POJ2788解题思路 任意一个数，一直对2做整数除法，就能走到它的上层结点 设common(x,y)表示x和y最接近的公共子结点，则比较x和y的值可以得到三种情况： x=y：则common(x,y)=x=y； xy：则common(x,y)= common(x/2,y)； xy：则common(x,y)= common(x,y/2)； * 例6：POJ2694 逆波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值，其中运算符包括 + - * / 四个。 输入数据 输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数 * + 11.0 12.0 + 24.0 35.0 输出要求 输出为一行，表达式的值 1357.000000 * POJ2694 问题：递归函数如何构造？ 递归函数如何定义？ 递归函数的出口如何定义？ 如何将递归函数定义与对输入数据的扫描结合起来？ 1.???????? #include stdio.h 2.???????? #includemath.h 3.???????? double exp(){ 4.???????? char a[10]; 5.???????? scanf(%s, a); 6.???????? switch(a[0]){ 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.???????} * 例7：常规表达式计算 输入为四则运算表达式，仅由数字、+、－、*、/ 、(、) 组成，没有空格，要求求其值 * 表达式 项 + － 项 * / 因子 解题思想 表达式是个递归的定义： 因子 表达式 ( ) 数字 因此对于表达式可以进行递归分析处理 #include iostream.h #include string.h #include ctype.h double factor_value(); double term_value(); double expression_value(); main() { cout Enter an expression: ; cout expression_value() endl; } * 问题 如何定义三个函数？ double factor_value(); double term_value(); double expression_value(); 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