算法竞赛入门经典1-3章习题答案.docx

第一章习题1-1#include int main()int a,b,c;double d;scanf(%d%d%d,&a,&b,&c);d=(double)(a+b+c);printf(%.3lfn,d/3.0);return 0;习题1-2#include int main()int f;double c;scanf(%d,&f);c=5.0*(f-32)/9;printf(%.3lfn,c);return 0;习题1-3#include int main()int n;scanf(%d,&n);printf(%dn,(n*(1+n)/2);return 0;习题1-4#include #include #define pi 4.0*atan(1.0)int main()int n;scanf(%d,&n);printf(%lfn,sin(pi*n)/180);printf(%lfn,cos(pi*n)/180);return 0;习题1-5#include #include int main()double x1,y1,x2,y2,a;scanf(%lf %lf %lf %lf,&x1,&y1,&x2,&y2);a=sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);printf(%lfn,a);return 0;习题1-6#include int main()int n;scanf(%d,&n);if(n%2=0)printf(yesn);elseprintf(non);return 0;习题1-7#include int main()int n;double a;scanf(%d,&n);a=n*95.0;if(a300)printf(%.2lfn,a);elseprintf(%.2lfn,a*0.85);return 0;习题1-8#include #include int main()double n;scanf(%lf,&n);printf(%.2lf,fabs(n);return 0;习题1-9#include int main()int a,b,c;scanf(%d%d%d,&a,&b,&c);if(a*a+b*b=c*c)|(a*a+c*c=b*b)|(b*b+c*c=a*a)printf(yesn);elseprintf(non);return 0;习题1-10#include int main()int n;scanf(%d,&n);if(n%4=0)if(n%100!=0)printf(yesn);elseif(n%400=0)printf(yesn);elseprintf(non);elseprintf(non);return 0;第二章习题2-1#include int main()int n,count=0;scanf(%d,&n);while(n0)count+;n=n/10;printf(%dn,count);return 0;习题2-2#include int main()int a,b,c;for(int i=100;i=999;i+)a=i%10;b=i/10%10;c=i/100;if(i=a*a*a+b*b*b+c*c*c)printf(%dn,i);return 0;习题2-3#include int main()int i,a,b,c;scanf(%d%d%d,&a,&b,&c);for(i=10;i=100;i+)if(i%3=a&i%5=b&i%7=c)printf(%dn,i);break;if (i=100)printf(no answern);return 0;习题2-4#include int main()int i,j,k,n;scanf(%d,&n);for(i=n;i0;i-)for(k=0;kn-i;k+)printf( );for(j=0;j2*i-1;j+)printf(#);printf(n);return 0;习题2-5文件题，南邮竞赛基本不涉及。习题2-6#include int main()int i,n;double sum=1.0;scanf(%d,&n);for(i=2;i=n;i+)sum+=(1.0/i);printf(%.3lfn,sum);return 0;习题2-7#include#includeint main() double sum = 0, a = 1.0; for(int i = 1; (1.0/i) (1e-6); +i) sum += a/(2*i-1); a *= -1; printf(%.8lf %.8lfn, sum, 4*sum); return 0;习题2-8#include int main()int i,n,m,temp;double sum=0;scanf(%d%d,&n,&m);if(nm)temp=n;n=m;m=temp;for(i=n;i=m;i+)sum=sum+(1.0/i/i);printf(%.5lfn,sum);return 0; 本题陷阱在于1/(n)2 + . ， 用1/(n*n)会溢出 ， 改为1/n/n就好。习题2-9printf的特殊用法:对于m.n的格式可以用如下方法表示 char ch20; printf(%*.*sn,m,n,ch); 前边的*定义的是总的宽度，后边的定义的是输出的个数。分别对应外面的参数m和n 。 这种方法的好处是可以在语句之外对参数m和n赋值，从而控制输出格式。 #include int main() int a,b,c;scanf(%d%d%d,&a,&b,&c);printf(%.*lfn,c,(double)a/b);return 0;习题2-10解法1：#include int main() int a,b,c,d,e,f,g,h,i;for(a=1;a=9;a+)for(b=1;b=9;b+)for(c=1;c=9;c+)for(d=1;d=9;d+)for(e=1;e=9;e+)for(f=1;f=9;f+)for(g=1;g=9;g+)for(h=1;h=9;h+)for(i=1;i=9;i+)if(2*(a*100+b*10+c)=1*(d*100+e*10+f)&(3*(a*100+b*10+c)=1*(g*100+h*10+i)&(a!=b)&(a!=c)&(a!=d)&(a!=e)&(a!=f)&(a!=g)&(a!=h)&(a!=i)&(b!=c)&(b!=d)&(b!=e)&(b!=f)&(b!=g)&(b!=h)&(b!=i)&(c!=d)&(c!=e)&(c!=f)&(c!=g)&(c!=h)&(c!=i)&(d!=e)&(d!=f)&(d!=g)&(d!=h)&(d!=i)&(e!=f)&(e!=g)&(e!=h)&(e!=i)&(f!=g)&(f!=h)&(f!=i)&(g!=h)&(g!=i)&(h!=i)printf(%d,%d,%dn,a*100+b*10+c,d*100+e*10+f,g*100+h*10+i);return 0;解法二：#include int main() int x, y, z, a10 = 0; for(x = 100; x 333; x+) y = 2*x; z = 3*x; /令a出现的数字 = 1 ax/100 = ax/10%10 = ax%10 = 1; ay/100 = ay/10%10 = ay%10 = 1; az/100 = az/10%10 = az%10 = 1; int i, s = 0; for(i = 1; i 10; i+) s += ai; if(s = 9) printf(%dt%dt%dn, x, y, z); for(i = 1; i 10; i+) /重新赋值为0 ai = 0; return 0; 第三章习题3-1 分数统计输入一些学生的分数，哪个分数出现的次数最多？如果有多个并列，从小到大输出。任务1：分数均为不超过100的非负整数任务2：分数均为不超过100的非负实数，但最多保留两位小数解法1：#includeusing namespace std;#define Max 10001 /定义数组最大长度为10001，可以在成绩为100时不超出边界int main()int scoreMax;double sMax;int n,time,count=0;double a;int c;double b;for(int i=0;iMax;i+)scorei=0;coutn;for(int j=0;ja;c=a*100;scorec+; time=score0;for(int j=1;jtime)time=scorej;b=j;cout出现最多次数的分数是：b/100 ; /*b中存放的数据即为出现次数最多分数中第一次出现的分数，time中存放的数据为该分数出现最大次数*/for(int j=0;jMax;j+)if(scorej=time&j!=b)scount+=j;for(int i=0;icount;i+)coutsi/100 ;return 0; /该程序虽然简单，但运算量极大，不适合数据及时性要求较高的系统解法2：#include #include int main()int i,a101,n,max;memset(a,sizeof(a),0); /将数组a全置为0 while(scanf(%d,&n)=1)an+; /通过对输入的n的记录，统计出输入次数，并存于数组a中 /*scanf函数返回的是成功输入的变量数目，当输入完毕后先按enter键，再按ctrl+z键，最后再按enter键，即可结束输入*/ max=a0;for(i=1;i=max)max=ai;for(i=0;i101;i+)if(ai=max)printf(%d ,i);printf(n);return 0;注：解法二仅适用于输入成绩为整数的情况解法三：#include #include #define MAXN 5000 int sMAXN,mMAXN2; int main() double x; int i=0,j=0,temp=0,length,min,max=0,last; while(scanf(%lf,&x) = 1) temp=x*1000; temp=temp%10; if (temp=5) si+=x*100+1; else si+=x*100; printf(n); length = i-1; for(i=0;i=i;j-) if (minsj) min=sj; sj=si; si=min; /将数组中的值按从小到大排序 for (i=0;i=length;i+) printf(%d ,si); printf(n); j=0; for(i=0;i0)&(slast=si) mj1+; if (maxmj1) max=mj1; else if (i!=0) j+; mj0=si; mj1=1; /将数组中的元素置于二维数组中，并记录相同元素个数，j中存放的是不同元素的个数 for(i=0;i=length;i+) if (mi1=max)printf(%.2lfn,mi0/100.0) ; return 0; 习题3-2 单词的长度输入若干个单词，输出它们的平均长度。单词只包含大写字母和小写字母，用一个或多个空格隔开解法1：#include #include /isalpha函数调用char s1000;int main()char ch;int i,j,m=0,sumlong=0,count=0;while(1)scanf(%c,&ch);if(ch=n|ch=EOF)break;elsesm+=ch;for(i=m-1;i0;i-)if(si= &si-1= )for(j=i-1;jm-1;j+)sj=sj+1;m-;/*若程序输入两个以上的空格，则删除多余的空格，只保留一个空格，并更改数组元素个数*/for(i=0;im;i+)if(isalpha(si)sumlong+;else if(si= )count+;printf(%.2lfn,(double)(sumlong+count+1)/(count+1);return 0;解法二：#include#include#include#define A 100000+10 /*假定用户输入字符的最多个数*/ int main() char aA; /*存储用户输入的字符数据*/ int y, tot=0, /*用户输入的字母的总数*/ word=0, /*单词的个数*/ i; gets(a); i=strlen(a); tot=i; for (y=0;y0 & isspace(ay-1) & !isspace(ay) /*如果数组中某个下标比0大的元素不为空格，且该元素的前一个元素是空格，则算是找到了一个单词*/ ) word=word+1; if (word=0) printf(没有输入任何单词”); else printf(单词的平均长度是%f,(tot*1.0)/word); return 0; 习题3-3 乘积的末3位输入若干个整数（可以是正数、负数或者零），输出它们的乘积的末三位。这些整数中会混入一些由大写字母组成的字符串，你的程序应当忽略它们。提示：试试看，在执行scanf（“%d”）时输入一个字符串会怎样？#include #include #include #define MAXN 5000 char aMAXN; int bMAXN; int main() int i,j=0,chuli=0,fuhao=1,kongge=0; long plus=1; fgets(a,sizeof(a),stdin); for (i=0;i=48)&(ai=57) chuli=1; if (chuli=1) if (ai=45) fuhao=(-1)*fuhao; else if(ai=32)|(ai=0) if (kongge=0) kongge=1; fuhao=1; j+; else kongge=0; bj=(ai-48)*fuhao+bj*10; printf(b%d=%dn,j,bj); if(ai=0) printf(EOF); for (i=0;i=j-1;i+) plus*=bi; printf(b%d=%d plus=%dn,i,bi,plus); printf(%03d,abs(plus%1000); return 0; 习题3-4 计算器编写程序，读入一行恰好包含一个加号、减号或乘号的表达式，输出它的值。这个运算符保证是二元运算符，且两个数均为不超过100的非负整数。运算数和运算符可以紧挨着，也可以用一个或多个空格、TAB隔开。行首末尾均可以有空格。提示：选择合适的输入方法可以将问题简化。样例输入：1+1样例输出：2样例输入：2- 5样例输出：-3样例输入：0 *1982样例输出：0#include #define MAXN 5000 int main() int a,b,c; char f; scanf(%d,&a); scanf(%c,&f); while(f!=+)&(f!=-)&(f!=*) scanf(%c,&f); scanf(%d,&b); if (f=+) c=a+b; else if(f=-) c=a-b; else c=a*b; printf(%d,c); return 0; 习题3-5 选择输入一个n*n的字符矩阵，把它左转90度后输出。解法一：#include char a10001000;int main()int i,j,n;scanf(%d,&n);scanf( );char temp;for(i=0;in;i+)for(j=0;jn;j+)scanf(%c,&aij);for(i=0;in;i+)for(j=i;j=0;i-)for(j=0;jn;j+)printf(%c ,aij);printf(n); return 0;解法二：#include #define MAXN 5000 char aMAXNMAXN; int main() int i=0,j=0,k,n; while(scanf(%c,&aij)=1) if (aij!=n) j+; else i+;j=0; printf(i=%d j=%dn,i,j); n=i;for (j=n-1;j=0;j-) for (i=0;i=n-1;i+) printf(%c,aij); printf(n); 习题3-6 进制转换1输入基数b(2=b=10)和正整数n（十进制），输出n的b进制表示。#include int main() int a10,b,i=0,j=0,n; scanf(%d %d, &b, &n); while(n0) ai=n%b; n=n/b; printf(%d %d n,n,ai); i+; for(j=i-1;j=0;j-) printf(%d,aj); return 0; 习题3-7 进制转换2输入基数b(2=b=10)和正整数n（b进制），输出n的十进制表示。#include in