ACM第三次培训题目及答案.doc

资源描述

2075 A|B? Problem Description 正整数A是否能被正整数B整除，不知道为什么xhd会研究这个问题，来帮帮他吧。 Input 输入数据的第一行是一个数据T，表示有T组数据。每组数据有两个正整数A和B(A,B<10^9)。 Output 对于每组输入数据，输出"YES"表示可以被整除，"NO"表示不能被整除。 Sample Input 2 4 2 5 3 Sample Output YES NO Author xhd Source ACM程序设计期末考试_热身赛(感谢 xhd & 8600) Recommend lcy 2014 青年歌手大奖赛_评委会打分 Problem Description 青年歌手大奖赛中，评委会给参赛选手打分。选手得分规则为去掉一个最高分和一个最低分，然后计算平均得分，请编程输出某选手的得分。 Input 输入数据有多组，每组占一行，每行的第一个数是n(2<n<100)，表示评委的人数，然后是n个评委的打分。 Output 对于每组输入数据，输出选手的得分，结果保留2位小数，每组输出占一行。 Sample Input 3 99 98 97 4 100 99 98 97 Sample Output 98.00 98.50 Author lcy Source C语言程序设计练习（三） Recommend lcy 2008 数值统计 Problem Description 统计给定的n个数中，负数、零和正数的个数。 Input 输入数据有多组，每组占一行，每行的第一个数是整数n（n<100），表示需要统计的数值的个数，然后是n个实数；如果n=0，则表示输入结束，该行不做处理。 Output 对于每组输入数据，输出一行a,b和c，分别表示给定的数据中负数、零和正数的个数。 Sample Input 6 0 1 2 3 -1 0 5 1 2 3 4 0.5 0 Sample Output 1 2 3 0 0 5 Author lcy Source C语言程序设计练习（二） Recommend JGShining 2017 字符串统计 Problem Description 对于给定的一个字符串，统计其中数字字符出现的次数。 Input 输入数据有多行，第一行是一个整数n，表示测试实例的个数，后面跟着n行，每行包括一个由字母和数字组成的字符串。 Output 对于每个测试实例，输出该串中数值的个数，每个输出占一行。 Sample Input 2 asdfasdf123123asdfasdf asdf111111111asdfasdfasdf Sample Output 6 9 Author lcy Source C语言程序设计练习（三） Recommend lcy 2020 绝对值排序 Problem Description 输入n(n<=100)个整数，按照绝对值从大到小排序后输出。题目保证对于每一个测试实例，所有的数的绝对值都不相等。 Input 输入数据有多组，每组占一行，每行的第一个数字为n,接着是n个整数，n=0表示输入数据的结束，不做处理。 Output 对于每个测试实例，输出排序后的结果，两个数之间用一个空格隔开。每个测试实例占一行。 Sample Input 3 3 -4 2 4 0 1 2 -3 0 Sample Output -4 3 2 -3 2 1 0 Author lcy Source C语言程序设计练习（三） Recommend lcy 2006 求奇数的乘积 Problem Description 给你n个整数，求他们中所有奇数的乘积。 Input 输入数据包含多个测试实例，每个测试实例占一行，每行的第一个数为n，表示本组数据一共有n个，接着是n个整数，你可以假设每组数据必定至少存在一个奇数。 Output 输出每组数中的所有奇数的乘积，对于测试实例，输出一行。 Sample Input 3 1 2 3 4 2 3 4 5 Sample Output 3 15 Author lcy Source C语言程序设计练习（一） Recommend JGShining 2005 第几天？ Problem Description 给定一个日期，输出这个日期是该年的第几天。 Input 输入数据有多组，每组占一行，数据格式为YYYY/MM/DD组成，具体参见sample input ,另外，可以向你确保所有的输入数据是合法的。 Output 对于每组输入数据，输出一行，表示该日期是该年的第几天。 Sample Input 1985/1/20 2006/3/12 Sample Output 20 71 Author lcy Source C语言程序设计练习（一） Recommend JGShining 2015 偶数求和 Problem Description 有一个长度为n(n<=100)的数列，该数列定义为从2开始的递增有序偶数，现在要求你按照顺序每m个数求出一个平均值，如果最后不足m个，则以实际数量求平均值。编程输出该平均值序列 Input 输入数据有多组，每组占一行，包含两个正整数n和m，n和m的含义如上所述。 Output 对于每组输入数据，输出一个平均值序列，每组输出占一行。 Sample Input 3 2 4 2 Sample Output 3 6 3 7 Author lcy Source C语言程序设计练习（三） Recommend lcy 2015问题分析 Problem Analyse 本题是为C语言初学者提供的。 Algorithm Analyse 解决这个问题，关键是要解决给出一个偶数X，求出从它开始连续的m个偶数的和而这个问题只要用等差数列求和公式就可以了。编码建议 Programing 从题目中可以看出，当这一组的第一个数是X时，下一组的第一个数就是X+2*m 而从X开始连续m个偶数的和就是: {X + [X + 2×(m - 1)]} × m / 2 = (X + m - 1) × m; 所以平均数就是X + m - 1 #include <stdio.h> int main(void) { int i, n, m, b, c; while (scanf("%d%d", &n, &m) != EOF) { b = 2; c = 0; for (i = 0 ; i < n / m ; i++) { printf(c++ ? " %d" : "%d", b + m - 1); b += m * 2; } printf(n % m ? " %d\n" : "\n", b + n % m - 1); } return 0; } 2017问题分析 Problem Analyse 本题是为C语言初学者提供的。 Algorithm Analyse 因为本题只要求输出每一行数字的个数。所以不需要把那些字符记录下来。因此不需要开个字符数组去记录。而且如果你想开也不知道该开多大，因为题目中没有提示一行最多有几个。而判断行末就判断是否为'\n'就可以。编码建议 Programing 判断是否为数字，直接调用库函数isdigit(); 语法: #include <ctype.h> int isdigit( int ch ); 功能：如果参数是0到9之间的数字字符，函数返回非零值，否则返回零值. #include <ctype.h> #include <stdio.h> int main(void) { int n, d; char c; scanf("%d%*c", &n); while (n--) { for (d = 0 ; (c = getchar()) != '\n' ;) { if (isdigit(c)) d++; } printf("%d\n", d); } return 0; } 2020问题分析 Problem Analyse 本题是为C语言初学者提供的。 Algorithm Analyse 这题的考点就是排序。对初学者来说，比较熟悉的排序是“冒泡排序”和“选择排序”。在排升序的时候，元素比较用'<'，降序用'>'。对于整数等基本数据类型，这样的比较符号很容易理解。但换了其他比较规则，你是不是还能很好地理解呢？呵呵。就像本题的规则：比较数的绝对值的大小，在这里-3 > 1，所以就不能直接用'>'，而是要自己制定一套大小规则。刚开始可能不习惯看到 -3 > 1这样的规则，熟悉后就好了。编码建议 Programing 你可以自己写一个判断大小的函数int cmp(a, b) 如果a > b返回大于0的值，a = b 返回0，a < b 返回小于0的值 ANSI C里的qsort()就是这样做的。用一个比较函数来提高排序函数的通用性。这里的比较规则就是return abs(*b) - abs(*a); #include <math.h> #include <stdio.h> #include <stdlib.h> int cmp(const int *a, const int *b) { return abs(*b) - abs(*a); } int main(void) { int n, i, x[101]; while (scanf("%d", &n), n) { for (i = 0 ; i < n ; i++) scanf("%d", x + i); qsort(x, n, sizeof(int), cmp); for (i = 0 ; i < n ; i++) printf("%d%c", x[i], (i != n - 1 ? ' ' : '\n')); } return 0; } 2014问题分析 Problem Analyse 本题是为C语言初学者提供的。 Algorithm Analyse 要实现的算法是:求整个数组的和、在数组中找最值。找最值，可以先把第一个元素赋给max、min变量，做一次遍历，一一比较，把最大值存入max，最小值存入min。也可以直接对数组进行排序，然后从第二个加到倒数第二个，这样就可以了，省去减两个最值。编码建议 Programing 我的代码采用的是第一种方法。因为对于本题来说，它的效率是O(N)。算法不难，可以直接看代码这里稍微讨论一下第二种方法。对于排序，我们可以直接调用库函数qsort(); 语法: #include <stdlib.h> void qsort( void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) ); 功能：对buf 指向的数据(包含num 项,每项的大小为size)进行快速排序。如果函数compare 的第一个参数小于第二个参数，返回负值；如果等于返回零值；如果大于返回正值。函数对buf 指向的数据按升序排序。 #include #include int cmp(const double *a, const double *b) { return *a > *b ? 1 : *a < *b ? -1 : 0; } int main(void) { int n, i; double x, y[100]; while (scanf("%d", &n) != EOF) { for (i = 0 ; i < n ; i++) scanf("%lf", y + i); qsort(y, n, sizeof(double), cmp); for (x = 0, i = 1 ; i < n - 1 ; i++) x += y[i]; printf("%.2f\n", x / (n - 2)); } return 0; } 你可能有疑问，为什么cmp函数不直接用return *a - *b; 这也就是我不打算用这种方法的原因了(虽然上面的代码可以Accpted)，这就是这段代码的不稳定因素。我们来做个实验： #include #include int main(void) { int i; double x; x = 0.123456; printf("%lf\n", x); for (i = 0 ; x - floor(x); i++) x *= 10; printf("%d\n", i); return 0; } 上面的代码的作用就是确定X小数点后有几位。我相信所有人都知道它有6位小数。但它的运行结果却是17(因编译器而异)。你可以自己复制代码去验证一下。我们在循环体里插入printf("%lf\n", floor(x));看看它的变化是怎样的。运行结果: 1.000000 12.000000 123.000000 1234.000000 12345.000000 123455.000000 1234559.000000 12345599.000000 123455999.000000 1234559999.000000 12345599999.000000 123455999999.000000 1234559999999.000000 12345599999999.000000 123455999999999.000000 1234559999999999.000000 12345599999999998.000000 这就是double型数据的精度问题。这是我们无法人为地控制的。所以建议尽量避免double的高精度运算。 #include <stdio.h> int main(void) { int n, i; double min, max; double x, y; while (scanf("%d", &n) != EOF) { scanf("%lf", &x); min = max = x; for (i = 1 ; i < n ; i++) { scanf("%lf", &y); x += y; if (y > max) max = y; if (y < min) min = y; } printf("%.2lf\n", (x - min - max) / (n - 2)); } return 0; } 2006问题分析 Problem Analyse 本题是为C语言初学者提供的。前置知识:循环语句 Algorithm Analyse 循环+条件判断编码建议 Programing 循环用for实现就可以了。至于那个判断条件，一般是if (t % 2 == 1)。但也可以简化为 if (t % 2) After Class 课外资料:在早期CPU处理的功能还不够强的时候，求X对于2^n的余数，可能不直接用%来运算。而是换成位运算。 X & (2^N - 1)。比如求 N 余 8，写成 n & 7。这样写可读性比较差。而且现在的机器性能提升了，一般的编译器也能自动转换这种优化。所以这种写法现在不推荐。仅做了解(当然如果你想炫耀一番自己的才华，那另当别论)。 #include <stdio.h> int main(void) { int n, i, s, t; while (scanf("%d", &n) != EOF) { for (s = 1, i = 0 ; i < n ; i++) { scanf("%d", &t); if (t & 1) s *= t; } printf("%d\n", s); } return 0; } 2008问题分析 Problem Analyse 本题是为C语言初学者提供的。前置知识:if嵌套语法 Algorithm Analyse 算法与2004题雷同，但要注意这里上以0作为结束符，而不是EOF #include <stdio.h> int main(void) { int n, i, a, b, c; double x; while (scanf("%d", &n) , n) { a = b = c = 0; for (i = 0 ; i < n ; i++) { scanf("%lf", &x); if (x > 0) c++; else if (x < 0) a++; else b++; } printf("%d %d %d\n", a, b, c); } return 0; } 2075问题分析 Problem Analyse 简单题 Algorithm Analyse 差不多是考你基本输入输出了。我也不明白他们为什么研究这个问题。 #include<stdio.h> int main(void) { int n, a, b; scanf("%d", &n); while(n-- && scanf("%d%d", &a, &b)) puts(a % b ? "NO" : "YES"); return 0; } 2005问题分析 Problem Analyse 本题是为C语言初学者提供的。前置知识:基本历法知识 Algorithm Analyse 判断N是否为闰年的方法是：N能4整数但不能被100整除或者 N能被400整除算出第N年的每个月的天数后就从一月开始累加，不要忘了最后要加天数哦。^_^ 编码建议 Programing 把判断闰年的算法写成一个宏： #define lev(n) (n % 4 == 0 && (n % 100 != 0 || n % 400 == 0)) 是闰年返回1，否则返回0。再开一个二维数组来保存闰年和非闰年每个月的天数。这样做可以减少编码的复杂度。当然，对于这样的简单题能通过的就是好代码。 #include <math.h> #include <stdio.h> #define lev(n) (n % 4 == 0 && (n % 100 != 0 || n % 400 == 0)) int main(void) { int y, m, d, i, s; int month[2][13] = { {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} }; while (scanf("%d/%d/%d", &y, &m, &d) != EOF) { for (s = 0, i = 1 ; i < m ; i++) s += month[lev(y)][i]; s += d; printf("%d\n", s); } return 0; }

展开阅读全文