清华大学C9

1、.,第六章函数、递推与递归 清华大学,.,函数的概念、定义、调用和返回 带自定义函数的程序设计 递推算法 递归思想及算法实现,内 容 要 点,.,为什么需要函数？ 满足实际应用需求,6.1 函数,函数是组成 C/C+ 程序的基础 C/C+ 库中已经为用户提供了许多标准库函数 用户可以根据自己的需要选用合适的库函数 如果没有所需函数，用户可自己定义和编写一些函数,.,函数概述,函数是模块化的基本单位 主调函数与被调函数 程序、源文件与函数关系 程序中各模块关系,., int main() int a, b, sum; sum = Add( a, b ); / 函数调用 ,int Add( int

2、 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

3、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 =

4、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;

5、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 y ) return 1; else return -1; ,.,编写函数 Swap，互换两个整型数据 x、y 的值,void Swap( int x, int y ) int t

6、; 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 ) r

7、eturn year % 4 = 0 ,函数定义示例： IsLeapYear 函数,.,int mysqrt(int x) int i=1,sum=0,count=0; while (sumtimes; n_chars(ch, times); coutch; cout0) coutc; coutn; ,., double cube(double x); int main() double p,q; p = 1.2; q = cube(p); coutp=pendl; cout实参p的地址是x; ciny; coutx“ “yendl; (1) Swap( x, y ); coutx“ “ya;

8、 cinb; couta“ “bendl; Swap(); couta“ “bendl; return 0; ,void Swap() int temp; couta“ “bendl; temp = a; a = b; b = temp; couta“ “b x ; p = Max( x, p ) ; q = Min( x, q ) ; sum = sum + x ; cout“选手得分”b ) return a ; else return b ; int Min( int c , int d ) if ( c ai; coutYou have entered the matrix a:n;

9、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

10、 (arrayiaij; coutYou 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; cout=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-

11、1+i; cout“切100刀后最多可得” qn块n; 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

12、，进入函数时,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! 为例）,递推：从已知的初始条件出发，逐次去求所需要的 阶乘值

13、。 fact( 1 ) = 1 fact( 2 ) = 2 * fact( 1 ) = 2 fact( 3 ) = 3 * fact( 2 ) = 6 递归：出发点不在初始条件上，而在求解目标上。 从所求的未知项出发，逐次调用自身，直到 递归的边界（初始条件）。 递归算法比较符合人的思维方式，逻辑性强， 易于理解。,.,递归与递推的相似之处： 都基于控制结构，均涉及循环 递推：使用显式循环结构 递归：使用选择结构，通过重复性的函数调用实现循环 均涉及终止测试，都有可能发生无限循环 递推：在循环条件不满足时终止 递归：遇到初始条件时终止 理论上，能用递归解决的问题也能用递推解决。,.,计算 x

14、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-; retu

15、rn 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

16、 ) 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 (2) = 1 fibonacci (n) = fibonacci(n-1) + fibonacci(n-2) 求Fibonacci数的递归程序具有指数复杂性。,

17、求Fibonacci数,算法举例(3),.,unsigned long GetFibonacci( unsigned int n ) if( n = 2 | n = 1 ) return 1; else return GetFibonacci( n - 1 ) + GetFibonacci( n - 2 ); ,unsigned long GetFibonacci( unsigned int n ) unsigned long result, i, f1, f2; if( n = 2 | n = 1 ) return 1; f2 = 1; f1 = 1; for( i = 3; i = n; i+ ) result = f1 + f2; f1 = f2; f2 = result; return result; 非递归程序,.,几个问题的递归思想：,求数组an中各元素的和,求数组an中各元素的最大(最小)值,给数组an 排序,求一个自然数的各位数字之和,下楼问题,跳马问题,八皇后问题,.,递归信任,理解递归问题的原则 不分析复杂细节而仅考虑单一层次上的操作 不必跟踪递归调用的堆栈框架 基本递归假设 只要递归调用时的参数比原始参数在某种程度上更简单，则递归调用就一定能获得正确答案 递归心理学：这种简单递归调用一定正确工作的假设即为递归信任,.,递归实现是否检查了最简单情形 在尝试将