【算法竞赛入门经典】【第三章】课后习题(第一部分)

课后习题第三波来了,,到第三章之后代码之类的稍微变长了一些,所以我把这一章的答案分为几部分。这一章重点是字符串的处理,对于字符串问题,通常只要细心就没有问题了,下面不多说了直接上详解。

习题3-1 分数统计(stat)

任务1:这个比较简单就直接上代码了:

#include <stdlib.h>#include <stdio.h> #include <string.h> #define MAXN 100 + 10int cmp(const void*a,const void*b){return *(int*)a – *(int*)b;}int main() {int i,j,n,max,p;int Stu[MAXN],a[MAXN]; memset(a,0,sizeof(a));scanf("%d",&n);for(i = 0; i < n; i++){scanf("%d",&p);a[p]++;}max=a[0];for( i = 1; i < MAXN; i++){if(a[i]>=max){max=a[i];}}for( i = 0, j = 0; i < MAXN; i++){if(a[i]==max){Stu[j++] = i;}}qsort(Stu,j,sizeof(Stu[0]),cmp);for( i = 0; i < j; i++){if(i) printf(" ");printf("%d",Stu[i]);}printf("\n");return 0;}

任务2:这个相对任务1难度就加大许多了,其中这一题,在使用 qsort 函数时还有一个小细节要注意,就是在return 时,对于double型的要使用 三元运算符,如果按照之前的处理方法会造成错误,错误来自于浮点数的误差。这一题我的处理方法与第一题类似,但是要与第一题整数类似,就必须做出一点牺牲,然而我牺牲了内存。代码如下:

#include <stdio.h> #include <string.h>#include <stdlib.h>#define MAXN 10000 + 100int cmp(const void*a,const void*b){return *(double*)a>*(double*)b?1:-1;}int main() {int i,j,a[MAXN],n,max,temp;double p,Stu[101];memset(a,0,sizeof(a));scanf("%d",&n);for(i = 0; i < n; i++){scanf("%lf",&p);temp = 100*p;a[temp]++;}max=a[0];for( i = 1; i < MAXN; i++){if(a[i] > max){max = a[i];}}for( i = 0, j = 0; i < MAXN; i++){if(a[i]==max){Stu[j++] = (double)i/100;}}qsort(Stu,j,sizeof(Stu[0]),cmp);for( i = 0; i < j; i++){if(i) printf(" ");printf("%.2lf",Stu[i]);}printf("\n");return 0;}

习题3-2 单词长度(word)

这一题比较简单,只需要注意 数单词 数的时候小心一些就好了

#include <stdio.h>#include <ctype.h>#define MAXN 10000 + 100char str[MAXN];int main(){int i,sum = 0,count = 0;//count用于记录空格数,sum用于记录字母的总数gets(str);if(str[0]!=' ')count = 1;for(i = 0; str[i]!='\0';i++){if(str[i]==' '&&isalpha(str[i+1]))count++;if(isalpha(str[i]))sum++;}printf("count = %d,sum = %d\n",count,sum);printf("%.2lf\n",1.0*sum/count);return 0;}

习题3-3 乘积的末三位(product)

这一题的分两步,第一步将含有大小写字母的字符串舍弃,第二部分将纯数字的字符串转化为数字进行运算。这样一来问题就清晰了,代码如下:

#include <stdio.h>#include <stdlib.h>#include <string.h>int isNum(char *a,int len){int i;for( i = 0; i < len; i++){if(a[i]<'0'||a[i]>'9')return 0;}return 1;}int main(){char str[20];int i,n,p,tmp;//n表示输入整数的个数,p表示那些整数乘积的后三位while(scanf("%d",&n) == 1){p = 1;for(i = 0; i < n; i++){scanf("%s",str);getchar();if(isNum(str,strlen(str))){tmp = atoi(str);p *= tmp;p %= 1000;}}printf("%03d\n",p);}return 0;}

对于【第三章】的其他习题,会在后面的文章继续

(如有错误,欢迎指正)

勇于接受自己的不完美,认清自己不足的地方,

【算法竞赛入门经典】【第三章】课后习题(第一部分)

相关文章:

你感兴趣的文章:

标签云: