C语言内涵教程 教学课件 ppt 作者 周二强 著 第7章函数(下)

C语言内涵教程周二强zeq126@126.com中国铁道出版社ISBN9787113163815第7章函数 7.5递归 7.6库函数简介 7.6.1getchar函数、getch函数和getche函数 7.6.2rand函数、srand函数和time函数 7.6.3字符串处理函数 7.7综合实例7.5.1递归算法与递归函数 以求523的阶乘为例。如何求出523的阶乘？ 方法一：从1乘以2乘以3……一直乘到523。 方法二：第一步，先求出522的阶乘；第二步，再用523乘以522的阶乘从而得到523的阶乘。 第二步计算乘法在理论上没有难度，关键在于第一步如何求出522的阶乘？ 遇到的问题与原问题相比： 性质相同：求一个数的阶乘 规模变小：523变成了522 性质相同意味着？ 规模变小意味着？523！可转化为523×522！。求523的阶乘的问题转化为求522的阶乘的问题，求522的阶乘相对求523的阶乘而言会容易一点。求522的阶乘又可转化为求521的阶乘，……，最终，问题转化为求1的阶乘，而1的阶乘是1，求出了1的阶乘就可以得到2的阶乘，……，最后可得到原问题的解，即523的阶乘。例7-22用递归算法求阶乘。 递归算法在C语言中用递归函数模拟。 设函数fac可以求出整数n的阶乘，该函数的首部为unsignedintfac(intn)。在求整数n的阶乘时，是否一定要转化为规模较小的子问题？ 如果整数n的规模已经小到可以直接得到结果了（0或1），则直接返回结果；否则，就要转化为规模较小的子问题，本例中需要转化为n*(n-1)!即返回n*(n-1)!的结果。函数可定义为：例7-22用递归算法求阶乘。 fac函数在定义中调用了自身，因此，它在执行过程中肯定会调用自身，函数调用fac(n-1)将如何执行？fac(3)的执行过程例7-23把用户输入的一行字符逆序输出,如输入abc，则程序输出cba。 以用户输入abc为例，可以分三步实现逆序输出： 第一步，得到用户输入abc中的第一个字符a； 第二步，把剩余的字符bc逆序输出； 第三步，把字符a输出，即输出了cba。 这个算法中的第二步需要逆序输出剩余的字符，此问题与原问题相同，但规模变小了，因此，此算法为递归算法。 规模缩小到何种程度，问题才能解决呢？如何把剩余的字符逆序输出呢？既然子问题的性质与原问题的相同，显然可以采用同样的步骤，把问题的规模再次缩小。实现逆序的reverse函数 reverse函数可描述如下：用户输入abc\n，则变量c的值为a缓冲区中有数据bc\n故c的值为b缓冲区中有数据c\n故c的值为c缓冲区中有数据\n故c的值\n例7-24　猴子吃桃。有若干桃子，一只猴子第一天吃了一半多一个，第二天吃了剩下的一半多一个，每天如此，第十天吃时只有一个桃子了，一共有多少个桃子？ f(n)表示第n天原有的桃子。第十天吃时只有一个桃子了，则f(10)=1。问题是： 求f(1)是多少。如果知道f(2)就好了， 因为有f(1)=(f(2)+1)*2（由等式f(2)=f(1)-(f(1)/2+1)可得），这样求f(1)就变成了求f(2)。猴子吃桃的规律相同， 因此函数f(n)可定义如下：例7-24　猴子吃桃。例7-25输入一个自然数，若为偶数，则把它除以2；若为奇数，则把它乘以3再加1，经过如此有限次处理，总可以得到自然数1。编程模拟该过程。 如输入23时输出 23703510653160804020105168421用了16步! 设函数f(n)可以完成这个操作，则该函数的定义如下。递归函数中全局变量的使用例7-26编写一个递归函数isPalin判断字符数组中的字符串是否为回文。 如果s[left]与s[right]相等，则s中的字符串是否为回文 与s中从left+1到right-1的子段是否为回文等价，否则该字符串不为回文。当子段只有一个字符，或者没有字符时，即left>=right时，认为此子段为回文。例7-27楼梯有n阶台阶，上楼时一步可以上1阶，也可以上2阶，编程计算n阶楼梯共有多少种不同的走法 设n阶台阶的走法为f(n)，当楼梯只有1阶时，显然只有一种走法，f(1)=1。只有2阶时， 有两种走法，一步一阶地或一步两阶地走上楼梯,f(2)=2。 楼梯多于2阶的时，有几种走法呢？例7-27n阶楼梯有几种不同的走法？ 先考虑上楼梯时第一步如何走？ 只有两种情况：上1阶和上2阶 n阶楼梯的不同走法等于 这两种情况下所有不同走法的总和。 第一步上1阶时走法有多少种？ 还有n－1阶楼梯需要上。 剩余的楼梯有多少种不同走法？ 性质相同，规模变小！ n阶台阶的走法为f(n)，剩余n－1阶的楼梯的走法当然有f(n-1)种！ 第一步上2阶时走法有多少种呢？例7-27n阶楼梯有几种不同的走法？ 设n阶台阶的走法为f(n)，则f(n)的定义为： 递归函数f(n)可实现为：intupstairs(intn){if(n==1||n==2)returnn;returnupstairs(n-1)+upstairs(n-2);}分析upstairs(4)的运行情况upstairs(4)分析upstairs(4)的运行情况upstairs(3)例7-28 汉诺塔问题。 古代有一个梵塔，塔内有3个标示为A、B、C的座，A座上有5个大小不等的盘子，大的在下面，小的在上面。现把5个盘子从A座移动到C座，每次只允许移动一个盘子，在移动过程中可以利用B座，但是3个座上要始终保持大盘在下面，小盘在上面。 设A座上有n个盘子。 如果n为1时，即A座上只有一个盘子，则把它直接移到C座上 否则，用下面三步完成任务： 第一步，把A座上的n-1个盘子先利用C座移动到B座上。 第二步，把A座上仅有的第n个盘子移动到C座上。 第三步，把B座上的n-1个盘子利用A座移动到C座上。不能用hanoi(n-1,'A','C','B');只能用？ 设src座上有n个盘子。 当n为1时，即src座上只有一个盘子，则把它直接移到dst座上 否则，用下面三步完成任务： 第一步，把src座上的n-1个盘子先利用dst座移动到tmp座上。 第二步，把src座上仅有的第n个盘子移动到dst座上。 第三步，把tmp座上的n-1个盘子利用src座移动到dst座上。7.6库函数简介 函数库是C语言必不可少的补充，常用的有输入输出库（stdio.h）、数学函数库（math.h）、标准库（stdlib.h）、日期时间库（time.h）、字符函数库（ctype.h）和字符串处理库（string.h）等。 使用库函数，既能提高编程效率，又能提高程序的可靠性。函数库的详细介绍可参考有关资料。7.6.1getchar函数、getch函数和getche函数 getchar函数在stdio.h中声明，getch函数和getche函数在conio.h（控制台输入输出）中声明。这三个函数的功能相似，可简单地理解为它们返回用户输入字符的ASCII码，不同之处在于： getchar函数使用输入缓冲区，而getch函数和getche函数不使用。使用输入缓冲区时，输入函数只有在缓冲区为空时才让用户输入数据；用户输入数据时，所有的输入会保存在缓冲区中，仅当用户按下回车键确认输入完成后，输入函数才能从输入缓冲区中获得用户的输入并返回。getch函数和getche函数只要执行就会暂停程序的执行让用户输入字符，当用户按下一个键时，它们会立即获得用户的输入并返回。getche函数会在输出设备上回显用户输入的字符，而getch函数不回显。例7-29getch函数、getche函数和getchar函数的区别例7-30　回车键的编码 键盘上的回车键相当于两个字符，把当前位置移到本行开头的回车符('\r')和新起一行并把当前位置移到新行开头的换行符('\n')。 基于Windows操作系统的C语言编译器通常把回车键编码为换行符（'\n'）。不使用输入缓冲区的getch函数在用户输入回车键时会返回什么字符呢？7.6.2rand函数、srand函数和time函数 rand函数和srand函数在stdlib.h中声明。rand函数的功能是返回一个0到RANDMAX之间的随机数。RANDMAX为stdlib.h中定义的符号常量，VC6.0中它的值为32767。 VC6.0中rand函数所用的算法与例7-17的相同。 存在的问题是？rand的问题？srand函数 随机序列与seed变量的初值相关，故称seed变量为“种子”。相同的种子自然产生重复的随机序列。 srand函数的头部为voidsrand(unsignedintseed)。调用srand函数可以改变rand函数的种子，从而使rand函数可以产生不同的随机序列。只用调用一次即可！！问题解决了吗？time函数 time函数在time.h中声明，它返回从公元1970年1月1日0时0分0秒起到现在（计算机当前的系统时间）所经过的秒数。它常用的调用形式为time(NULL)，其中NULL为stdio.h中定义的一个值为0的符号常量。 程序总是在不同的时刻运行，因此，time(NULL)的返回值在每次程序运行时都不相同，把它作为rand函数的种子，就可以保证rand函数在每次程序运行时产生不同的随机序列。srand(time(NULL));例7-31不重复的随机序列7.6.3字符串处理函数 字符串处理函数用来处理字符串，常用的有strcat函数、strcpy函数、strncpy函数、strcmp函数和strlen函数等，它们都在string.h中声明。 字符串常存储于字符数组中，因此下面在分析字符串处理函数时用字符数组代替字符串，这里的字符数组实际上为存储在其中的字符串。 如：strcat(字符数组1，字符数组2)strcat函数（stringcatenate字符串连接） 一般形式为：strcat(字符数组1，字符数组2) strcat函数的作用是把字符数组2中的字符串2复制并连接到字符数组1中字符串1的后面，最终，字符数组1中的字符串由字符串1和字符串2连接而成，而字符数组2中的字符串不变。注意： 字符数组1必须能容纳新的字符串，否则使用该函数的程序将出现问题。例7-32strcat函数的使用strcpy函数（stringcopy字符串拷贝） 函数的一般形式为：strcpy(字符数组1，字符数组2) strcpy函数的功能是将字符数组2中的字符串2拷贝到字符数组1中，最终，两个数组中的字符串均为字符串2。 此函数同样要求字符数组1能容纳新的字符串。如有charstr1[11]={"IloveC!"},str2[]={"Hehe"};，当执行完strcpy(str1,str2)后，字符数组str1的变化如图7-9所示。注意： 不能用字符串常量给字符数组赋值，也不能用一个字符数组给另一个字符数组赋值，如语句str1="comeon!";或str1=str2;都是错误的。 字符串的赋值操作需用strcpy函数，正确的作法为：strcpy(str1,"comeon!");或strcpy(str1,str2);。 可以用字符串常量初始化字符数组， 如语句charstr1[]="comeon!";strncpy函数 一般形式为：strncpy(字符数组1,字符数组2,n) strncpy函数的功能是把字符数组2中所含字符串2的前n个字符复制到字符数组1的起始部分。 特别注意：只复制n个字符，但字符串2的长度小于n时，会以'\0'字符补足n个字符。此函数要求字符数组1的长度至少为n。 如有charstr1[11]={"IloveC!"},str2[]="Hehe";，则执行完语句strncpy(str1,str2,2);后， 字符数组str1中的字符串为"HeloveC!"。strncpy函数 如果执行了语句strncpy(str1,str2,7)；则字符数组str2中的字符串为"Hehe"，其状态如图所示。strcmp函数(stringcompare字符串比较) 一般形式为strcmp(字符数组1,字符数组2) strcmp(stringcompare字符串比较)函数的功能为比较两个字符数组中所含字符串的大小，如果字符数组1中的字符串大于字符数组2中的字符串则返回一个正整数；如果等于，则返回0；如果小于，则返回一个负整数。该函数常用的形式为： if(strcmp(str1,str2)>0)　　　printf("%s大于%s\n",str1,str2);strlen函数（stringlength字符串长度） 一般形式为：strlen(字符数组) strlen函数的功能是求字符数组中所含字符串的长度，它返回有效长度而非实际长度，即不计算末尾字符'\0'。如strlen("China")的值为 5，而sizeof("China")的值 为6。7.7综合实例例7-33确定公元y年m月d日是星期几。 已知公元1年1月1日是星期一，则再过7天、14天、……、7*n天后仍是星期一，因此只要求出公元1年1月1日到公元y年m月d日有多少天，设有x天，再计算x%7的值， 若结果是0，则公元y年m月d日为星期天，否则结果为几，公元y年m月d日就是星期几。 如公元1年1月1日到公元1年1月20日有20天，因为20%7的值为6，所以1年1月20日为星期6。例7-33确定公元y年m月d日是星期几。 第一步，请用户输入年（year）,月（month）,日（day），并判断year年month月day日的合法性； 第二步，求出从1年1月1日到（year-1）年12月31日有多少天； 第三步，求出从year年1月1日到year年month月day日有多少天； 第四步，把第二步和第三步求出的天数累加起来，累加和与7进行模运算，并根据运算结果判断出year年month月day日为星期几。例7-33确定公元y年m月d日是星期几。 设首部为intcheck(inty，intm，intd)的check函数可以检测出日期数据的合法性，如果y年m月d日是合法的日期check函数返回1，否则返回0。 设首部为intdaysOfYears(intyear)的daysOfYears函数可以返回1年1月1日至year年12月31日有多少天。 设首部为intdaysOfThisYear(inty，intm，intd)的daysOfThisYear函数可以返回y年1月1日至y年m月d日有多少天。check函数 日期合法性的检查内容主要是月份值应在1到12之间，每月的天数应不超过该月的最大天数。在工程7_33中加入名为7_3302.c的源文件，其内容如下：daysOfYears函数 天数需从1年累加到year年，平年为365天，闰年为366天，但是考虑到最终的天数要与7进行模运算，余数才是关键，因此没有必要累加出实际天数，只需累加实际天数除以7所得的余数即可，也就是平年按（365%7）1天计算，闰年按2天计算。在工程7_33中加入名为7_3303.c的源文件，其内容如下：daysOfThisYear函数 计算天数时先把1月至（m-1）月的天数累加起来，再加上d的值即可。在工程7_33中加入名为7_3304.c的源文件，其内容如下：523！可转化为523×522！。求523的阶乘的问题转化为求522的阶乘的问题，求522的阶乘相对求523的阶乘而言会容易一点。求522的阶乘又可转化为求521的阶乘，……，最终，问题转化为求1的阶乘，而1的阶乘是1，求出了1的阶乘就可以得到2的阶乘，……，最后可得到原问题的解，即523的阶乘。如何把剩余的字符逆序输出呢？既然子问题的性质与原问题的相同，显然可以采用同样的步骤，把问题的规模再次缩小。使用输入缓冲区时，输入函数只有在缓冲区为空时才让用户输入数据；用户输入数据时，所有的输入会保存在缓冲区中，仅当用户按下回车键确认输入完成后，输入函数才能从输入缓冲区中获得用户的输入并返回。getch函数和getche函数只要执行就会暂停程序的执行让用户输入字符，当用户按下一个键时，它们会立即获得用户的输入并返回。getche函数会在输出设备上回显用户输入的字符，而getch函数不回显。