最新-C--课件9-PPT

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

2、 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】素数判定思路：设计一个函数

3、 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; elsecout a 不是素数 endl; return 0;int checkprime( int n); / 函数声明int checkprime(int n) / 函数定义，n为形式参数 int k=0; for (k = 2; k = sq

4、rt(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

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

6、 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;if( n 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 r

7、eturn -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 & c = 48 & c = a & c = z ) / az的ASCII值为61H7AH / AZ的ASCII值为41H5AH return c a + A; else return c;函数定义示例： TransformIntoUpperCase 函数编写函数 IsLea

8、pYear，判断某个给定年份是否为闰年int IsLeapYear( int year ) return year % 4 = 0 & year % 100 != 0 | year % 400 = 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)

9、i+; return i-1;函数定义示例： 我的平方根函数int main() int times; char ch; coutch; while (ch!=q) couttimes; n_chars(ch, times); coutThe value of times is timesendl; coutch; cout0) coutc; coutn; double cube(double x);int main() double p,q; p = 1.2; q = cube(p); coutp=pendl; cout实参p的地址是&pendl; coutq=qendl; return 0

10、;double cube(double x) coutx=xendl; cout形参x的地址是&xx; ciny; coutx“ “yendl; (1) Swap( x, y ); coutx“ “yendl; (4) return 0;例：互换两个整数void Swap( int x, int y ) int temp; coutx“ “yendl; (2) temp = x; x = y; y = temp; coutx“ “ya; cinb; couta“ “bendl; Swap(); couta“ “bendl; return 0;void Swap() int temp; cout

11、a“ “bendl; temp = a; a = b; b = temp; couta“ “bendl; return;输出：10 20 10 20 20 1020 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#includeusing namespace std;int Max

12、( 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=10; i = i+1 ) cout“请第” i “位裁判给分” 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 d ) return c ; else re

13、turn d ; #include#includeusing namespace std;void print(int,int); /void print(int*,int);int main() const int n=5; int an; coutEnter matrix a:n; for(int i=0;iai; coutYou 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=siz

14、e-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#includeusing namespace std;void prin

15、t(int4,int);int main() const int n=5; int an4; coutEnter matrix a:n; for(int i=0;in;i+)for(int j=0;jaij; 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; i-) if ( fishi+1%4 != 0 ) break

16、; / 跳出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】王小二切饼 1 2 4 7 11切0刀 切1刀 切2刀 切3刀 切4刀 递推公式： q(0) = 1 q(n) = q(n-1) + n5051 递归

17、算法在可计算性理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。6.3 递归及其实现递归的目的简化复杂问题的手段： 将问题逐步化简（递简），在化简过程中保持原问题的性质不变，直到问题最简，可以轻易地获得答案；然后将简化问题的答案组装成原始问题的解（回归）递归示例n! = 1 2 3 n: n! = (n-1)! n; 1! = 1xn = x x x x: xn = xn-1 x; x0 = 1或结点和与结点：ABC条件 Z 条件 !ZABGZ1 Z2 ZnC条件为 Z1 , Z2 , , Zn A 取值为 B 或 C , 或 G或结点 A 为与结点，A 的最终取值为C 结

18、点的值，为了求得 C的值，先求出 B结点的值，C 是 B 的函数。ABCABDC与结点 A 结点的值最终为 D 的值，为了求 D 需要先求 B 和 C。先求左边的点才能求最右边的点。例如：求 n ! 的与或图直接可解结点C = 1D = 2*C = 2B = D = 2E = 3*B = 3*2 = 6A = E = 6例如：求 3 ! 的与或图求 3! 的递归调用与返回 求 3! 的程序框图1求 3! 的程序框图2unsigned long fact( unsigned int );int main()int n=0;coutn;coutn的阶乘为fact(n)endl;return 0;u

19、nsigned long fact( unsigned int n ) unsigned long result; if( n = 1 )result = 1; elseresult = n * fact( n - 1 ) ; return result;【任务6.5】求n!3nmainmain 函数栈框架函数调用栈框架mainfact第一次以 3 为参数调用 fact，进入函数时3nresultmainfact第二次以 2 为参数调用 fact，进入函数时fact2nresultmainfact第三次以 1 为参数调用 fact，进入函数时factfact1nresultmainfact第三

20、次以 1 为参数调用 fact，退出函数前factfact11nresultmainfact第二次以 2 为参数调用 fact，退出函数前fact22nresultmainfact第一次以 3 为参数调用 fact，退出函数前36nresult3nmain递归调用结束后的 main 函数栈框架递归与递推的比较（以求 n! 为例）递推：从已知的初始条件出发，逐次去求所需要的 阶乘值。 fact( 1 ) = 1fact( 2 ) = 2 * fact( 1 ) = 2fact( 3 ) = 3 * fact( 2 ) = 6 递归：出发点不在初始条件上，而在求解目标上。 从所求的未知项出发，逐次

21、调用自身，直到 递归的边界（初始条件）。 递归算法比较符合人的思维方式，逻辑性强， 易于理解。递归与递推的相似之处： 都基于控制结构，均涉及循环 递推：使用显式循环结构 递归：使用选择结构，通过重复性的函数调用实现循环 均涉及终止测试，都有可能发生无限循环 递推：在循环条件不满足时终止 递归：遇到初始条件时终止 理论上，能用递归解决的问题也能用递推解决。计算 x nlong double CalPower( long double x, int n ) long double result; if( n = 0 ) result = 1; else result = x * CalPower(

22、 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,

23、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 (2) = 1 fibonacci (n) = fibonacci(n-1) + fibonacci(n-2)求Fibonacci数的递归程序具有指数复杂性。求Fibonacci数算法举例(3)unsigned long GetFibonacci(