资源描述
5/12/20221 c c程序设计竞赛程序设计竞赛竞赛与考试的区别1PPT学习交流一、注重程序效率二、信息数字化1.数学模型提高程序效率2.算术技巧提高程序效率三、数据存储(机试的共同特点)1. 状态信息数字化2. 特征信息数字化文件操作3.优化数据结构提高程序效率2PPT学习交流1 . 数学知识提高程序效率【例1】杨辉三角形的应用求n次二项式各项的系数:已知二项式的展开式为: (a+b)n=Cn0an+ Cn1an-1b+Cn2an-2 b2+Cnnbn它们共有n+1个系数。若你编写程序用n!/(j!*(n-j)!)计算组合系数Cnj ,会怎样?3PPT学习交流5/12/20224coeff(int a ,int n)if(n=1) a1=1; a2=1; else coeff(a,n-1) an+1=1 for (i=n;i=2;i- -) ai=ai+ai-1; a1=1; 程序如下: main( )int a100,i,n; scanf(“%d”,&n ); for(i=1;i=n;i+) scanf(“%d”,&ai); coeff(a,n);for(i=1;i=n;i+) printf(“%d”,ai);返回4PPT学习交流5/12/20225【例2】最大公约数的应用 数组中有n个数据,要将它们顺序循环向后移k位,即前面的元素向后移k位,后面的元素则循环向前移k位,例:1、2、3、4、5循环移3位后为:3、4、5、1、2。考虑到n会很大,不允许用2*n以上个空间来完成此题。 若题目没有关于存储空间的限制,可以方便地开辟两个一维数组,一个存储原始数据,另一个存储移动后的数据。分析1: 5PPT学习交流5/12/20226程序1如下: main( )int a100,b100,i,n,k; scanf(“%d%d”,&n,&k ); for(i=0;in;i+) scanf(“%d”,&ai); for(i=0;in;i+) b(k+i)%n=ai; for(i=0;in;i+) printf(“%d”,bi);6PPT学习交流5/12/20227分析2:1)一组循环移动的情况:通过计算我们可以确定某个元素移动后的具体位置。 当n=5,k=3时,可计算出1 4 , 4 2 , 2 5 , 5 3 , 3 1 的位置,一组移动正好将全部数据按要求进行了移动。这样只需一个辅助变量就可完成整个移动过程。2)多组循环移动的情况:但若把问题就这样按一组移动去解决,会怎样?7PPT学习交流5/12/20228数学模型: 问题与最大公约数有关, 即循环移动的组数等于N与K的最大公约数。这就是利用数学知识建模的过程。“感知”是否正确可以通过数学方法证明(就象哥德巴赫猜想),或通过程序进行大量数据验证。1)编写函数,完成求n,k最大公约数m的功能2)进行m组循环移动。3)每组移动,和程序1一样,通过计算可以确定某个元素移动后的具体位置。在移动之前,用临时变量存储需要被覆盖的数据。 实现要点:8PPT学习交流5/12/20229程序2如下:main( )int a100,b,i,n,k,m; printf(“input the number of data”); scanf(“%d”,&n); printf(“input the distant of moving”); scanf(“%d”,&k ); for(i=0;in;i+) scanf(“%d”,&ai); m=ff(n,k); for(j=0;jm;j+) for(i=j;in;i=i+k) b=a(j+k)%n; a(j+k)%n=aj; aj = b; for(i=0;in;i+) printf(“%d”,ai);返回9PPT学习交流5/12/202210ff(int a,int b)t=1 for (i=2;i=a& i=b;i+) while (a % i=0 & b % i=0 ) t=t*i; a=a/i; b=b/i; return(t);10PPT学习交流5/12/202211【例3】 最小公倍数的应用编写程序完成下面给“余”猜数的游戏: 你心里先想好一个1100之间的整数x,将它分别除以3、5和7并得到三个余数。你把这三个余数告诉计算机,计算机能马上猜出你心中的这个数。游戏过程如下:please think of a number between 1 and 100your number divided by 3 has a remainder of? 1your number divided by 5 has a remainder of? 0your number divided by 7 has a remainder of? 5let me think a momentyour number was 4011PPT学习交流5/12/202212用程序模拟这个游戏过程的关键是:找出余数与求解数之间的关系,也就是建立问题的数学模型。分析:数学模型: 记a,b,c分别为所猜数据d除以3,5,7后的余数,则d=70*a+21*b+15*c。 则建立数学模d=70*a+21*b+15*c的过程如下:12PPT学习交流5/12/202213 a、b、c的系数必须满足:1)b、c的系数能被3整除,且a的系数被3整除余1;这样d除以3的余数与a相同。2)a、c的系数能被5整除,且b的系数被5整除余1;这样d除以5的余数与b相同。3)a、b的系数能被7整除,且c的系数被7整除余1;这样d除以7的余数与c相同。d=70*a+21*b+15*c13PPT学习交流5/12/202214 由上可见:c的系数是3和5的最公倍数且被7整除 余 1,正好是15;a的系数是7和5的最公倍数且被3整除余1,最小是70; b的系数是7和3的最公倍数且被5整除余1,正好是21。实现要点: 用以上数学模型求解的数d,可能比100大,这时只要减去3,5,7的最小公倍数就是问题的解了。游戏程序如下:14PPT学习交流5/12/202215main( )int a,b,c,d; printf( “please think of a number between 1 and 100.”); printf( “your number divded by 3 has a remainker of”); scanf( “%d”,& a); printf( “your number divded by 5 has a remainker of”); scanf( “%d”,& b); printf( “your number divded by 7 has a remainker of”); scanf( “%d”,&c); printf( “let me think a moment”); for (i=1 ,i105) d=d-105; printf( “your number was %d ”, d);返回15PPT学习交流5/12/2022162. 算术运算的妙用1) 减化或避免条件判断【例1】一次考试,共考了五门课。统计五十个学生中至少有三门课成绩高于90分的人数。实现要点:1)对每个同学,先计算其成绩高于90分的课程数目,若超过3,则累加满足条件的人数中。2)用二重循环实现以上过程,外层循环模拟50个同学,内层循环模拟五门课程。 16PPT学习交流5/12/202217main( ) int a5,i,j,s,num=0; for ( i=1;i=50;i+) s=0; for( j=0;j=90) s=s+1; if(s=3) num=num+1; printf(“The number of =90 is“%d”,num); 程序如下:对于计算其成绩高于90分的课程数目,应如何编写? 17PPT学习交流5/12/202218【例2】开灯问题:有从1到n依次编号的n个同学和n 盏灯。1号同学将所有的灯都关掉;2号同学将编号为2的倍数的灯都打开;3号同学则将编号为3的倍数的灯作相反处理(该号灯如打开的,则关掉;如关闭的,则打开);以后的同学都将自己编号的倍数的灯,作相反处理。问经n个同学操作后,哪些灯是打开的?18PPT学习交流5/12/2022191)定义有n个元素的a数组,它的每个下标变量ai视为一灯,i表示其编号。ai=1表示灯处于打开状态,ai=0 表示灯处于关闭状态。2)当ai为1时,ai被重新赋为0;当ai为0时,ai被重新赋为1。但通过以下算术运算:ai=1-ai就很好地模拟“开关”灯的操作。我们把这种形式的赋值语句形象地称为“乒乓开关”。分析:19PPT学习交流5/12/202220main( )int n,a1000,i,k; printf(“input a number”); scanf(“%d”,&n); for( i=1;i=n;i+) ai=0; for( i=2;i=n;i+) k=1 while ( i*k=n) ai*k=1-ai*k; k=k+1; for( i=1;i=n;i+) printf(“%d”, ai);程序如下: 程序中第二个for循环i枚举的不是灯的编号,而是编号为i的同学,其内层循环中,就将包含i因素的灯的编号为“i*k”的灯,改变其状态。程序中还用计算省去了用if语句判断编号能被哪些数整除的过程。 20PPT学习交流5/12/202221【例3】右图中所示的圆圈中,我们把相隔一个数据的两个数(如1和10,3和5,3和6)称作是“一对数”,试编写程序求出乘积最大的一对数和乘积最小的一对数。输出格式如下:max: ?*?=?min: ?*?=?其中?表示:找到的满足条件的数和乘积。 1 17 16 8 10 12 16 5 1 9 9 3 15 8 12 621PPT学习交流5/12/2022221)数据有前后“位置”关系,必须用数组来存储。数组定义为anum,则有a0anum-1共num个元素。2)用i代表下标,题目就是顺序将a(i-1)与a(i+1)相乘,求出乘积的最大值和最小值即可。3) 关键是i=num-1时,保证i+1的“值”是0;当i=0时,保证i-1的“值”是num-1,把数组当成圆圈操作通过求余运算很容易实现:当i=num-1时,(i+1)%num等于0;当i=0时(num+i1)%num等于num-1。实现要点:22PPT学习交流5/12/2022234)通过求余运算,便“避免了”判别数组起点与终点的操作。用变量Max记录当前最大的乘积,m、n为对应的两个乘数;变量min记录当前最小的乘积,s、t为对应的两个乘数。23PPT学习交流5/12/202224程序如下:main( )intmax=1,min=32767, a100,num,i,k,m,n,s,t; printf(“input a number”); scanf(“%d”,&num); for( i=0;inum;i+) scanf(“%d”,&ai); for( i=0;imax) max=k; m=ap; n=aq; if (kmin) min=k; s=ap; t=aq; printf(”max=%d*%d=%d”,m,n,max); printf(”min=%d*%d=%d”,s,t,min);返回24PPT学习交流5/12/2022252) 构造下标【例】请编写程序统计100人的身高分布,分布等级:180以上、175180、170175、165170、160165、155-160、155以下。分析: 此类问题表面看不太适合用switch语句来完成。因为即使身高是整数若不借助数学运算至少也有20多种情况,需要20多个case子句。但若注意到每个等级基本是5分一段,通过除法运算将成绩(变量sg)除以5后,分支最多也就只有6个了。 25PPT学习交流5/12/202226main( )int sg,k,s7,t; printf(“Input %d height:”,100); for(k=1;k=100;k+) scanf(“%d”,&sg); if ( sg300) printf(“Input error!,Input again”); k-; continue; t=sg/5-30; if(t=6) s6=s6+1;t=6; else st=st+1; 程序如下:通过计算t=sg/5-30使七类统计区间与数组下标对应,提高了程序效率。这个if语句的功能是什么? 26PPT学习交流5/12/202227for(t=0;k=6;t+)switch(t ) case 0 : printf(“180:%d”,s6”); break; 返回27PPT学习交流 1 1)数组存储减少条件判断)数组存储减少条件判断【例1】某次选举,要从五个候选人(编号分别为1、2、3、4、5)中选一名厂长。请编写程序完成统计选票的工作。实现要点: 1虽然选票发放的数量一般情况下是已知的,但收回的数量通常是无法预知的,所以程序采用随机循环,设计停止标志为“-1”。 2统计过程的简单方法为:先为五个候选人各自设置五个“计数器”a,b,c,d,e,然后根据录入数据,通过多分支语句或嵌套条件语句决定为某个“计数器”累加1。最后输出统计结果。 3.优化数据结构提高程序效率28PPT学习交流main( ) int xp,a,b,c,d,e; a=b=c=d=e=0; printf(input integer number: ); scanf(%d,&xp); while(xp!=-1)switch (a) case 1: a=a+1;break; case 2: b=b+1;break; case 3: c=c+1;reak; case 4: d=d+1;break; case 5: e=e+1;break; default: printf(input data errorn); scanf(%d,&xp); 29PPT学习交流printf(1s number of votes is %dn,a); printf(2s number of votes is %d n,b); printf(3s number of votes is %d n,c); printf(4s number of votes is %d n,d); printf(5s number of votes is %d n,e); 30PPT学习交流实现要点: 把五个“计数器”用数组代替,选票中候选人的编号xp正好做下标,执行Axp=Axp+1就可方便地将选票内容累加到相应的“计数器”中。程序2如下:返回程序改进:这样的程序效率太低,因为程序在执行中要进行大量的比较运算。利用数组做计数器问题可得到很好的解决。31PPT学习交流main( ) int i,xp,a6; printf(“input data until input -1”); scanf(“%d”,& xp ); while(xp!=-1) if (xp=1 & xp=5 ) axp=axp+1; else printf( %d input error!,xp); scanf(“%d”,& xp ); for (i=1;i=5;i+) printf(%d number get %d votes,i,ai); 32PPT学习交流【例例2 2】统计找数字对的出现频率统计找数字对的出现频率 算法说明:输入N(2N100)个数字(在0与9之间),然后统计出这组数中相邻两数字组成的链环数字对出现的次数。例如:输入:N=20 表示要输入数的数目 0 1 5 9 8 7 2 2 2 3 2 7 8 7 8 7 9 6 5 9 输出:(7,8)=2 (8,7)=3 指(7,8)、(8,7)数字对出现次数分别为2次、3次 (7,2)=1 (2,7)=1 (2,2)=2 (2,3)=1 (3,2)=1 33PPT学习交流算法设计: 其实并不是只有一维数组这样的数据结构可以在算法设计中有多采的应用,根据数据信息的特点,二维数组的使用同样可以使算法易于实现,此题就正是如此。 用10*10的二维数组(行、列下标均为0-9),存储统计结果,i行j列存储数字对(i,j)出现的次数,无需存储原始数据,用其做下标,在数据输入的同时就能统计出问题的结果, 34PPT学习交流main( )int a1010,m,i,j,k1,k0;print(“How many is numbers?”); input(n);print(“Please input these numbers:”); input(k0); for (i=2;i=n;i=i+1) input(k1); ak0k1=ak0k1+1; k0=k1;for (i=0;i=9;i=i+1) for (j=0;j=9;j=j+1) if (aij0 and aji0) print(“i,j”)=aij,“j,i”=aji)35PPT学习交流2 2)数组使信息有序化数组使信息有序化 【例1】给1000个职工发工资,每人的工资从键盘输入。为了保证不要临时兑换零钱,且取款的张数最少,取工资前要统计出所有职工的工资所需各种币值(100,50,20,10,5,2,1元共七种)的张数。请编写程序。 当题目中的数据缺乏规律时,很难把重复的工作抽象成循环不变式来完成,但先用数组结构存储这些地信息后,问题就迎刃而解了, 36PPT学习交流main( )int i,j,GZ,A,B8=0,100,50,20,10,5,2,1,S8; for(j=1;j=7;j=j+1) Sj=0; for(i=1;i=1000;i+) scanf(“%d”,&GZ); for(j=1,j=7;j+) A=GZ/Bj; Sj=Sj+A; GZ=GZ-A*Bj; for(i=1;i=7;i+) printf(“%d-%d”,i,Si); 程序说明:每求出一种面额所需的张数后,一定要把这部分金额减去: “GZ=GZ-A*Bj;”,否则将会重复计算。37PPT学习交流问题思考 1、这个例题是否让你进一步体会到什么叫“循环不变式”? 2、先看一个例子若某人的工资是3100,则只需要100元一种币值,但程序中要对所有的币种进行计算,若要避免这种现象怎么样修改程序?返回38PPT学习交流【例2】编程将编号“翻译”成英文。例35706“翻译”成three-five-seven-zero-six。 39PPT学习交流算法设计算法设计1 1: 1) 编号一般位数较多,可按长整型输入和存储。2) 将英文的“zeronine”存储在数组中,对应下标为09。这样无数值规律可循的单词,通过下标就可以方便存取、访问了。3) 通过求余、取整运算,可以取到编号的各个位数字。用这个数字作下标,正好能找到对应的英文数字。4)考虑输出翻译结果是从高位到低位进行的,而取各位数字,比较简单的方法是从低位开始通过求余和整除运算逐步完成的。所以还要开辟一个数组来存储从低位到高位翻译好的结果,并记录编号的位数,最后倒着从高位到低位输出结果。 40PPT学习交流main( ) int i,a10, ind; long num1,num2; char eng106=“zero”,”one”,”two”,”three ”,” four”, ” five”,”six”,”seven”,“eight”,”nine”; print(“Input a num”); input(num1); num2=num1; ind =0;while (num20)aind=num2 mod 10; ind= ind +1; num2=num2/10; print(num1, “English_exp:”, engaind-1);for( i=ind-2;i=0;i=i-1) print(“-”,engai); 41PPT学习交流例例1 1【例1】求X,使X2为一个各位数字互不相同的九位数。分析:只能用枚举法尝试完成此题。由X2为一个九位数,估算X应在1000032000之间。3)记录状态信息42PPT学习交流算法设计: 1) 用一个10 个元素的状态数组p,记录数字09在X2中出现的情况。数组元素都赋初值为1,表示数字09没有被使用过。 2) 对尝试的每一个数x,求x*x,并取其各个位数字,数字作为数组的下标,若对应元素为1,则该数字第一次出现,将对应的元素赋为0,表示该数字已出现一次。否则,若对应元素为0,则说明有重复数字,结束这次尝试。 3) 容易理解当状态数组p中有9个元素为0时,就找到了问题的解。但这样判定有解,需要扫描一遍数组p。为避免这个步骤,设置一个计数器k,在取x*x各个位数字的过程中记录不同的数字的个数,当k=9时就找到了问题的解。 43PPT学习交流main( )long x, y1, y2; int p10, 2,i, t, k,num=0; for (x=10000;x32000; x=x+1) for(i=0; i=9; i=i+1) pi=1; y1=x*x ; y2=y1; k=0; for(i=1; i=9. i=i+1) t=y2 mod 10; y2=y2/10; if(pt=1) k=k+1; pt=0; else break; if(k=9) num=num+1; print (“No.”,num , “:n=”, x, “n2=”, y1); 44PPT学习交流【例2】游戏问题:12个小朋友手拉手站成一个圆圈,从某一个小朋友开始报数,报到7的那个小朋友退到圈外,然后他的下一位重新报“1”。这样继续下去,直到最后只剩下一个小朋友,求解这个小朋友原来站在什么位置上呢? 实现要点: 首先是如何表示状态的问题。开辟12个元素的数组,记录12个小朋友的状态,开始时将12个元素的数组值均赋为1,表示大家都在圈内。这样小朋友报数就用累加数组元素的值来模拟,累加到7时,该元素所代表的小朋友退到圈外,将相应元素的值改赋为0,这样再累加到该元素时和不会改变,又模拟了已出圈外的状态。45PPT学习交流main( ) int a100,i,k,p,m; printf(“input numbers of game:”); scanf(“%d”,&n); printf(“input serial number of game start:”); scanf(“%d”,&k); printf(“input number of out_ring:”); scanf(“%d”,&m); for( i=1;i=n;i+) ai=1; 其中n表示做游戏的总人数,k表示开始及状态数组的下标变量,m表示退出圈外的报数点,即报m的人出队,p表示已退出圈外的人数。程序如下:46PPT学习交流p=0; while (pn-1) x=0; while (xn) k=1; x=x+ak; printf(“%d”, k); ak=0; p=p+1; for( i=1;in时,赋k=1,表示n号报完数就该1号报数。模拟了将n个人连成了一个“圈”的情况。 2、x为“报”出的数,x=m时输出退出圈外人的下标k,将ak赋值为0; 3、p=n-1时游戏结束; 4、最后检测还在圈上ai=1的人,输出其下标值即编号。返回47PPT学习交流48二、信息数字化1. 状态信息数字化1)提高效率【例1】冒泡排序算法的改进分析: 冒泡排序算法的基本思想就是:相邻数据比较若逆序则交换,逐渐将小数据冒到数组的前面,大的数据则沉到数组的后面,从而完成排序工作。 48PPT学习交流5/12/202249数据原本有序的概率并不高,但经过少于n-1趟操作后,数据已经有序的概率却非常高。为提高效率,可以对冒泡排序算法进行改进,当发现某趟没有交换后就停止下一趟的比较操作。用标志量来记录每趟交换数据的情况,如flag=0表示没有进行过交换,一但有数据进行交换则置flag为1,表示已进行过交换。当一趟比较交换完成后,若flag仍为0时,则无需进行下一趟操作,否则若flag为1时,只能继续进行下一趟操作。 49PPT学习交流5/12/202250main() int i,j,t,n,a100,flag; printf(“input data number(100):”);scanf(“%d”,&n); printf(“input %d data:”,n); for(i=0;in;i+) scanf(“%d”,&ai); flag=1; for(i=1;i=i;j-) if(ajaj-1) t=aj; aj=aj-1; aj-1=t; flag=1; for(i=0;in;i+) printf(%d ,ai); 改进后的程序如下: 返回50PPT学习交流5/12/202251程序说明:1)排序前“for(i=1;i=n-1 & flag=1;i+) 之前”的flag=1;是为了保证循环的开始。 2)内层循环外的flag=0;是假设这趟比较中没有交换,一但发生交换操作在内层循环中就置flag=1;,以保证继续下一趟操作。51PPT学习交流5/12/2022522)表示复杂情况【例2】编写程序判定从键盘输入n个数据互不相等。 main( )int a100 ,i,j,t,n; scanf(“%d”,&n); for (i=1;i=n;i+) scanf(“%d”,&ai); t=1; for (i=1;i=n-1;i+) for (j=i+1;j=b+c | b=a+c | c=a+b) printf(“dont form a triangle”); else flag=0; if (a*a=b*b+c*c | b*b=a*a+c*c | c*c=a*a+b*b) printf(“form a right-angle triangle”); flag=1; if(a=b & b=c) printf(“form a equilateral triangle”); flag=1; else if(a=b | b=c | c=a) printf(“form a equal haunch triangle”); flag=1; if(flag=0) printf(“form a triangle”); 程序如下: 55PPT学习交流5/12/202256【例3】编写程序,求任意三个数的最小公倍数。程序如下: #include max(int x, int y, int z ) if(xy&xz) return(x); else if (yx & yz)return(y); else return(z); main( ) int x1,x2,x3,t=1,i,flag,x0; printf(“Input 3 number:”); scanf(“%d%d%d”,&x1,&x2,&x3); 56PPT学习交流5/12/202257for (i=2;i=x0;i+) flag=1; while(flag) flag=0; if (x1%i=0) x1=x1/i; flag=1; if(x2%i=0) x2=x2/i; flag=1; if(x3%i=0) x3=x3/i; flag=1; if (flag=1) t=t*i; x0=max(x1,x2,x3); printf(“The result is%dn”,t); 返回57PPT学习交流5/12/2022582. 特征信息数字化1) 逻辑类问题【例1】警察局抓了a,b,c,d四名偷窃嫌疑犯,其中只有一人是小偷。审问中 a说:“我不是小偷。” b说:“c是小偷。” c说:“小偷肯定是d。” d说:“c在冤枉人。”现在已经知道四个人中三人说的是真话,一人说的是假话,问到底谁是小偷?58PPT学习交流5/12/202259实现要点: 用变量x存放小偷的编号,则x的取值范围从1取到4,就尝试了他们中的某人是小偷的所有情况。四个人所说的话就可以分别写成: a说的话:x!=1 b说的话:x=3 c说的话:x=4 d说的话:x!=4或not(x=4) 注意利用前面学习到的技巧,在x的枚举过程中,当这四个逻辑式的值相加等于3时,即表示“四个人中三人说的是真话,一人说的是假话”,所以以此为定解条件。分析: 将a,b,c,d将四个人进行编号,号码分别为1,2,3,4。则问题可用枚举尝试法来解决。 59PPT学习交流5/12/202260程序如下:main( )int x; for (x=1;x=4;x+) if (x!=1)+(x=3)+(x=4)+(x!=4)=3) printf(“%c is a thief .”, chr(64+x);运行结果: c is a thief .程序说明: 为了程序的方便运行我们对人名进行了数字化,但结果的形式还要符合题目的描述,所以输出时,将数字转化为对应的字母。这个程序可以方便的改写成PASCAL或BASIC程序,就C语言而言程序还可直接写成如下形式:60PPT学习交流5/12/202261 main( )int x; for (x=a;x=d;x+) if ( (x!=a)+(x=c)+(x=d)+(x!=d)=3 ) printf(“%c is a thief .”, x);61PPT学习交流5/12/202262【例2】三位老师对某次数学竞赛进行了预测。他们的预测如下:甲说:学生A得第一名,学生B得第三名。乙说:学生C得第一名,学生D得第四名。丙说:学生D得第二名,学生A得第三名。竞赛结果表明,他们都说对了一半,说错了一半,并且无并列名次,试编写程序输出A、B、C、D各自的名次。62PPT学习交流5/12/202263分析: 用数1,2,3,4分别代表学生a,b,c,d获得的名次。问题就可以利用三重循环把所有的情况枚举出来。程序如下: 返回63PPT学习交流5/12/202264main( )int a,b,c,d; for( a=1;a=4;a+) for( b=1;b=4;b+) if (a!=b) for( c=1;c=4;c+) if (c!=a & c!=b) d=10-a-b-c; if (d!=a & d!=b & d!=c ) if (a=1)+(b=3)=1 & (c=1)+(d=4)=1 &(d=2)+(a=3)=1) printf( “a=%d,b=%d ,c=%d,d=%d”,a,b,c,d); 运行结果:a=4,b=3,c=1,d=264PPT学习交流5/12/202265实现要点: 【例1】填写运算符 输入任意5个数x1,x2,x3,x4,x5每相邻两个数之间填上一个运算符+、-、* 或 /。在填入四个运算符后,使得表达式值为一个指定值y(y由键盘输入)。求出所有满足条件的表达式。模仿人去试填所有的运算符 ,结果是什么2) 智巧类问题?1)枚举法解题2)若当前运算符轮到/则运算符右端的数必须非零,因为零不能当除数。65PPT学习交流5/12/2022663)现在接着考虑+、-、*、/应如何表示,才能方便程序对表达式的求值?4)如何处理“先乘除/后加减”的优先顺序? 模拟计算:f-减去标志。减法运算时,置f=-1,否则f=1;q-若当前运算符为+(-)时,q存贮运算符的左项 值;若当前运算符为*(/)时,q存贮两数乘(除) 后结果;p-累加器。每填一个算符p=p+f*q。为了解决运算的优先级问题,我们设置如下变量:66PPT学习交流5/12/202267程序如下:main( )int j, k,f,i5, total; float n6,p,q; char c5 = ,+,-,*,/; printf(“n input five number”); for(j=1;j=5;j+) scanf(“%f”,&nj); total=0; for (i1=1 ;i1=4 ;i1+) if (i14) | (n2!=0) ) for (i2=1 ;i2=4 ;i2+) if( (i24) | (n3!=0) ) for (i3=1 ;i3=4 ;i3+) if (i34) |(n4!=0) ) for (i4=1 ;i4=4 ;i4+) if(i44) | (n5!=0) ) p=0; q=n1; f=1;1.四个for循环后的四个if语句 的作用是什么?2.四个数组元素i1、i2、i3、i4代表四个运算符,定义的作用是什么? 67PPT学习交流5/12/202268for (k=1;k=4;k+) switch (ik) case 1: p=p+f*q; f=1; q=nk+1;break; case 2: p=p+f*q; f=-1; q=nk+1;break; case 3: q=q*nk+1;break; case 4: q=q/nk+1;if ( p+f*q=n0) total+; printf (“n total:%5d: ” ,total); for (k=1;k=4;k+) printf (“%f %c”,nk,cik); printf (“%f=%f”,n5, n0); if (total % 20=0 ) 每20个方案为一屏,逐屏显示 printf (“press enter to continue”); getchar( ); 68PPT学习交流5/12/202269【例2】有10箱产品每箱有1000件,正品每件100克。其中的几箱是次品,次品每件比正品轻10克,问能否用秤只称一次,就找出哪几箱是次品。程序如下:main( ) int i,k,n,w1=0,w2=0,t=1; printf(“n Input the number of boxes:”);scanf(“%ld”,&n); printf(“n”); for (i=1;i=0)t=t*2; k=k+1; printf(“n %d is bad”,k); w1=w1-t/2; 70PPT学习交流5/12/202271【例3】编写程序对输入的一个整数,判断它能否被3,5,7整除,并输出以下信息之一: 1)能同时被3,5,7整除; 2)能被其中两数(要指出哪两个)整除; 3)能被其中一个数(要指出哪一个)整除; 4)不能被3,5,7任一个整除。71PPT学习交流5/12/202272switch (k) case 3: printf(“n All”); break; case 2: printf(“n two”); break; case 1: printf(“n one”); break; case 0: printf(“n none“); break; 程序1: main( )long n; int k; printf(“nPlease enter a number:”); scanf(“%1d”,&n); k=(n%3=0)+(n%5=0)+(n%7=0) 72PPT学习交流5/12/202273程序2: main( )long n; int k; printf(“n Please enter a number:”); scanf(“%1d”,&n); k=(n%3=0)+(n%5=0)*2+(n%7=0)*473PPT学习交流5/12/202274程序中k表示整除的情况值。 程序1中,k的范围是03可以表示四种情况, 而程序2中,为k赋值的表达式是: (n%3=0)+(n%5=0)*2+(n%7=0)*4, k的范围是07可以表示八种情况。switch (k) case 7: printf(“n All”); bresk; case 6: printf(“n 5 and 7 is ”); break; case 5: printf(“n 3 and 7 is ”); break; case 4: printf(“n 7 is ”); break; case 3: printf(“n 3 and 5 is ”); break; case 2: printf(“n 5 is ”); break; case 1: printf(“n 3 is ”); break; case 0: printf(“n none“); break; 程序说明: 返回74PPT学习交流5/12/202275三、文件 1. C语言文件概述 存储在外存储器上一组相关数据集合称为“文件”每个文件都有一个文件名 OS 广义的文件 狭义的文件数据文件程序的处理的数据(输入)和结果(输出)75PPT学习交流5/12/202276从文件存储的方式来看,文件可分为: ASCII码文件和二进制码文件两种ASCII文件也称为文本文件,这种文件在磁盘中存放时每个字符对应一个字节,用于存放对应的ASCII码。 二进制文件是按二进制的编码方式来存储文件的。 输入输出字符流的开始和结束,只由程序控制而不受物理符号的控制。 则把这种文件称作“流式文件”。76PPT学习交流772. 文件的打开与关闭1)文件指针 文件在进行读、写操作之前要先打开,使用完毕后要关闭。 打开文件实际上是建立文件的各种有关信息,并使文件指针指向该文件,以便进行其它操作。 关闭文件则是断开指针与文件之间的联系,也就禁止再对该文件进行操作。 77PPT学习交流5/12/202278用一个指针变量指向一个文件,这个指针称为文件指针。通过文件指针就可对它所指的文件进行各种操作。定义文件指针的一般形式为: FILE *指针变量标识符;2)文件的打开 就是打开外存数据进入内存的通道,并分配一定的内存空间存储进行内存中的文件数据。78PPT学习交流5/12/202279fopen()函数用来打开一个文件,一般形式为:文件指针名=fopen(文件名,使用文件方式);对于文件使用方式有以下几点说明:1)文件使用方式由r,w,a,t,b,+六个字符拼成,各字符的含义是: r(read): 读 w(write): 写 a(append): 追加 t(text): 文本文件,可省略不写 b(banary): 二进制文件 +: 读和写79PPT学习交流2)凡用“r”打开一个文件时,该文件必须已经存在,且只能从该文件读出。3) 用“w”打开的文件只能向该文件写入。若打开的文件不存在,则以指定的文件名建立该文件,若打开的文件已经存在,则将该文件已有信息删去,重建一个新文件。4)若要向一个已存在的文件追加新的信息,只能用“a”方式打开文件。(该文件必须存在)5) 在打开一个文件时,如果出错,fopen将返回一个空指针值NULL。80PPT学习交流5/12/2022813)文件的关闭关闭文件的操作是由函数fclose()实现的,一般形式是: fclose(文件指针);正常完成关闭文件操作时,fclose函数返回值为0。如返回非零值则表示有错误发生。RETURN81PPT学习交流5/12/2022823 文件的读写 字符读写函数 :fgetc和fputc 字符串读写函数:fgets和fputs 数据块读写函数:freed和fwrite 格式化读写函数:fscanf和fprinf1 字符读写函数fgetc和fputc字符读写函数是以字符(字节)为单位的读写函数。每次可从文件读出或向文件写入一个字符。1)读字符函数fgetc()fgetc函数的功能是从指定的文件中读一个字符,形式为: 字符变量=fgetc(文件指针);82PPT学习交流5/12/202283【注意事项】 在fgetc函数调用中,读取的文件必须是以读或读写方式打开的。读取字符的结果也可以不向字符变量赋值。在文件内部有一个位置指针。用来指向文件的当前读写字节。文件系统在文件的末尾存储了一个结束标志EOF,表文件中的字符已读“完”了 。83PPT学习交流5/12/2022842)写字符函数fputcfputc函数的功能是把一个字符写入指定的文件中,形式为: fputc(字符,文件指针); 【注意事项】 被写入的文件可以用写、读写、追加方式打开,用写或读写方式打开一个已存在的文件时将清除原有的文件内容,写入字符从文件首开始。 每写入一个字符,文件内部位置指针向后移动一个字节。fputc函数有一个返回值,如写入成功则返回写入的字符,否则返回一个EOF 。84PPT学习交流5/12/2022852 字符串读写函数fgets和fputs1)读字符串函数fgets功能是从指定的文件中读一个字符串到字符数组中,形式为: fgets(字符数组名,n,文件指针);【注意事项】 在读出n-1个字符之前,如遇到了换行符或EOF,则读出结束。 fgets函数也有返回值,其返回值是字符数组的首地址。85PPT学习交流5/12/2022862)写字符串函数fputs功能是向指定的文件写入一个字符串,形式为: fputs(字符串,文件指针);3数据块读写函数fread和fwtrite读数据块函数调用的一般形式为:fread(buffer,size,count,fp);写数据块函数调用的一般形式为:fwrite(buffer,size,count,fp);86PPT学习交流5/12/202287其中:buffer 是一个指针,在fread函数中,它表 示存放输入数据的首地址;在fwrite函数中,它表示存放输出数据的首地址。size 表示数据块的字节数。count 表示要读写的数据块块数。fp 表示文件指针。4格式化读写函数fscanf和fprintffscanf(文件指针,格式字符串,输入表列);fprintf(文件指针,格式字符串,输出表列);RETURN87PPT学习交流5/12/2022884 文件定位1定位在文件首的函数rewind函数的其调用形式为:ewind(文件指针);它的功能是把文件内部的位置指针移到文件首。2相对定位函数fseek函数用来移动文件内部位置指针,形式为: fseek(文件指针,位移量,起始点);88PPT学习交流5/12/202289其中:“文件指针”指向被移动的文件。 “位移量”表示移动的字节数。 “起始点”表示从何处开始计算位移量。规定的起始点有三种:文件首,当前位置和文件尾。起始点起始点 表示符号表示符号 数字表示数字表示文件首文件首 SEEK_SET 0当前位置当前位置 SEEK_CUR 1文件末尾文件末尾 SEEK_END 2RETURN89PPT学习交流5/12/2022905 文件其它相关函数1)文件结束检测函数feof函数调用格式:feof(文件指针);功能:判断文件是否处于文件结束位置, 如文件结束,则返回值为1,否则为0。2)读写文件出错检测函数调用格式:ferror(文件指针); 功能:检查文件在用各种输入输出函数进行 读写时是否出错。如ferror返回值为0表示未出错,否则表示有错。90PPT学习交流5/12/2022913)文件出错标志和文件结束标志置0函数调用格式:clearerr(文件指针); 功能:本函数用于清除出错标志和文件结束标志,使它们为0值。RETURN91PPT学习交流5/12/2022例 编程求M行N列的二维数组每一列的最小值,二维数组存储在文件“in.dat”中,求解的结果存储到文件“out.dat”中。并将文件“in.dat”中的第3个数据和倒数第3个数据输出。(in.dat中的每个数据占6B)#include #define M 3#define N 4void fun (int ttMN, int ppN) int i,j,k;for(i=0;iN;i+) k=tt0i; for(j=1;jM;j+) if (ttjik) k=ttji;ppi=k; 92PPT学习交流fun1(int tMN,int pN) int i, j, k; FILE *rf, *wf ; rf = fopen(in.dat,r); wf = fopen(out.dat,w);if(rf =NULL|wf=NULL) perror(open error); return -1; for(i=0; iM; i+) for(j=0; jN; j+) fscanf (rf, %d, &tij); fun (t, p); for (k = 0; k N; k+) fprintf (wf, %4d, pk); fprintf(wf, n); fclose(rf); fclose(wf);93PPT学习交流fun2( ) int k; FILE *rf, *wf ; rf = fopen(in.dat,r);if(rf =NULL)perror(open error); return -1; fseek(rf,(3-1)*6,SEEK_SET);fscanf (rf, %d, &k);printf ( %4d , k);fseek(rf,-3*6,SEEK_END);fscanf (rf, %d, &k);printf ( %4d , k);94PPT学习交流main()int p N,tMN; int i, j, k; fun1(t,p); printf (The original data is : n); for(i=0; iM; i+) for(j=0; jN; j+) printf (%6d, tij); printf(n); printf(nThe result is:n); for (k = 0; kN; k+) printf ( %4d , pk); printf(n); fun2();95PPT学习交流此课件下载可自行编辑修改,供参考!感谢您的支持,我们努力做得更好!96PPT学习交流
展开阅读全文