C语言第五六次作业解析.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,C,语言作业解析,第四弹,。原来真正变态的是这两作业哇,原本是做完第五次作业等大家数分期中考完以后给大家，结果直接出了第六次。就顺便做了。买一送一还包邮哦亲,虽然这两次作业比较难。理解起来困难无比。不过考试的时候不会有这么变态的题目啦,放心,当前编程题：,11,级第五次作业,-,凸多边形面积,1.,【,问题描述,】,给出平面上一组顶点的坐标，计算出它们所围成的凸多边形的面积。,【,输入形式,】,从标准输入读取顶点坐标。格式为：第一行是点的个数,N,（,3N15,），后面紧接着,N,行，每行两个数字（由空格隔开），分别表示该点的,X,、,Y,坐标（,0X,，,Y32767,）。所有点的坐标互不相同，且按顺时针次序给出。输入数据确保该多边形是一个凸多边形。,【,输出形式,】,向标准输出打印一个浮点数，是该多边形的面积。该浮点数保留两位小数。,【,输入样例,】4 3,33,01,01,2【,输出样例,】5.00【,样例说明,】,输入数据表示了如图所示的四边形。其面积为,5.00,。,提示：求三角形面积可用海伦公式，求平方根可用,头文件中定义的,sqrt,函数。,【,评分标准,】,结果完全正确得,20,分，每个测试点,4,分。提交程序名为：,points.c,。,本题解析：,这个题是把凸,n,边形面积分成,n-2,个三角形面积和来做的。用海伦公式,S=sqrt(p*(p-a)*(p-b)*(p-c),P=(a+b+c)/2 a,b,c,为三边长,例如,n,边形点为,a,1,a,2,a,n,那,S=(Sa,1,a,k,a,k+1,)(2KN-1),边长则为两点间距离。,#include,#include,int main(),int n;,float x15,y15;,int i;,float dx,dy;,float tot=0;,float a,b,c,p;,scanf(%d,for(i=0;in;i+),scanf(%f%f,for(i=1;in-1;i+),dx=x0-xi;,dy=y0-yi;,a=sqrt(dx*dx+dy*dy);/*,两点间距离公式*,/,dx=xi-xi+1;,dy=yi-yi+1;,b=sqrt(dx*dx+dy*dy);,dx=xi+1-x0;,dy=yi+1-y0;,c=sqrt(dx*dx+dy*dy);,p=(a+b+c)/2;,tot+=sqrt(p*(p-a)*(p-b)*(p-c);/*,海伦公式*,/,printf(%.2f,tot);,return 0;,当前编程题：,11,级第五次作业,-,整数的,N,进制字符串表示,【,问题描述,】,编写函数,itob(n,s,b),用于把整数,n,转换成以,b,为基的字符串并存储到,s,中,.,编写程序,使用函数,itob(n,s,b),将输入的整数,n,转换成字符串,s,将,s,输出,.,转换后的字符串从最高的非零位开始输出。如果,n,为负数，则输出的字符串的第一个字符为,-,。,b,为大于,1,小于,37,的任意自然数值。当,b=2,时，输出字符只可能是,0,和,1,；当,b=16,时，输出字符串中可能含有字符为,0-9,，,a-f(,字母以小写输出,),。,b,还可以是其它数值。比如输入,n=33,b=17,，则输出,33,的,17,进制值为,1g,。,【,输入形式,】,控制台输入整数,n,和,b,，其中,n,可以为负数。,n,和,b,以空格分隔,.【,输出形式,】,控制台输出转化后的字符串,s.【,样例输入,】5 2【,样例输出,】101【,样例说明,】5,的二进制就是,101【,评分标准,】,结果完全正确得,20,分，每个测试点,4,分。提交程序名为：,itob.c,本题解析：,十进制转换为其他进制的方法是不断除目标进制的数取余数，然后倒序输出。例如,5,变为二进制就是,5%2=1,；,5/2=2;2%2=0;2/2=1;1%2=1;,得到,101,倒序得到,101,即为正解。十进制以上则是若目标大于,10,就变为相应的字母即可。,如果目标数为负数，则先忽略负号求解最后加上一个负号就可以了,#include,#include,void itob(int n,char s,int b),int flag=1;,int sum=0;,int i,j;,char ch;,if(n0)/*,不断除,b,取余*,/,ssum+=n%b;,n=n/b;,for(i=0,j=sum-1;ij;i+,j-),/*,将数字倒序存放*,/,ch=si;si=sj;sj=ch;,for(i=0;isum;i+),if(si0;i-),si=si-1;,s0=-;,int main(),int n,b;,char s100;,scanf(%d%d,itob(n,s,b);,printf(%s,s);,return 0;,当前编程题：,11,级第五次作业,-,求两组整数的异或集,3.【,问题描述,】,从标准输入中输入两组整数,(,每行不超过,20,个整数，每组整数中元素不重复,),合并两组整数，去掉在两组整数中都出现的整数，并按从大到小顺序排序输出（即两组整数集“异或”）。,【,输入形式,】,首先输入第一组整数，以一个空格分隔各个整数；然后在新的一行上输入第二组整数，以一个空格分隔，行末有回车换行。,【,输出形式,】,按从大到小顺序排序输出合并后的整数集（去掉在两组整数中都出现的整数，以一个空格分隔各个整数）。,【,样例输入,】5 1 4 32 8 7 9-6 5 2 87 10 1【,样例输出,】87 32 10 9 8 7 4 2-6【,样例说明,】,第一组整数为,5 1 4 32 8 7 9-6,，第二组整数分别为,5 2 87 10 1,。将第一组和第二组整数合并（去掉在两组整数中都出现的整数,5,和,1,），并从大到小顺序排序后结果为,87 32 10 9 8 7 4 2-6,。,【,评分标准,】,该题要求输出两组整数的异或集，共有,5,个测试点，提交程序文件名为,xor.c,。,本题解析：,求异或，同时降序输出。那么将问题简化后可以发现如果将两个数组中的数都读进同一个数组然后降序排序若是数组中存在相同元素则不输出，若只出现一次则输出。那么结果与题目要求就相同了。,#include,int main(),int a100;,int i,j,k;,int sum=0;,char ch;,int tot=0;,scanf(%d,while(1),ch=getchar();,if(ch=n)tot+=1;,if(tot=2)break;,scanf(%d,/*,这里是进行读入，由于一共有两行那么每读完一个数就读入一个字符判断这个字符是不是换行符，当出现两个换行符的时候读入结束*,/,for(i=0;isum;i+),for(j=i+1;jsum;j+),if(aiaj),k=ai;,ai=aj;,aj=k;,/*,降序排序*,/,asum=5257;/*,保证,asum,不与前面的数相同*,/,int flag=0;/*flag,表示已经输出了多少数，若为,0,则不需要先输出空格，否则输出空格与前面输出的数字隔开*,/,for(i=0;isum;i+),if(i=0)if(ai!=ai+1),if(flag)printf();,printf(%d,ai);,flag+;,if(i!=0)if(ai!=ai+1)&(ai!=ai-1),if(flag)printf();,printf(%d,ai);,flag+;,当前编程题：,11,级第五次作业,-,字符串中字符排序,4.,【,问题描述,】,编写一个程序，从键盘接收一个字符串，然后按照字符顺序从小到大进行排序，并删除重复的字符。,【,输入形式,】,用户在第一行输入一个字符串。,【,输出形式,】,程序按照字符,(ASCII),顺序从小到大排序字符串，并删除重复的字符进行输出。,【,样例输入,】badacgegfacb【,样例输出,】abcdefg【,样例说明,】,用户输入字符串,badacgegfacb,，程序对其进行按从小到大,(ASCII),顺序排序，并删除重复的字符，最后输出为,abcdefg【,评分标准,】,结果完全正确得,20,分，每个测试点,4,分。提交源程序名为,stringsort.c,本题解析：,这个题做法比较多。一种简单的做法是：由于一共只有,255,个,ascii,码的值。那么开一个,300,的数组,a ai,表示,ascii,码为,i,的字符出现的次数，输出时从,0,到,255(,或,255,以上，例如,300),循环，若,ai,不为,0,则输出对应的字符。,#include,#include,int main(),int a300;,int i,j;,char k;,char s200;,memset(a,0,sizeof(a);,scanf(%s,s);,for(i=0;istrlen(s);i+),asi+;,for(j=0;j260;j+),if(aj),k=j;,printf(%c,k);,当前编程题：,11,级第五次作业,-,最长升序子串,5.【,问题描述,】,输入一行字符串，该字符串只由小写英文字母,a-z,组成，且其中的字符可以重复，最长不超过,10000,个字符。从该字符串中按顺序挑选出若干字符（不一定相邻）组成一个新串，称为“子串”。如果子串中每两个相邻的字符或者相等，或者后一个比前一个大，则称为“升序子串”。编程求出输入字符串的最长升序子串的长度。例如，由输入字符串,abdbch,可以构成的升序子串有：,abd,、,abch,、,bbch,、,abbch,等。其中最长的升序子串是,abbch,，其长度为,5,。,【,输入形式,】,从标准输入读取一行字符串，该串不含空格，以回车符结束。,【,输出形式,】,向标准输出打印一个正整数，是字符串中最长的升序子串的长度，在行末要输出一个回车符。,【,输入样例,】abdbch【,输出样例,】5【,样例说明,】abdbch,中最长子串是,abbch,，长度是,5,。,【,评分标准,】,结果完全正确得,20,分，每个测试点,4,分。上传,c,语言源程序为,up.c,。,本题解析：,这道题是从出现作业为止最难得题目。涉及到一些动态规划的思想。,(,我只想到这一种做法，欢迎大家有简单做法的来分享,),用,fij,表示到字符串,s,中的第,i,个字符为止最高位为,j(,用,1-26,分别代替,a-z),的最长字串的字符数。,动态转移方程为：,Fij=Fi-1j(sij),Fij=max(fi-1k)+1(1kj)(si=j),这个题目不是很好讲清楚，如果想透彻的理解的话可以来找我,(,中,408 JRC),不过。不保证一定能讲清楚。,#include,#include,int main(),char s10001;,int f1000127;,int i,j,k,l;,scanf(%s,s);l=strlen(s);,memset(f,0,sizeof(f);/*f,数组初始化*,/,f0s0-a+1=1;/*f0s0,对应的值应该是,1,，因为以,s0,为终结的最长字串长度为,1*/,for(i=1;il;i+),for(j=1;j=26;j+),if(j=si-a+1),for(k=1;k=j;k+),if(fijfi-1k+1),fij=fi-1k+1;,else fij=fi-1j;,int max=0;,for(i=1;imax)max=fl-1i;,printf(%d,max);,当前编程题：,11,级第五次作业,-,字符串替换（新）,6.【,问题描述,】,编写程序将一个指定文件中某一字符串替换为另一个字符串。要求：（,1,）被替换字符串若有多个，均要被替换；（,2,）指定的被替换字符串，大小写无关。,【,输入形式,】,给定文件名为,filein.txt,。从控制台输入两行字符串（不含空格，行末尾都有回车换行符），分别表示被替换的字符串和替换字符串。,【,输出形式,】,将替换后的结果输出到文件,fileout.txt,中。,【,评分标准,】,该题要求得到替换后的文件内容，共有,5,个测试点。上传,C,语言文件名为,replace.c,。,本题解析：,这个题就是首先用一个字符串将,filein.txt,中的东西全部读入进来，然后进行一个判断与替换。对每一小段字符串都判断是不是与需要被替换的东西相等即可。,#include,#include,char a200,b200,c2000;,int judge(int i,int l),/*,判断从第,i,位开始的,l,位是否与待替换字符串一样*,/,int j;,for(j=0;jl;j+),if(ci+j!=aj)&(ci+j!=aj+a-A)&(ci+j!=aj+A-a)/*,注意大小写*,/,return 0;,return 1;,int main(),int l,i,len=0;,char ch;,scanf(%s,a);,scanf(%s,b);,l=strlen(a);,freopen(filein.txt,r,stdin);,freopen(fileout.txt,w,stdout);,memset(c,0,sizeof(c);,while(ch!=EOF),ch=getchar();,clen+=ch;,for(i=0;i=len-1),/*,如果剩余字符数不到待替换字符串的长度的时候直接输出就可以了*,/,printf(%c,ci);,else,if(judge(i,l),/*,如果一致的话就替换*,/,printf(%s,b);,i+=l-1;,else/*,否则输出当前位*,/,printf(%c,ci);,exit(0);,return 0;,11,级第六次作业,-,合并字符串,1.,【,问题描述,】,编写一个函数,char*str_bin(char*str1,char*str2),，,str1,、,str2,是两个有序字符串（其中字符按,ASCII,码从小到大排序），将,str2,合并到字符串,str1,中，要求合并后的字符串仍是有序的，允许字符重复。在,main,函数中测试该函数：从键盘输入两个有序字符串，然后调用该函数，最后输出合并后的结果。,【,输入形式,】,分行从键盘输入两个有序字符串（不超过,100,个字符）,【,输出形式,】,输出合并后的有序字符串,【,输入样例,】acegbdfh【,输出样例,】abcdefgh【,样例说明,】,输入两个有序字符串,aceg,和,bdfh,，输出合并后的有序字符串,abcdefgh【,评分标准,】,结果完全正确得,20,分，每个测试点,4,分，提交程序文件名为,combine.c,。,本题解析：,这道题主要用到了双队列维护。就是说将两个字符串看为两个队列，然后从排头开始出列，哪一列的排头比较小就出列同时出现一个新的排头。也就是原来的排头后面的那个字符,#include,#include,char str3200;,void str_bin(char str1,char str2),int l1,l2;,l1=strlen(str1);l2=strlen(str2);/*,分别为队列长度*,/,int i=0,j=0,k=0;,while(il1|jl2),if(str1i=0)str3k+=str2j+;/*,如果第一列的人都出列了则出列第二列的*,/,else if(str2j=0)str3k+=str1i+;,else if(str1istr2j)str3k+=str1i+;/*,否则的话比较大小，谁小谁出*,/,else str3k+=str2j+;,str3k=0;,int main(),char str1100,str2100;,scanf(%s%s,str1,str2);,str_bin(str1,str2);,printf(%s,str3);,11,级第六次作业,-,删除子串,2.,【,问题描述,】,编写一个程序，当在一个字符串中出现子串时就删除它。,【,输入形式,】,用户在第一行输入一个字符串，用户在第二行输入一个子串。,【,输出形式,】,程序在下一行输出删除其中所有子串后的字符串。如果字符串不包含子串则输出原字符串本身。,【,样例输入,】I am a boy!a【,样例输出,】I m boy!【,样例说明,】,用户首先输入字符串,I am a boy!,然后输出子串,a,程序会寻找字符串中的子串删除它，最后 将删除后的结果输出,:I#m#boy!#,表示空格。,【,评分标准,】,结果完全正确得,20,分，每个测试点,4,分。提交程序名为：,delsubstring.c,。,本题解析：,这道题跟第五次作业的最后一题基本一样。只不过被替换的字符串变成了空的而已。解析见第五次作业第六题。,#include,#include,char a200,b200;,int judge(int i,int l),int j;,for(j=0;jl;j+),if(ai+j!=bj)return 0;,return 1;,int main(),int l;,gets(a);,gets(b);,l=strlen(b);,int i;,for(i=0;istrlen(a);i+),if(judge(i,l)i+=l-1;,else printf(%c,ai);,return 0;/*,不过感觉程序上简单多了。*,/,11,级第六次作业,-,超长正整数的减法,3.,【,问题描述,】,编写程序实现两个超长正整数（每个最长,80,位数字）的减法运算。,【,输入形式,】,从键盘读入两个整数，要考虑输入高位可能为,0,的情况（如,00083,）。,1.,第一行是超长正整数,A,；,2.,第二行是超长正整数,B,；,【,输出形式,】,输出只有一行，是长整数,A,减去长整数,B,的运算结果，从高到低依次输出各位数字。要求：若结果为,0,，则只输出一个,0,；否则输出的结果的最高位不能为,0,，并且各位数字紧密输出。,【,输入样例,】234098134098703578230056【,输出样例,】,134098703577995958【,样例说明,】,进行两个正整数减法运算，,234098,134098703578230056=,134098703577995958,。,【,评分标准,】,完全正确得,20,分，每个测试点,4,分，提交程序文件名为,subtract.c,。,本题解析：,高精度减法。因为是两个正整数。所以先要去掉题目描述的最高位处的多余的,0,其次是比较两个数字的大小。如果被减数小于减数，则是输出一个符号然后将两个数对调。,注意，由于此处是高精度数，读入时需要直接使用字符串读入，采用竖式相减得方法还要考虑退位的问题。同时要从个位数开始相减。,#include,#include,int c101;,int judge(char a,char b)/*,判断,a,与,b,的大小关系*,/,int i;,if(strlen(a)strlen(b)return 1;,for(i=0;istrlen(a);i+)/*,一样多的话逐位比较大小,第一位不同的谁大则谁比较大*,/,if(aibi)return 0;,return 1;,void minus(char a,char b)/*,减法操作*,/,int i,j;,char k;,for(i=0,j=strlen(a)-1;ij;i+,j-)/*,首先将字符串倒过来，方便从个位开始相减*,/,k=ai;ai=aj;aj=k;,for(i=0,j=strlen(b)-1;ij;i+,j-),k=bi;bi=bj;bj=k;,for(i=0;i=strlen(b)ci=ai-0;,else ci=ai-bi;,for(i=0;istrlen(a)-1;i+)/*,退位操作*,/*,下页还有*,/,if(ci0)ci+=10;ci+1-=1;,int main(),int i,j,k,s=0,l;,char a100,b100;,memset(c,0,sizeof(c);,gets(a);,gets(b);,while(as=0)s+;/*,去掉多余的,0*/,l=strlen(a)-s;,for(i=0;i=l;i+),ai=ai+s;,s=0;,while(bs=0)s+;,l=strlen(b)-s;,for(j=0;j=l;j+),bj=bj+s;,if(judge(a,b)minus(a,b);,else printf(“-”);minus(b,a);/*,如果,a=0;j-)printf(“%d”,cj);/*,输出结果*,/,当前编程题：,11,级第六次作业,-,旋转魔方阵,(,文件,),4.,【,问题描述,】,输入一个自然数（,2N9,），要求输出如下的魔方阵，即边长为,N*N,，元素取值为,1,至,N*N,，,1,在左上角，呈顺时针方向依次放置各元素。,N=3,时：,1 2 3 8 9 4 7 6 5【,输入形式,】,从标准输入读取一个整数,N,。,【,输出形式,】,将结果输出到文件文件,file.out,。输出符合要求的方阵，每个数字占,5,个字符宽度，向右对齐，在每一行末均输出一个回车符。,【,输入样例,】4【,输出样例,】,输出文件,file.out,内容为：,1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7,本题解析：,模拟做法。因为是,n*n,的一个矩阵，所以我只需要不停地转圈赋值即可。这个看程序会比较清楚。,#include,int main(),freopen(file.out,w,stdout);,int n,i,j,k=1,x=1,y=1,s=1,t,tot;,int p1010;,scanf(%d,tot=n*n;t=n;,while(1),while(x=t)px+y=k+;/*go right*/,x-;k-;if(k=tot)break;/*,如果已经填充了,n*n,个了就退出循环*,/,while(y=s)px-y=k+;/*go left*/,x+;k-;,while(ys)pxy-=k+;/*go up*/,y+;k-;,s+;t-;/*,矩阵缩小一层*,/,if(k=tot)break;,for(i=1;i=n;i+),for(j=1;j=n;j+),printf(%5d,pji);,printf(n);,exit(0);,11,级第六次作业,-,全排列数的生成,5.,【,问题描述,】,输入整数,N(1=N=10),，生成从,1N,所有整数的全排列。,【,输入形式,】,输入整数,N,。,【,输出形式,】,输出有,N!,行，每行都是从,1N,所有整数的一个全排列，各整数之间以空格分隔。各行上的全排列不重复。输出各行遵循“小数优先”原则,在各全排列中，较小的数尽量靠前输出。如果将每行上的输出看成一个数字，则所有输出构成升序数列。,本题解析：,这道题如果做法太过暴力的话可能会超时。于是我们用一种半数学的方法。也就是说,n,的全排列按顺序排好的话，前,(n-1)!,个的第一位都是,1,，第二位就跟,(n-2)!,有关,那么我们就可以通过第,x,个直接判断从第一位到第,n,位应该是第几个数，如果遇到这个数已经被使用了的情况的话就将这个数,+1.,以此类推,#include,int main(),int i,j,k,n,s,f,p;,int jc11=1,1,2,6,24,120,720,5040,40320,362880,3628800;/*0-10,的阶乘*,/,int judge11;/*,用来判断,1-10,是否已经输出过*,/,scanf(%d,for(i=1;i=jcn;i+)/*n,的全排列共,n!,个*,/,s=i;,memset(judge,0,sizeof(judge);,for(j=0;jn;j+)/*n,的全排列共,n,位*,/,if(j!=0)printf();,p=(s-1)/jcn-1-j+1;/*p,表示这次输出的数应该是第几个没出现过的数*,/,for(k=1;k=p;k+),if(judgek)p+;/*,如果比,p,小的数中有的数出现过那么,p,就只能,+1*/,printf(%d,p);,judgep=1;,s=(s-1)%jcn-1-j+1;/*,去掉,(n-1)!,项*,/,/*,其实这个题的做法类似,Taylor,展开式，还是比较显然的*,/,printf(n);,return 0;,11,级第六次作业,-,单词排序（命令行参数）,6.,【,问题描述,】,编写一个程序，从一个文件中读入单词（即：以空格分隔的字符串），并对单词进行排序，删除重复出现的单词，然后将结果输出到另一个文件中。,【,输入形式,】,源文件名和目标文件名在执行时作为程序命令行参数输入，例如若程序名为,sort,，源文件名和目标文件名分别为,sort.in,和,sort.out,，则命令行为：,sort sort.in sort.out,。程序将从当前目录下,sort.in,文件中读入单词。,【,输出形式,】,对单词进行排序，删除重复出现的单词，然后将结果输出到文件,sort.out,中。,【,输入样例,】,假如,sort.in,文件内容如下：,rrr sss aaa bbb ccc ddf aaa dd【,输出样例,】sort.out,文件内容为：,aaa bbb ccc dd ddf rrr sss【,样例说明,】,读入文件,sort.in,，做适当的排序，并删除重复出现的单词，输出到文件,sort.out【,评分标准,】,对单词进行排序，删除重复出现的单词，符合此要求得,20,分，每个测试点,4,分，提交程序名为,sortwords.c,。,本题解析：,本题题目与前面很多题目都类似，题目本身并不难，主要是一个叫做“命令行参数”的东西。,命令行参数就是在,main,函数中定义参数,int main(int argc,char*argv),argc,表示参数的个数，,argv,即存储了各个参数 按题目要求的,test test.in test.out,argv0=“test”argv1=test.in argv2=“test.out”,#include,#include,int min(int a,int b),if(ab)return a;,else return b;,int judge(char a,char b)/*,判断,a,与,b,的大小关系*,/,int l1,l2,l,i;,l1=strlen(a);l2=strlen(b);l=min(l1,l2);,for(i=0;i=l;i+),if(aibi)return 1;,return 2;/*ab,返回,1,a=b,返回,2*/,int main(int argc,char*argv),freopen(argv1,r,stdin);,freopen(argv2,w,stdout);,char s100100;,char ch,t100;,int i=0,j,k=0;,scanf(%s,sk+);,while(ch=getchar()=),scanf(%s,sk+);,for(i=0;ik-1;i+),for(j=i;j=sj*/,strcpy(t,si);/*,字符串不能直接赋值，只能用这个函数，相当于,t=si*/,strcpy(si,sj);,strcpy(sj,t);,printf(%s,s0);,for(i=1;ik;i+),if(judge(si-1,si)!=2)/*,如果这个与之前的单词不相同*,/,printf(%s,si);,exit(0);,随着题目越来越难，,maybe,很多以前觉得,c,语言还能忍的同学已经不能忍了。不过。大家都是,6,系的同学。我们都讨厌,c,语言,c,语言就木有活路了。想要本次,ppt,电子版的同学加我,qq,吧。,JRC,：,631157428,加油,