(921页PPT幻灯片)c++课件

,程序设计实习课程(C+ProgrammingPractice)C+程序设计第一讲课程简介与简单程序设计,2,为什么要加强程序设计能力？,Highthoughtsmusthavehighlanguage.Aristophane,(Greek,Comicdramatist)450BC-388BC,3,为什么要加强程序设计能力？,Programming之于计算机专业学生Gun之于士兵,为什么要加强程序设计能力？,北大计算机专业学生未来可能人生规划国内就业机会,=不好,=好,出国深造的积极性,出国留学,在国内读博士,=高,=差,个人IT能力,开IT公司/核心人才,在家吃父母,=强,=差,个人研究能力=强,顺利毕业高级研究员,拿不到学位,=差,结论：必须具有较高的程序设计能力！,4,典型案例,RickRashid博士微软公司主管研究的高级副总裁美国国家工程院院士、CMU教授、Mach操作系统项目的负责人、参与开发最早的计算机网络游戏之一AltoTrek据称，每年亲自编写近1.5万行代码！经典语录编程：艺术与科学,RickRashid,5,内容提要,6,课程相关信息C语言知识巩固和补充代码风格摸底测验,课程相关信息,7,课程内容授课方式成绩评定教材进度安排课程网页,课程内容,8,1.掌握VC+编程环境能够使用该环境进行基于控制台输入输出及文件输入输出的C及C+程序的源代码编辑、编译连接、调试和运行2.巩固和增强程序设计和代码实现能力高精度计算，日期的处理，字符串的处理，链表的概念、实现和应用，枚举和递归的求解方法。3.学习用C+语言编程基本概念（类、对象、数据抽象、重载、继承、虚函数、多态等）及其语法实现。C+程序基本构成、输入输出流及文件处理、模板、字符串处理、文件处理及标准模板库等。,授课方式,9,课上讲授、练习及测验复习、自学和书面作业上机实习并完成上机作业期中及期末考试,成绩评定,10,期中考试：15%上机考试期末考试：50%有B卷，考试内容为作业作业：25%平时成绩与B卷成绩加权课堂表现：10%鼓励上课主动发言随机抽取发言人将在课程网站上公布发言名单,教材,11,自编讲义,程序设计部分：程序设计导引及在线实践李文新等编著清华大学出版社2007C+部分：C+大学教程（第二版）HarveyM.Deitel,PaulJamesDeitel著邱仲潘等译冯平审校电子工业出版社2004参考教材C+大学教程（第五版）C+Primer中文版（第4版）StanleyB.Lippman,JoseeLajoie,BarbaraE.Moo著，李师贤、蒋爱军、梅晓勇、林瑛等译,进度安排（暂定）,12,2月18日第一周2月25日第二周3月03日第三周3月10日第四周3月17日第五周3月24日第六周3月31日第七周4月07日第八周,课程简介与简单程序设计日期处理与高精度计算字符串处理指针和链表枚举和搜索递归和动态规划递归和动态规划类和对象,进度安排（暂定）,13,4月14日第九周4月21日第十周4月28日第十一周5月05日第十二周5月12日第十三周5月19日第十四周5月26日第十五周6月02日第十六周,类和对象继承和多态String类与字符串流处理文件处理标准模板库（一）标准模板库（二）标准模板库（三）标准模板库（四）,单周的课程内容根据情况由任课教师安排,课程网页,14,北京大学信息科学技术学院网络与信息系统研究所人工智能研究室北京大学数字媒体研究所,内容提要,15,课程相关信息C语言知识巩固和补充代码风格摸底测验,C语言知识巩固和补充,16,位运算函数指针指针和动态内存分配命令行参数C语言标准库函数,位运算,17,有时我们需要对某个整数类型变量中的某一位,（bit）进行操作，比如，判断某一位是否为1，或只改变其中某一位，而保持其他位都不变。C/C+语言提供了“位运算”的操作，能够做到类似的操作。C/C+语言提供了六种位运算符来进行位运算操作：,按位异或,22,按位异或运算符“”是双目运算符。功能：将参与运算的两操作数各对应的二进制位进行异或操作，即只有对应的两个二进位不相同时，结果的对应二进制位才是1，否则为0。例如：表达式“2118”的值是7(即二进制数111)。异或运算的特点如果ab=c，那么就有cb=a以及ca=b。此规律可以用来进行最简单的加密和解密。,按位非,23,按位非运算符“”是单目运算符。其功能是将操作数中的二进制位0变成1，1变成0。,例如，表达式“21”的值是无符号整型数0 xffffffea，而下面的语句：printf(%d,%u,%x,21,21,21);输出结果就是:-22,4294967274,ffffffea,左移运算符,24,左移运算符“”是双目运算符。其功能是将左操作数的各二进位全部左移若干位后得到的值，右操作数指明了要左移的位数。左移时，高位丢弃，左边低位补0。左移运算符不会改变左操作数的值。,左移运算符,25,例如，常数9有32位，其二进制表示是：00000000000000000000000000001001因此，表达式“94”的值，就是将上面的二进制数左移4位，得：00000000000000000000000010010000即为十进制的144。实际上，左移1位，就等于是乘以2，左移n位，就等于是乘以2n。而左移操作比乘法操作快得多。特别注意：有符号数的左移溢出情况。,#includemain(),intn1=15;shortn2=15;unsignedshortn3=15;unsignedcharc=15;n1=15;n2=15;n3=15;c=6;printf(n1=%x,n2=%d,n3=%d,c=%x,c4=%d,n1,n2,n3,c,c4);上面程序的输出结果是:n1=78000,n2=-32768,n3=32768,c=c0,c”是双目运算符。其计算结果是把“”的左操作数的各二进位全部右移若干位后得到的值，要移动的位数就是“”的右操作数。移出最右边的位就被丢弃。对于有符号数，如long,int,short,char类型变量，在右移时，符号位（即最高位）将一起移动，并且大多数C/C+编译器规定，如果原符号位为1，则右移时右边高位就补充1，原符号位为0，则右移时高位就补充0。,右移运算符,28,对于无符号数，如unsignedlong,unsignedint,unsignedshort,unsignedchar类型的变量，则右移时，高位总是补0。右移运算符不会改变左操作数的值。实际上，右移n位，就相当于左操作数除以2n，并且将结果往小里取整。,#includemain(),intn1=15;shortn2=-15;unsignedshortn3=0 xffe0;unsignedcharc=15;n1=n12;n2=3;n3=4;c=3;printf(n1=%x,n2=%d,n3=%x,c=%x,n1,n2,n3,c);上面的程序输出结果是：n1=3,n2=-2,n3=ffe,c=1,思考题,30,有两个int型的变量a和n(0=nn,函数指针,31,程序运行期间，每个函数都会占用一段连续的内存空间。函数名就是该函数所占内存区域的起始地址(也称“入口地址”)。将函数的入口地址赋给一个指针变量，使该指针变量指向该函数。然后通过指针变量就可以调用这个函数。这种指向函数的指针变量称为“函数指针”。,函数指针,32,函数指针定义的一般形式为：类型名(*指针变量名)(参数类型1,参数类型2,);“类型名”表示被指函数的返回值的类型。“(参数类型1,参数类型2,)”中则依次列出了被指函数的所有参数的类型。例如：int(*pf)(int,char);表示pf是一个函数指针，它所指向的函数，返回值类型应是int，该函数应有两个参数，第一个是int类型，第二个是char类型。,函数指针,33,可以用一个原型匹配的函数的名字给一个函数指针赋值。要通过函数指针调用它所指向的函数，写法为：函数指针名(实参表);下面的程序说明了函数指针的用法,#includevoidPrintMin(inta,intb),if(ab)printf(%d,a);elseprintf(%d,b);intmain()void(*pf)(int,int);intx=4,y=5;pf=PrintMin;pf(x,y);return0;上面的程序输出结果是：4,函数指针应用：快速排序库函数qsort,35,voidqsort(void*base,intnelem,unsignedintwidth,int(*pfCompare)(constvoid*,constvoid*);base是待排序数组的起始地址，nelem是待排序数组的元素个数，width是待排序数组的每个元素的大小（以字节为单位），最后一个参数pfCompare是一个函数指针，它指向一个“比较函数”。,快速排序库函数qsort,36,排序就是一个不断比较并交换位置的过程。qsort如何在连元素的类型是什么都不知道的情况下，比较两个元素并判断哪个应该在前呢？答案是，qsort函数在执行期间，会通过pfCompare指针调用一个“比较函数”，用以判断两个元素哪个更应该排在前面。这个“比较函数”不是C/C+的库函数，而是由使用qsort的程序员编写的。在调用qsort时,将“比较函数”的名字作为实参传递给pfCompare。程序员当然清楚该按什么规则决定哪个元素应该在前，哪个元素应该在后，这个规则就体现在“比较函数”中。,快速排序库函数qsort,37,qsort函数的用法规定，“比较函数”的原型应是：int函数名(constvoid*elem1,constvoid*elem2);该函数的两个参数，elem1和elem2，指向待比较的两个元素。也就是说，*elem1和*elem2就是待比较的两个元素。该函数必须具有以下行为：1)如果*elem1应该排在*elem2前面，则函数返回值是负整数（任何负整数都行）。2)如果*elem1和*elem2哪个排在前面都行，那么函数返回03)如果*elem1应该排在*elem2后面，则函数返回值是正整数（任何正整数都行）,下面的程序，功能是调用qsort库函数，将一个unsignedint数组按照个位数从小到大进行排序。比如8，23，15三个数，按个位数从小到大排序，就应该是23，15，8#include#includeintMyCompare(constvoid*elem1,constvoid*elem2)unsignedint*p1,*p2;p1=(unsignedint*)elem1;p2=(unsignedint*)elem2;return(*p1%10)-(*p2%10);,38,快速排序库函数qsort的实现,#defineNUM5intmain(),unsignedintanNUM=8,123,11,10,4;qsort(an,NUM,sizeof(unsignedint),MyCompare);for(inti=0;iNUM;i+)printf(%d,ani);return0;上面程序的输出结果是：101112348,思考题,40,如果要将an数组从大到小排序，那么MyCompare函数该如何编写？,动态内存分配,41,在C+中，通过“new”运算符来实现动态内存分配。new运算符的第一种用法如下：P=newT;T是任意类型名，P是类型为T*的指针。这样的语句，会动态分配出一片大小为sizeof(T)字节的内存空间，并且将该内存空间的起始地址赋值给P。示例int*pn;pn=newint;/(1)*pn=5;语句(1)即动态分配了一片4个字节大小的内存空间，而pn会指向这片空间，通过pn,可以读写该内存空间。,动态内存分配,42,new运算符还有第二种用法，可以用来动态分配一个任意大小的数组：P=newTN;T是任意类型名P是类型为T*的指针N代表“元素个数”，它可以是任何值为正整数的表达式，表达式里可以包含变量、函数调用。这样的语句动态分配出Nsizeof(T)个字节的内存空间，这片空间的起始地址被赋值给P。示例int*pn;inti=5;pn=newinti*20;pn0=20;pn100=30;/编译没问题。运行时导致数组越界。,动态内存分配,43,如果要求分配的空间太大，操作系统找不到足够的内存来满足，那么动态内存分配就会失败。保险做法是在进行较大的动态内存分配时，要判断一下分配是否成功。判断的方法是：如果new表达式返回值是NULL，则分配失败，否则分配成功。例如：int*pn=newint200000;if(pn=NULL)printf(“内存分配失败”);elseprintf(“内存分配成功”);,动态内存分配,44,程序从操作系统动态分配所得的内存空间，使用完后应该释放，交还操作系统，以便操作系统将这片内存空间分配给其他程序使用。C+提供“delete”运算符，用以释放动态分配的内存空间。delete运算符的基本用法是：delete指针；该指针必须是指向动态分配的内存空间的，否则运行时很可能会出错。例如：int*p=newint;*p=5;deletep;,deletep;,/本句会导致程序异常,动态内存分配,45,如果是用new动态分配了一个数组，那么，释放该数组的时候，应以如下形式使用delete运算符：delete指针;示例int*p=newint20;p0=1;deletep;,动态内存分配,46,特别注意New和Delete配对使用：用new运算符动态分配的内存空间，一定要用delete运算符予以释放。否则即便程序运行结束，这部分内存空间仍然不会被操作系统收回，从而成为被白白浪费掉的内存垃圾。这种现象也称为“内存泄漏”。,命令行参数,47,将用户在DOS窗口输入可执行文件名的方式启动程序时，跟在可执行文件名后面的那些字符串，称为“命令行参数”。命令行参数可以有多个，以空格分隔。例如，在DOS窗口输入：copyfile1.txtfile2.txt“copy”,“file1.txt”,“file2.txt”就是命令行参数如何在程序中获得命令行参数呢？,命令行参数,48,intmain(intargc,char*argv)参数argc就代表启动程序时，命令行参数的个数。C/C+语言规定，可执行程序程序本身的文件名，也算一个命令行参数，因此，argc的值至少是1。参数argv是一个数组，其中的每个元素都是一个char*类型的指针，该指针指向一个字符串，这个字符串里就存放着命令行参数。argv0指向的字符串就是第一个命令行参数，即可执行程序的文件名argv1指向第二个命令行参数argv2指向第三个命令行参数。例子程序：,#includeintmain(intargc,char*argv),for(inti=0;i=4)printf(“%d”,nAge);for(i=0;i100;i+);,一些好的编程习惯,70,1）尽量不要用立即数，而用#define(C+中用const)定义成常量，以便以后修改#defineMAX_STUDENTS20structSStudentaStudentsMAX_STUDENTS;structSStudentaStudents20;/不好的范例#defineTOTAL_ELEMENTS100for(i=0;iTOTAL_ELEMENTS;i+),一些好的编程习惯,71,2）使用sizeof()宏，不直接使用变量所占字节数的数值好的范例intnAge;for(j=0;j100;j+)fwrite(fpFile,一些好的编程习惯,72,3）稍复杂的表达式中要积极使用括号，以免优先级理解上的混乱n=k+j;/不好n=(k+)+j;/好一点4）不很容易理解的表达式应分几行写：n=(k+)+j;应该写成：n=k+j;k+;,一些好的编程习惯,73,5）不提倡在表达式中使用?:形式，而用if.else语句替代不好的范例xp=2*k(n-m)?ck+1:dk-;好的范例if(2*k(n-m)xp=ck+1;elsexp=dk-;,一些好的编程习惯,74,6）嵌套的ifelse语句要多使用不好的范例if(Condition1()if(condition2()DoSomething();elseNoCondition2();好的范例if(Condition1()if(condition2()DoSomething();elseNoCondition2();,一些好的编程习惯,7）应避免ifelse的多重嵌套，而用并列的完成。if(Condition1()if(Condition2()if(Condition3(),Condition123();,else,NoCondition3();,elseNoCondition2();elseNoCondiction1();,if(!condition1)NoCondition1();elseif(!condition2)NoCondition2();elseif(!condition3)NoCondition3();elseCondition123();,75,一些好的编程习惯,76,8)遵循一些惯例的写法，如：循环的固定写法：for(i=0;im)a=u0+u1+u2+u3-5;b=u0*(u1-u2/u3+8);c=u0*u1/u2*u3;x=(a+b+2)*3-u(c+3)%4;y=(c*100-13)/a/(ub%3*5);if(x+y)%2=0)z=(a+b+c+x+y)/2;z=(a+b+cx-y)*2;coutx+y-z;return0;输入：2574输出：,课堂测验试题2：校门外的树,92,某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。任务：编程计算将这些树都移走后，马路上还有多少棵树。,校门外的树,93,【输入描述】输入的第一行有两个整数L（1=L=10000）和M（1=M=100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。【输出描述】输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。,校门外的树,94,【样例输入】5003150300100200470471【样例输出】298,程序设计实习课程(C+ProgrammingPractice)程序设计实习第三讲数制转换和日期处理主讲教师：田永鸿yhtian2008年2月25日,通知,2,课程网页改在：,关于课程作业作业提交的规定时间：为作业布置周的下下周末24:00前POJ作业+平时邮件作业POJ作业在平时邮件作业：程设08_第X讲作业_姓名_学号（如程设08_第4讲作业_张三_100）POJ帐号规定如果有计算概论课程的ID，可继续使用该ID，如果没有帐号，则使用学号注册自己的ID昵称一律改为CPP08XX+自己喜欢的名称（XX为小班号，详见分班情况）,关于助教和分班,3,上机及助教分班已在网页上公布；本班四个助教01班：黄贝宁(huangbn)学号：=74805502班：唐大闰(tangcatcat)学号：74805774818903班：潘晨光(cgp)学号：74819174828404班：栾俊义(xmaswillyou)学号：748288748713,内容提要,4,关于POJ评测系统程序阅读练习程序设计练习作业,关于POJ评测系统,5,对于每一个题目，评测系统收到源代码后，就用在提交框中指定的编译器进行编译和链接得到目标代码后，将其运行。在运行过程中，如果程序要求从标准输入读入数据，则评测系统自动将已经存放在服务器端的测试数据提供给待测程序，待程序产生输出后，评测系统将程序产生的输出，与服务器端的标准答案做比较，如果相同，则程序被Accepted，否则出错。,关于POJ评测系统,6,出错程序的错误产生序列如下：CompileError，此时程序无法运行，可查看错误说明，如果程序有多个编译错，则只显示第一引起编译错的代码行引发的错误，如果你的程序在本机编译没错，通常有几种情况：选用了不正确的编译器，在VC+编程环境中编程由环境自动生成了“stdafx.h”等等；RuntimeError，运行错，通常是数组、指针越界，或除零错；,关于POJ评测系统,7,TimeLimitExceeded，超时错，在每个问题的说明里都给出了时限，如果提交的程序在相应的时间内不结束，则评测系统自动将其终止，并返回超时错。引起超时错的原因主要有：死循环（尤其是判断输入结束有误），算法或代码效率不够好；OutputLimitExceeded，输出过多，如果程序输出比标准答案多一倍以上的内容，则评测系统返回此错误。引发这一错误的原因多半是死循环。,关于POJ评测系统,8,WrongAnswer，结果错，这是最为复杂的一种错误，引发该错误的原因有很多，从读入数据不正确，到算法程序不正确，到输出不正确，都有可能引发该错误；PresentationError，格式错，这是最为温和的一类错误，如果得到格式错，表明输入和程序的算法都没有错误，给出的答案是正确的，只是在输出时多余或少了空格空行等。有些时候不容易判格式错的问题也可能答案正确格式不正确，但得到结果错。,关于POJ评测系统,9,ProblemDisabled，题目有错，两种可能：该题已被删除，或者是在,讨论：你要在本课程上学到什么？,10,分析求解问题的方法架构程序的思路设计与调试程序的技巧,程序设计练习上节课的例2（作业）,11,1013称硬币问题描述赛利有12枚银币。其中有11枚真币和1枚假币。假币看起来和真币没有区别，但是重量不同。但赛利不知道假币比真币轻还是重。于是他向朋友借了一架天平。朋友希望赛利称三次就能找出假币并且确定假币是轻是重。例如:如果赛利用天平称两枚硬币，发现天平平衡，说明两枚都是真的。如果赛利用一枚真币与另一枚银币比较，发现它比真币轻或重，说明它是假币。经过精心安排每次的称量，赛利保证在称三次后确定假币。,1013题,12,输入输入有三行，每行表示一次称量的结果。赛利事先将银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示：天平左边放置的硬币天平右边放置的硬币平衡状态。其中平衡状态用up,down,或even表示,分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。输出输出哪一个标号的银币是假币;并说明它比真币轻还是重。,1013题,13,输入样例1ABCDEFGHevenABCIEFJKupABIJEFGHeven输出样例Kisthecounterfeitcoinanditislight.,1013题,14,问题分析此题并非要求你给出如何称量的方案，而是数据已经保证三组称量后答案唯一。不是那道传统的智商测验题。此题可以有多种解法，这里只介绍一种比较容易想到和理解的逐一枚举法。,1013题,15,总体构想逐一试探法对于每一枚硬币x逐个试探：x比真币轻的猜测是否整理？若成立则输出；x比真币重的猜测是否整理？若成立则输出isLight?Yes.输出，No.isHeavy?-Yes.输出,1013题,16,定义变量存储称量结果charleft37,right37,result37;数组下标3代表3次称量；数组下标7代表每次左右至多6枚硬币，多出一个字符位置是为了方便用字符串读取的函数。,1013题,17,逐一枚举硬币的代码for(charc=A;c=L;c+)if(isLight(c)coutcisthecounterfeitcoinanditislight.n;break;elseif(isHeavy(c)coutcisthecounterfeitcoinanditisheavy.n;break;,1013题,18,boolisLight(charx)/判断硬币x是否为轻的代码inti;for(i=0;i3;i+)/判断是否与三次称量结果矛盾switch(resulti0)caseu:if(!inRight(i,x)returnfalse;break;casee:if(inRight(i,x)|inLeft(i,x)returnfalse;break;cased:if(!inLeft(i,x)returnfalse;break;returntrue;,1013题,19,boolisHeavy(charx)/判断硬币x是否为重的代码inti;for(i=0;i3;i+)/判断是否与三次称量结果矛盾switch(resulti0)caseu:if(!inLeft(i,x)returnfalse;break;casee:if(inRight(i,x)|inLeft(i,x)returnfalse;break;cased:if(!inRight(i,x)returnfalse;break;returntrue;,1013题,20,boolinLeft(inti,charx)/判断硬币x是否在第i次称量左侧intj;for(j=0;jstrlen(lefti);j+)if(leftij=x)returntrue;returnfalse;boolinRight(inti,charx)/判断硬币x是否在第i次称量右侧intj;for(j=0;jstrlen(righti);j+)if(rightij=x)returntrue;returnfalse;,数值转换,21,数制转换（1）,根据数制表示中相邻位的基数关系，数制可以分为两类相邻位的基数为等比关系：如十进制相邻位的基数为不等比关系：如时间表示数制转换问题的一般处理方法数值存储：不是十进制时，一般用字符型数组来存放，数组中每个元素分别存储它的一个数字。十进制为中介：按位转换求和，得到十进制表示，再把十进制表示转换成所求的数制表示，结果也用字符型数组存储,数制A数值（字符数组）,数制B数值（字符数组）,十进制数值（整型）,22,数制转换（2）,23,数制B的bmbm-1b1十进制的dndn-1d1数制B的中第i位的基数为basei(1=i=m)(basei*bi)十进制的dndn-1d1数制B的bmbm-1b1数制B中相邻位的基数为等比关系：basei可表示为Ci(1)将dndn-1d1除以C，余数即为b1；(2)将dndn-1d1和C相除的结果再除以C，余数即为b2；直至计算出bm。数制B中相邻位的基数为不等比关系：(1)判断dndn-1d1在数制B中需要的位数m；(2)从高到低依次计算bm,bm-1,b1。,#include#includedoublemysqrt(doubleguess,doublex);boolgoodEnough(doubleguess,doublex);doubleimprove(doubleguess,doublex);voidmain()coutmysqrt(2.25,2.25)endl;doublemysqrt(doubleguess,doublex)if(goodEnough(guess,x)returnguess;returnmysqrt(improve(guess,x),x);boolgoodEnough(doubleguess,doublex)#definethreshold0.000001if(fabs(guess*guess-x)threshold)returntrue;returnfalse;doubleimprove(doubleguess,doublex)return(guess+x/guess)/2;,输出：,25,小结：如何阅读程序？,阅读程序不能象阅读小说程序阅读的一些好方法快速找到Main()和输入输出；确定程序架构，画出流程图，确定调用关系；找到关键语句段/函数，作为黑盒子单独阅读/调试。阅读代码的格言1.第一次分析一个程序时，main是一个好的起始点。2.层叠if-elseif-.-else序列可以看作是由互斥选择项组成的选择结构。3.有时，要想了解程序在某一方面的功能，运行它可能比阅读源代码更为恰当。4.在分析重要的程序时，最好首先识别出重要的组成部分。5.了解局部的命名约定，利用它们来猜测变量和函数的功能用途。6.推理地递归调用等同于一个回到函数开始处的循环。7.,26,程序阅读练习例1,#include#includedoublemysqrt(doubleguess,doublex);boolgoodEnough(doubleguess,doublex);doubleimprove(doubleguess,doublex);voidmain()coutmysqrt(2.25,2.25)endl;doublemysqrt(doubleguess,doublex)if(goodEnough(guess,x)returnguess;returnmysqrt(improve(guess,x),x);boolgoodEnough(doubleguess,doublex)#definethreshold0.000001if(fabs(guess*guess-x)threshold)returntrue;returnfalse;doubleimprove(doubleguess,doublex)return(guess+x/guess)/2;,输出：1.5,Mysqrt(guess,x),2.25,2.25,Main(),Mysqrt(y,x),Mysqrt(guess,x),goodEnough(guess,x)N,y=Improve(guess,x),guess,Y,121,程序设计练习例1,则输出0。,1331(确定进制)问题描述6*9=42对于十进制来说是错误的，但是对于13进制来说是正确的。即,6(13)*9(13)=42(13)，而42(13)=4*131+2*130=54(10)。你的任务是写一段程序读入三个整数p,q和r，然后确定一个进制B(2=B=16)使得p*q=r.如果B有很多选择,输出最小的一个。例如：p=11,q=11,r=121.则有对于禁止3：11(3)*11(3)=121(3)因为11(3)=1*31+1*30=4(10)和121(3)=1*32+2*31+1*30=16(10)。对于进制10,有11(10)*11(10)=121(10)。这种情况下，应该输出3。如果没有合适的进制，,程序设计练习例1,28,输入输入有T组测试样例。T在第一行给出。每一组测试样例占一行，包含三个整数p,q,r。p,q,r的所有位都是数字，并且1=p,q,r=1,000,000。输出对于每个测试样例输出一行。该行包含一个整数-即使得p*q=r成立的最小的B。如果没有合适的B，则输出0。,程序设计练习例1,29,输入样例369421111121222输出样例1330,程序设计练习例1,30,此题没难度，逐一试探法，注意一些实现的细节。选择一个进制B（2=B0),/确定月,if(daysinyear=365)days-=m1ithmonth;elsedays-=m2ithmonth;ithmonth+;,if(daysinyear=365)days+=m1ithmonth-1;elsedays+=m2ithmonth-1;printf(%d-%02d-%02d%sn,2000+ithyear,ithmonth,days,weekweekday);scanf(%d,/while/main,/确定天,程序设计练习例3,46,问题描述：一种细菌的繁殖速度是每天成倍增长。例如：第一天有10个，第二天就变成20个，第三天变成40个，第四天变成80个，。现在给出第一天的日期和细菌数目，要你写程序求出到某一天的时候，细菌的数目。,程序设计练习例3,47,输入第一行有一个整数n，表示测试数据的数目。其后n行每行有5个整数，整数之间用一个空格隔开。第一个数表示第一天的月份，第二个数表示第一天的日期，第三个数表示第一天细菌的数目，第四个数表示要求的那一天的月份，第五个数表示要求的那一天的日期。已知第一天和要求的一天在同一年并且该年不是闰年，要求的一天一定在第一天之后。数据保证要求的一天的细菌数目在长整数（long）范围内。输出对于每一组测试数据，输出一行，该行包含一个整数，为要求的一天的细菌数。,程序设计练习例3,48,样例输入2111122281032样例输出240,解题思路,49,求给定的两天之间间隔的天数m，第一天的细菌数乘以2的m次方就是题目的答案难点：每月的天数不很规则，程序处理过程中较为复杂用一个数组将每个月的天数存起来算法框架读入测试样例数n；做n次(1)读入两个日期及第一天的细菌数；(2)将两个日期转换为当前的第几天；(3)得到两个天数的差，即他们中间间隔的天数m；(4)用第一天的细菌数乘以2的m次方得到x；(5)输出x,#includevoidmain()intnDays12=31,28,31,30,31,30,31,31,30,31,30,31;intn;scanf(%d,程序设计练习课堂练习2,51,2210问题描述有一种特殊的日历法，它的一天和我们现在用的日历法的一天是一样长的。它每天有10个小时，每个小时有100分钟，每分钟有100秒。10天算一周，10周算一个月，10个月算一年。现在要你编写一个程序，将我们常用的日历法的日期转换成这种特殊的日历表示法。这种日历法的时、分、秒是从0开始计数的。日、月从1开始计数，年从0开始计数。秒数为整数。假设0:0:01.1.2000等同于特殊日历法的0:0:01.1.0。,程序设计练习课堂练习2,52,输入第一行是一个整数N，表示测试样例的数目。每个测试样例包含一行，格式为：“hour:minute:secondday.month.year”日期总是合法的，并且2000=y)returnx;elsereturny;voidmain()intx=0,y=0,z=0;x=20;y=45;intz=max(x,y);,参数传递：传地址（指针方式）,23/70,intswap(int*x,int*y)inttmp=0;tmp=*x;*x=*y;*y=tmp;,参数传递：传地址（引用方式）,24/70,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;,C语言库函数中的几个带函数参数的函数,41/70,#includeqsort/快速排序Bsearch/数组的二分法搜索#include_lfind/线性搜索_lsearch/线性搜索_lfind与_lsearch不同点在于，当找不到关键数据时_lfind仅会返回NULL，_lsearch会主动把该笔数据加入数组尾端。,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。,42/70,qsort,43/70,Theqsortfunctionimplementsaquick-sortalgorithmtosortanarrayofnumelements,eachofwidthbytes.Theargumentbaseisapointertothebaseofthearraytobesorted.qsortoverwritesthisarraywiththesortedelements.Theargumentcompareisapointertoauser-suppliedroutinethatcomparestwoarrayelementsandreturnsavaluespecifyingtheirrelationship.qsortcallsthecompareroutineoneormoretimesduringthesort,passingpointerstotwoarrayelementsoneachcall:,qsort,44/70,compare(void*)elem1,(void*)elem2);Theroutinemustcomparetheelements,thenreturnoneofthefollowingvalues:ReturnValueDescription0elem1greaterthanelem2,验的多多一眼就能少。为了训练多多的生最多的植株，去植株里花生最多的，你一定要在我限定的45,习题1928题,鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！熊字”。鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。有经看出，每棵花生植株下的花生有多算术，鲁宾逊先生说：“你先找出花采摘它的花生；然后再找出剩下的去采摘它的花生；依此类推，不过时间内回到路边。”,/70,习题1928题,46/70,我们假定多多在每个单位时间内，可以做下列四件事情中的一件：1.从路边跳到最靠近路边（即第一行）的某棵花生植株；2.从一棵