清华大学C 课件9.ppt

第六章函数、递推与递归 清华大学,函数的概念、定义、调用和返回 带自定义函数的程序设计 递推算法 递归思想及算法实现,内 容 要 点,为什么需要函数？ 满足实际应用需求,6.1 函数,函数是组成 C/C+ 程序的基础 C/C+ 库中已经为用户提供了许多标准库函数 用户可以根据自己的需要选用合适的库函数 如果没有所需函数，用户可自己定义和编写一些函数,函数概述,函数是模块化的基本单位 主调函数与被调函数 程序、源文件与函数关系 程序中各模块关系, int main() int a, b, sum; sum = Add( a, b ); / 函数调用 ,int Add( int x, int y ) ; / 函数声明,int Add( int x, int y ) / 函数定义 / 函数体取代函数声明尾部的分号,要使用C+函数，必须 完成如下工作： 提供函数定义 提供函数声明（原型） 调用函数,函数定义：有返回值的函数 没有返回值的函数（void函数）,void functionName (parameterList) /没有返回值 return; / 可选 ,typeName functionName (parameterList) /有返回值 return value; ,【任务6.1】素数判定,思路：设计一个函数 int checkprime(int a) ， 负责检查 a 是否为素数： 如果是素数，该函数返回 1； 否则，该函数返回 0。,#include #include using namespace std; int main( ) int a=0; cout a; if ( checkprime(a) ) / 函数调用 cout a “是素数“ endl; else cout a “不是素数“ endl; return 0; ,int checkprime( int n); / 函数声明,int checkprime(int n) / 函数定义，n为形式参数 int k=0; for (k = 2; k = sqrt(n); k = k+1) if (n % k = 0) / 如果 n 能被k整除则返回0 return 0; return 1; / n 不能被k整除则返回1 ,函数原型 int checkprime(int n);,提高算法效率 只要在 1 和 n 之间存在一个因子就可终止，并返回 n 不是素数 若 n 可被 2 整除，不需检验其它数，程序终止并返回 n 不是素数；若否，则所有偶数都不是因子，程序只需检验奇数 程序不必检验因子一直到 n，只需到sqrt(n)即可,int checkprime( int n ) int i; if( n % 2 = 0 ) return 0; for( i = 3; i = sqrt(n); i += 2 ) if( n % i = 0 ) return 0; return 1; ,问题1：本算法效率？ 每次迭代都需要计算平方根，很费时,问题2：本算法正确性？ n=1 n=2 时结果错误,int checkprime( int n ) int limit, i; limit = sqrt(n); if( n % 2 = 0 ) return 0; for( i = 3; i = limit; i += 2 ) if( n % i = 0 ) return 0; return 1; ,问题：本算法正确性？ 浮点数的存储有误差，程序的正确性依赖于机器的表示精度,int checkprime( int n ) int limit, i; limit = sqrt(n) + 1; if( n % 2 = 0 ) return 0; for( i = 3; i = limit; i += 2 ) if( n % i = 0 ) return 0; return 1; ,改进后的正确函数：,函数定义: int checkprime( int n ) checkprime 为函数名 int 是函数返回值的数据类型 n 为函数的形式参数，形式参数也要定义其数据类型,形式参数的特点： 定义函数时放在函数名后的括号中 函数未被调用时不占内存空间 函数被调用时系统为其分配内存空间 函数调用结束后释放内存空间 作用域限定在函数内，属于局部变量,函数声明（原型）： 例：int checkprime( int n) ; 要放在主函数之前，告诉系统有自定义的函数可以被调用。,函数原型确保： 编译器正确处理函数返回值 编译器检查使用的参数数目是否正确 编译器检查使用的参数类型是否正确,函数调用： 一个函数在调用子函数时，要将实在参数赋给形式参数。 实在参数是一个具有确定值的表达式。,例如：if ( checkprime(a) ),实在参数的个数及类型应与形式参数一致， 赋值时前后对应关系不能改变。,int checkprime( int n ) ,如何设计(定义)函数？ 函数名称 参数 返回值,求整数的绝对值 int abs(int x) return ; ,求两个正整数的最小公倍数 int lcm(int x, int y) ,计算n! unsigned long Factorial(int n) ,求Fibonacci数列的第n项 unsigned long Fibonacci(int n) ,求一元二次方程的根 ? Compute(double a, double b, double c) ? ,判断a是否为素数 int checkPrime(int n) ,计算整型数组元素的和 int Sum( ? ) ,将数组元素排序 ? Sort( ? ) ? ,编写函数 Add，求两个整数之和,int Add( int x, int y ) int t; t = x + y; return t; ,函数定义示例：Add 函数,int Add( int x, int y ) return x+y; ,编写函数 Compare，比较两个整型数据 x、y 的大小。若 x 等于 y 返回 0，若 x 大于 y 返回 1，若 x 小于 y 返回 -1,int Compare( int x, int y ) int t; if( x = y ) t = 0; else if( x y ) t = 1; else t = -1; return t; ,函数定义示例： Compare函数,; 多条 return 语句 int Compare( int x, int y ) if( x = y ) return 0; else if( x y ) return 1; else return -1; ,编写函数 Swap，互换两个整型数据 x、y 的值,void Swap( int x, int y ) int t; t = x; x = y; y = t; return; / 没有返回值只需直接写return语句 ,函数定义示例：Swap 函数,int IsDigit( char c ) if( c = 0 ,int IsDigit( char c ) if( c = 48 ,函数定义示例：IsDigit 函数,char TransformIntoUpperCase( char c ) if( c = a ,函数定义示例： TransformIntoUpperCase 函数,编写函数 IsLeapYear，判断某个给定年份是否为闰年,int IsLeapYear( int year ) return year % 4 = 0 ,函数定义示例： IsLeapYear 函数,int mysqrt(int x) int i=1,sum=0,count=0; while (sum=x) sum+=i; count+; i+=2; return count-1; ,求整数的平方根，取其整数部分,思考：参数的有效性、合法性判断应 放在函数里? 放在主程序里?,int mysqrt(int x) int i=0; while (i*i=x) i+; return i-1; ,函数定义示例： 我的平方根函数, int main() int times; char ch; coutch; while (ch!=q) couttimes; n_chars(ch, times); coutch; cout“Bye!n“; return 0; ,例：字符串输出,void n_chars(char, int);,void n_chars(char c, int n) while (n- 0) coutc; cout“n“; , double cube(double x); int main() double p,q; p = 1.2; q = cube(p); cout“p=“pendl; cout“实参p的地址是“ ,例：, int main() int x, y; cinx; ciny; coutx“ “yendl; (1) Swap( x, y ); coutx“ “yendl; (4) return 0; ,例：互换两个整数,输入：10 20,输出： 10 20 (1) 10 20 (2) 20 10 (3) 10 20 (4),函数调用栈框架:,值传递与数据互换问题,值传递：值复制操作 将实际参数值复制给形式参数 此过程单向不可逆 复制完成后，形参与实参没有任何关联,如何解决数据值互换问题？ 使用全局变量作为函数通信的手段 使用指针传递变量的地址,缺点： 将全局变量作为函数调用环境的一部分， 没有在函数声明头部显式给出来，不易理解 代码逻辑。, int a, b; /* 全局变量，保证所有函数都可以访问到 */ void Swap(); /* 不再需要函数参数 */ int main() cina; cinb; couta“ “bendl; Swap(); couta“ “bendl; return 0; ,void Swap() int temp; couta“ “bendl; temp = a; a = b; b = temp; couta“ “bendl; return; ,输出： 10 20 10 20 20 10 20 10,【任务6.2】给歌手打分,定义int Max( int a,int b)函数，返回a,b中的大者 定义int Min( int a,int b)函数，返回a,b中的小者 定义整型变量p，用以保存 N个数中的最大值 定义整型变量q，用以保存 N个数中的最小值 定义一个整型变量 sum 做累加用 最终得分： (sum-p-q) / (N-2),# include #include using namespace std; int Max( int , int ); int Min( int , int ); int main( ) int p = 0; int q = 100; int sum = 0，x = 0; int i = 1; for ( i = 1; i x ; p = Max( x, p ) ; q = Min( x, q ) ; sum = sum + x ; cout“选手得分”(sum-p-q)/(10-2); return 0; ,int Max( int a , int b ) if ( a b ) return a ; else return b ; int Min( int c , int d ) if ( c d ) return c ; else return d ; ,#include #include using namespace std; void print(int,int); /void print(int*,int); int main() const int n=5; int an; coutai; cout“You have entered the matrix a:n“; print(a,n); return 0; void print(int array,int size) /void print(int *array,int size) for(int k=0;k=size-1;k+) coutsetw(10)arraykendl; ,问题：一维数组作为参数, void bubble(int,int); int main() int a10; bubble(a,10); return 0; ,void bubble(int array,int size) for (int j=1;jsize;j+) for (int i=0;isize-j;i+) if (arrayiarrayi+1) int p=arrayi; arrayi=arrayi+1; arrayi+1=p; ,冒泡排序：,#include #include using namespace std; void print(int4,int); int main() const int n=5; int an4; coutaij; cout“You have entered the matrix a:n“; print(a,n); return 0; void print(int array4,int xsize) for(int i=0;i=xsize-1;i+) for(int j=0;j4;j+) coutsetw(10)arrayij; coutendl; ,问题：二维数组作为参数,6.2 递推,递推是计算机数值计算中的一个重要算法，可将复杂运算化为若干重复的简单运算，发挥计算机长于重复处理的特点。,写成一般形式： fishi = (fish i-11) * 4/5 i = 2, 3, ,5 换一种写法： fishi-1 = fishi * 5/4 +1 i = 5, 4,2,分析： . 当 i = 5 时，fish5 表示 E 醒来看到的鱼数，该数应满足 fish 5 % 5 = 1 2. 当 i = 5 时，fishi-1 表示 D 醒来看到的鱼数，这个数要满足 fish 4 = fish 5 * 5 / 4 + 1 3 . 从小到大枚举，可以把 fish5 初始化为 6 来试，之后每次增加 5 再试，直至递推到 fish1 得整数为止。,【任务6.3】的程序框图, int main( ) int fish6=1,1,1,1,1,1; / 记录每人醒来后看到的鱼数 int i=0; do fish5=fish5+5; / 让E看到的鱼数增5 for (i=4; i=1; i-) if ( fishi+1%4 != 0 ) break; / 跳出for循环 else fishi=fishi+1*5/4+1; / 计算第i人看到的鱼数 while( i=1 ); for (i=1; i=5; i+) cout fishi endl; return 0; , int main() int n=100, i=0; int q101; q0=1; for (i=1;i=n;i=i+1) qi=qi-1+i; cout“切100刀后最多可得” qn“块“endl; return 0; ,【任务6.4】王小二切饼,5051,递归算法在可计算性理论中占有重要地位，它是算法 设计的有力工具，对于拓展编程思路非常有用。,6.3 递归及其实现,递归的目的 简化复杂问题的手段： 将问题逐步化简（递简），在化简过程中保持原问题的性质不变，直到问题最简，可以轻易地获得答案；然后将简化问题的答案组装成原始问题的解（回归） 递归示例 n! = 1 2 3 n: n! = (n-1)! n; 1! = 1 xn = x x x x: xn = xn-1 x; x0 = 1,或结点和与结点：,A 为与结点，A 的最终取值为 C 结点的值，为了求得 C的值， 先求出 B结点的值，C 是 B 的 函数。,与结点,A 结点的值最终为 D 的值， 为了求 D 需要先求 B 和 C。 先求左边的点才能求最右边 的点。,例如：求 n ! 的与或图,直接可解结点,C = 1 D = 2*C = 2 B = D = 2 E = 3*B = 3*2 = 6 A = E = 6,例如：求 3 ! 的与或图,求 3! 的递归调用与返回,求 3! 的程序框图1,求 3! 的程序框图2, unsigned long fact( unsigned int ); int main() int n=0; coutn; coutn“的阶乘为“fact(n)endl; return 0; unsigned long fact( unsigned int n ) unsigned long result; if( n = 1 ) result = 1; else result = n * fact( n - 1 ) ; return result; ,【任务6.5】求n!,3,n,main,main 函数栈框架,函数调用栈框架,fact,第一次以 3 为参数调用 fact，进入函数时,3,n,result,fact,第二次以 2 为参数调用 fact，进入函数时,fact,2,n,result,fact,第三次以 1 为参数调用 fact，进入函数时,fact,fact,1,n,result,fact,第三次以 1 为参数调用 fact，退出函数前,fact,fact,1,1,n,result,fact,第二次以 2 为参数调用 fact，退出函数前,fact,2,2,n,result,fact,第一次以 3 为参数调用 fact，退出函数前,3,6,n,result,3,n,main,递归调用结束后的 main 函数栈框架,递归与递推的比较（以求 n! 为例）,递推：从已知的初始条件出发，逐次去求所需要的 阶乘值。 fact( 1 ) = 1 fact( 2 ) = 2 * fact( 1 ) = 2 fact( 3 ) = 3 * fact( 2 ) = 6 递归：出发点不在初始条件上，而在求解目标上。 从所求的未知项出发，逐次调用自身，直到 递归的边界（初始条件）。 递归算法比较符合人的思维方式，逻辑性强， 易于理解。,递归与递推的相似之处： 都基于控制结构，均涉及循环 递推：使用显式循环结构 递归：使用选择结构，通过重复性的函数调用实现循环 均涉及终止测试，都有可能发生无限循环 递推：在循环条件不满足时终止 递归：遇到初始条件时终止 理论上，能用递归解决的问题也能用递推解决。,计算 x n,long double CalPower( long double x, int n ) long double result; if( n = 0 ) result = 1; else result = x * CalPower( x, n 1 ) ; return result; ,算法举例(1),求两个正整数的最大公约数,算法举例(2),unsigned int gcd(unsigned int x, unsigned int y) unsigned int t; t = x y ? x : y; while( x % t != 0 | y % t != 0 ) t-; return t; ,穷举法,欧氏算法,步骤 1：x 整除以 y，记余数为 r 步骤 2：若 r 为 0，则最大公约数即为 y，算法结束 步骤 3：否则将 y 作为新 x，将 r 作为新 y，重复上述步骤 unsigned int gcd(unsigned int x, unsigned int y) unsigned int r; while( 1 ) r = x % y; if( r = 0 ) return y; x = y; y = r; ,求两个正整数的最大公约数,unsigned int gcd(unsigned int x, unsigned int y) while( y != 0 ) unsigned int r = x%y; x = y; y = r; return x; ,unsigned int gcd(unsigned int x, unsigned int y) if( x%y = 0 ) return y; return gcd(y,x%y); ,递归算法,求两个正整数的最大公约数,1, 1, 2, 3, 5, 8, 13, 21, fibonacci (1) = 1 fibonacci