北京大学程序设计实习课程

程序设计实习第四讲函数指针和高精度计算,主讲教师：田永鸿yhtian2008年3月3日,2,上机遇到的问题,程序风格请参见第一讲程序风格部分常见问题：1、多个语句写在1行（特别是for语句）2、没有遵循命名规范对特定问题的分析不清晰程序设计问题数组的分配可以选用VisualStudio.Net2003/2005或其他编译环境,3,内容提要,函数调用的内存变化示意图函数指针程序阅读练习程序设计练习作业,4,C+组件,C程序是由函数构成的。程序员编写新的函数并调用C语言的函数库中的有关函数以完成具有特定功能的程序。C+程序是由类构成的。程序员编写新的类并使用C+标准类库中的类来完成编程。C+标准类库中也提供丰富的函数（数学计算、字符串操作、字符操作、输入输出、错误检查等）供程序员使用。函数在C和C+程序中都是一个非常重要的内容。,5,数学函数库,例：计算并输出900.0的平方根，用如下语句：cout语句,6,数学函数库,在math.h中还有下列函数：ceil(x)向上取整floor(x)向下取整exp(x)log(x)底数为elog10(x)pow(x,y)x的y次方sqrt(x)sin(x)cos(x)tan(x)fabs(x)/求浮点数的绝对值fmod(x,y)/双精度数取模，即x/y的余数,7,库函数及头文件,C语言中的一些库函数/设定插入点/字符处理/浮点数处理/定义各种数据类型最值常量/定义数学函数/定义输入输出函数/定义杂项函数及内存分配函数/字符串处理/定义关于时间的函数,8,库函数及头文件,C语言中的一些库函数或/数据流输入输出/参数化输入输出/文件输入输出/定义错误码/宽字符处理及输入输出/宽字符分类每个头文件中包含一组函数，使用哪个头文件中的函数就必须在程序中用#include语句包含哪个头文件。,9,函数的定义,函数的定义语句如下：返回值类型函数名（参数1类型参数名1,参数2类型参数名2,）语句1；/语句可能与参数有关语句2；/语句可能与参数有关return返回值；/如果返回值类型为void，则不用返/回语句,10,函数定义的例子,下面是一个函数定义的例子：intadd(intx,inty)returnx+y;,11,函数说明和函数体,intmultiple(intx,inty);/函数说明voidmain()inta=0,b=0;scanf(%d%d,12,函数的调用,intadd(intx,inty)returnx+y;intminus(intx,inty)returnx-y;,13,函数的调用,voidmain()intn1,n2;scanf(“%d%d”,14,函数调用的过程,intmax(intx,inty)if(x=y)returnx;elsereturny;voidmain()intx=0,y=0,z=0;x=20;y=45;intz=max(x,y);,15,函数调用的过程,16,函数调用的过程,17,函数调用的过程,18,函数调用的过程,19,函数调用的过程,20,函数调用的过程,21,参数传递：传值和传地址,A程序可以向B程序传递某些数值，也可以向B程序传递内存地址。,22,参数传递：传值,intmax(intx,inty)if(x=y)returnx;elsereturny;voidmain()intx=0,y=0,z=0;x=20;y=45;intz=max(x,y);,23,参数传递：传地址（指针方式）,intswap(int*x,int*y)inttmp=0;tmp=*x;*x=*y;*y=tmp;,24,参数传递：传地址（引用方式）,voidmain()inta=0,b=0;a=20;b=45;if(ab)return0;return(*term)(a)+sum(a+1,b,(*term);intterm(inta)returna;voidmain()coutsum(69,90,term)endl;ints=0;for(inti=69;i=90;i+)s+=i;coutsb)return0;return(*term)(a)+sum(a+1,b,(*term);intcube_term(inta)returna*a*a;voidmain()coutsum(1,3,cube_term)endl;cout1*1*1+2*2*2+3*3*3b)return0;return(*term)(a)+sum(a+1,b,(*term);doublepi_term(inta)return(1.0/(4*(a-1)+1)*(1.0/(4*(a-1)+3);voidmain()coutsum(2,5,pi_term)endl;cout1.0/(5*7)+1.0/(9*11)+1.0/(13*15)+1.0/(17*19)b)return0;return(*term)(a)+sum(a+1,b,(*term);intterm1(inta)returna;intterm2(inta)returna*a*a;doubleterm3(inta)return(1.0/(4*(a-1)+1)*(1.0/(4*(a-1)+3);voidmain()coutsum(1,3,term1)endl;coutsum(1,3,term2)endl;coutsum(1,3,term3)endl;,41,C语言库函数中的几个带函数参数的函数,#includeqsort/快速排序Bsearch/数组的二分法搜索#include_lfind/线性搜索_lsearch/线性搜索_lfind与_lsearch不同点在于，当找不到关键数据时_lfind仅会返回NULL，_lsearch会主动把该笔数据加入数组尾端。,42,qsort,voidqsort(void*base,size_tnum,size_twidth,int(_cdecl*compare)(constvoid*elem1,constvoid*elem2);,_cdecl和_stdcall都是函数调用规范(还有一个_fastcall),规定了参数出入栈的顺序和方法_cdecl是C/C+和MFC程序默认使用的调用约定，也可以在函数声明时加上_cdecl关键字来手工指定。采用_cdecl约定时，函数参数按照从右到左的顺序入栈，并且由调用函数者把参数弹出栈以清理堆栈。因此，实现可变参数的函数只能使用该调用约定。由于每一个使用_cdecl约定的函数都要包含清理堆栈的代码，所以产生的可执行文件大小会比较大。_cdecl可以写成_cdecl。,43,qsort,Theqsortfunctionimplementsaquick-sortalgorithmtosortanarrayofnumelements,eachofwidthbytes.Theargumentbaseisapointertothebaseofthearraytobesorted.qsortoverwritesthisarraywiththesortedelements.Theargumentcompareisapointertoauser-suppliedroutinethatcomparestwoarrayelementsandreturnsavaluespecifyingtheirrelationship.qsortcallsthecompareroutineoneormoretimesduringthesort,passingpointerstotwoarrayelementsoneachcall:,44,qsort,compare(void*)elem1,(void*)elem2);Theroutinemustcomparetheelements,thenreturnoneofthefollowingvalues:ReturnValueDescription0elem1greaterthanelem2,45,习题1928题,鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！熊字”。鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”,46,习题1928题,我们假定多多在每个单位时间内，可以做下列四件事情中的一件：从路边跳到最靠近路边（即第一行）的某棵花生植株；从一棵植株跳到前后左右与之相邻的另一棵植株；采摘一棵植株下的花生；从最靠近路边（即第一行）的某棵花生植株跳回路边。现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。,47,例如在图2中的花生田里，只有位于(2,5),(3,7),(4,2),(5,4)的植株下长有花生，个数分别为13,7,15,9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。,48,【输入】输入第一行包括三个整数，M,N和K，用空格隔开；表示花生田的大小为M*N（1=M,N=20），多多采花生的限定时间为K（0=K=1000）个单位时间。接下来的M行，每行包括N个非负整数，也用空格隔开；第i+1行的第j个整数Pij（0nPeanuts;,53,解法2,主要流程1、读入输入记录的个数2、对每个输入记录，分别读入各参数，并初始化Field数组3、用qsort将Field数组排序4、开始采摘初始化耗时FOR循环：从大到小偏离所有的Field数组,直至超时或超Field数组中记录个数计算所有摘取的花生数计算总耗时，加上采摘并走到下一个节点的时间5、输出源程序,54,程序设计过程,提出问题建立数学模型设计算法程序实现,55,提出问题,明确程序的已知条件、原始数据、输入、处理的数据类型、输出的形式和精度,56,建立数学模型,将原始问题简化、抽象、转换成适合计算机处理的数据结构、公式选择合适的数据类型以及存储调用方式（需要注意的：数据的类型、数据的精度、数据的生命周期）建立数据之间的关系即公式,57,设计算法,使用计算机可以实现的方法描述数据和数据之间的关系选择合适的程序流，使用流程图描述程序流,58,程序实现,编写程序、调试运行、测试验证、保存编译等良好程序风格输入输出声明数据，申请存储空间实现程序流,59,高精度计算,高精度计算：C/C+中int类型表示范围：-231231-1unsigned类型表示范围：0232-1因此均不超过10位整数即使用很大数字范围的double有时也不能满足要求大整数的表示和存放用数组来存放和表示，一个数组元素存放大整数的一位改进：每个数组元素存放十进制大整数的4位例题：编程实现两个N位内高精度正整数的加法。（N已知，1001000内）,60,存储两个输入的N位数字#defineMAXLEN500intdigital1MAXLENintdigital2MAXLEN从低位往高位依次运算使用一个变量记录高位数值存储输出的N+1位数字,61,IntdigitMAXLEN，N，i,输入整数N,i+;ifi=10(或0)需要考虑从上位增或减1，本位减或加10输出时注意跳过高位时多余的0数组需要稍微大一些，避免运算时溢出,63,例题,高精度计算：编程精确计算2的N次方。（N是介于100和1000之间的整数）,64,解决第一步提出问题,明确程序的已知条件、原始数据、输入、处理的数据类型、输出的形式和精度Input:NasIntegerOutput:2的N次方=?,65,解决第一步提出问题,可以计算输出结果的位数输出为一个0.31N位整数,66,解决第二步建立数学模型,将原始问题简化、抽象、转换成适合计算机处理的数