《算法语言与数据结构》由会员分享，可在线阅读，更多相关《算法语言与数据结构（174页珍藏版）》请在金锄头文库上搜索。
1、算法语语言与数据结结构信息与物流管理系王健西安财经学院管理学院西安财经学院管理学院信息信息与与物流管理系物流管理系第5章 函数信息信息与与物流管理系物流管理系第5章 函数数IntroductionIntroduction1 1Main titleMain title2 2ExamplesExamples3 3ConclusionConclusion4 4信息信息与与物流管理系物流管理系/ * / * 程 序：6_3.cpp（验证素数程序） * / * 作 者：wuwh * / * 编制时间：2002年10月20日 * / * 主要功能：可验证某数是否为素数 * / * #include / 预
2、编译命令 #include / 预编译命令 int checkprime( int );/ 子函数声明int main()/ 主函数 int a=0;/ 定义整型变量，初始化为0 cout a; / 键盘输入一个整数/ 用实参a调用子函数，该子函数的 / 返回值作为if语句的分支条件 if ( checkprime(a) ) / checkprime(a)为1 cout a; if ( checkprime(a) ) bool checkprime(int b) int k=0;for (k=2; k#includeint Max( int , int ) int Min( int , int
3、 )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 ; coutb ) return a ;else return b ; int Min( int c , int d ) if ( c / 预编译命令 const int n = 6; / 定义常量 n 为 6 const int k = 4; / 定义常量 k 为 4int SOP(int m, int l)
4、; / 声明函数SOPint power(int p, int q);/ 声明函数power信息信息与与物流管理系物流管理系/ 输出结果, 其中SOP(n,k)为被调用函数int main()/ 主函数 cout () 信息信息与与物流管理系物流管理系形式参数与实在参数1、形式参数是在定义函数时放在函数名后括号中的参数。在未进行函数调用时，并不对形式参数分配内存单元。在发生 函数调用时，立刻给形式参数分配内存单元。调用结束后， 释放掉行参所占的内存单元。2、因此，形参变量属于局部变量，其作用域在它所在的函数体内。3、在定义函数的时候，必须指定形参变量的类型，如下所示int power(int
5、p, int n) / 函数体c信息信息与与物流管理系物流管理系4、实在参数是一个具有确定值的表达式。函数在调用 时，将实在参数赋给形式参数。 比如，主函数调用SOP(n,k)，这时，n,k为实在 参数，n的值为6，k的值为4。在被调用函数定义中 ，int SOP(m,l) 中的 m, l 为形式参数，在SOP被 调用时，系统给 m, l 这两个形式参数分配了内存单 元。之后，n 的值 6 赋给 m; k 的值 4 赋给 l。信息信息与与物流管理系物流管理系power( i, l ) 处在 SOP( m, l ) 函数中，表示SOP函数去调用 power 函 数。其中 i, l 为实在参数，而
6、 int power( p, q )中的 p, q 为形式参数 。比如，执行 SOP( 6, 4 )时，l=4, m=6, 当 i=1 时， sum = sum + power( 1, 4 )这里 1，4 为实在参数，调用power( p, q )，两个形式参数 p, q 分别被赋以 1，4 。信息信息与与物流管理系物流管理系信息信息与与物流管理系物流管理系递推是计算机数值计算中的一个重要算法，可以将复杂的运算化为若干重复的简单运算，充分发挥计算机长于重复处理的特点，现举一例递 推信息信息与与物流管理系物流管理系【例例5.35.3】A A、B B、C C、D D、E E五人合伙夜间捕鱼，凌晨时
7、五人合伙夜间捕鱼，凌晨时 都疲惫不堪，各自在河边的树丛中找地方睡着了，都疲惫不堪，各自在河边的树丛中找地方睡着了， 日上三竿，日上三竿，A A第一个醒来，他将鱼平分作五份，把第一个醒来，他将鱼平分作五份，把 多余的一条扔回湖中，拿自己的一份回家去了，多余的一条扔回湖中，拿自己的一份回家去了，B B 第二个醒来，也将鱼平分为五份，扔掉多余的一条第二个醒来，也将鱼平分为五份，扔掉多余的一条 ，只拿走自己的一份，接着，只拿走自己的一份，接着C C、D D、E E依次醒来，依次醒来， 也都按同样的办法分鱼。问五人至少合伙捕到多少也都按同样的办法分鱼。问五人至少合伙捕到多少 条鱼？每个人醒来后看到的鱼数
8、是多少条？条鱼？每个人醒来后看到的鱼数是多少条？信息信息与与物流管理系物流管理系解题思路解题思路: :假定假定A A、B B、C C、D D、E E 五人的编号分别为五人的编号分别为1 1 、2 2、3 3、4 4、5 5，整数数组，整数数组 fishk fishk 表示第表示第 k k 个人个人 所看到的鱼数。所看到的鱼数。fish1 fish1 表示表示A A所看到的鱼数，所看到的鱼数， fish2 fish2 表示表示 B B 所看到的鱼数所看到的鱼数fish1 fish1 为五人合伙捕鱼的总鱼数为五人合伙捕鱼的总鱼数 fish2=(fish1-1)*4/5fish2=(fish1-1)
9、*4/5 fish3=(fish2-1)*4/5fish3=(fish2-1)*4/5 fish4=(fish3-1)*4/5fish4=(fish3-1)*4/5 fish5=(fish4-1)*4/5fish5=(fish4-1)*4/5信息信息与与物流管理系物流管理系写成一般式 fish i = ( fish i - 1 1 ) * 4 / 5 i = 2, 3, ,5这个公式可用于知 A 看到的鱼数去推算 B 看到的，再推算 C 看到的 ，.。现在要求的是 A 看到的，能否倒过来，先知 E 看到的再反 推 D 看到的，直到A看到的。为此将上式改写为：fish i-1 = fish i
10、* 5 / 4 +1 i = 5, 4,2信息信息与与物流管理系物流管理系分析上式. 当 i = 5 时，fish 5 表示 E 醒来所看到的鱼数，该数应满足被整除后 余，即fish 5 % 5 = 12. 当 i = 5 时，fish i-1 表示 D 醒来所看到的鱼数，这个数既要满足fish 4 = fish 5 * 5 / 4 + 1 又要满足fish 4 % 5 = 1显然，fish 4 不能不是整数，这个结论同样可以用至 fish 3 , fish 2 和 fish 1 信息信息与与物流管理系物流管理系3 . 按题意要求 5 人合伙捕到的最少鱼数，可以从小往大枚举，可以先让 E 所看
11、到的鱼数最少为 6 条，即 fish 5 初始化为 6 来试，之后每次增加 5 再试，直至递推到 fish 1 得整数且除以 5 之后的余数为 1。根据上述思路，我们可以构思如下的程序框图：信息信息与与物流管理系物流管理系信息信息与与物流管理系物流管理系该图可分为三部分(1) 是说明部分：包含定义数组 fish6，并初始化为 1 和 定义循环控制变量 i，并初始化为 0。(2) 是 do.while 直到型循环，其循环体又含两块：(2).1 是枚举过程中的 fish5 的初值设置，一开始 fish5=1+5; 以后每次增 5。(2).2 是一个 for 循环，i 的初值为 4，终值为 1，步长
12、 为 -1，该循环的循环体是一个分支语句，如果 fishi+1不能被 4 整除，则跳出 for 循环（使用 break 语句）; 否则，从 fishi+1 算出 fishi。信息信息与与物流管理系物流管理系当由 break 语句让程序退出循环时，意味着某人看到的鱼数不是整 数，当然不是所求，必须令fish 5 加 5 后再试，即重新进入直到 型循环 do while 的循环体。当着正常退出 for 循环时，一定是控制变量 i 从初值 4，一步一步执 行到终值 1，每一步的鱼数均为整数，最后 i = 0，表示计算完毕， 且也达到了退出直到型循环的条件。(3) 输出计算结果信息信息与与物流管理系物
13、流管理系/* /* 程 序 名：5_3.c（五人合伙捕鱼） * /* 作 者：wuwh * /* 编制时间：2002年10月2日 * /* 主要功能：递推算法的实现 * /* #include / 预编译命令 void main() /主函数 int fish6=1,1,1,1,1,1; / 整型数组，记录每人醒来后看到的鱼数int i=0;dofish5=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
14、( i=1 ); / 当 i=1 继续做do循环/ 输出计算结果for (i=1; i1 时，A 的取值即 C 的值，而 C 的值即 E 的值，为了求得 E 的值，需要先求出 D 的值。D 值 fact( n-1 ) 乘以 n 即为 E 的值。信息信息与与物流管理系物流管理系与结点可能有多个相关联的点，这时可描述为下图A 结点的值最终为 D 的值，但为了求 D 需先求 B 和 C。从图上看, 先求左边的点才能求最右边的点的 值，我们约定最右边 D 点的值就是 A 结点的值。信息信息与与物流管理系物流管理系下面我们以3！为例来画与或结点图，目的是体 会递归的含义。C = 1 D = 2*C = 2 B = D = 2 E = 3*B = 3*2 = 6 A = E = 6信息信息与与物流管理系物流管理系下面画出了调用和返回的递归示意图信息信息与与物流管理系物流管理系从图可以想象： 欲求 fact( 3 )，先要求 fact( 2 )；要求 fact( 2
