算法竞赛入门经典各章(第二版)前4章课后习题答案

《算法竞赛入门经典各章(第二版)前4章课后习题答案》由会员分享，可在线阅读，更多相关《算法竞赛入门经典各章(第二版)前4章课后习题答案（27页珍藏版）》请在装配图网上搜索。

1、第一章#includeintmain()inta,b,c;doubled;scanf(,%d%d%d,&a,&b,&c);d=(double)(a+b+c);printf(”3lfn，d/3O);return0;习题42#includeintmain()intf;doublec;scanf(%d,&f);c=5*(f-32)/9;printf(”3lfn蔦c);return0;习题1-3#includeintmain()intn;scanf(%d,&n);printf(”dn“,(n*(l+n)/2);return0;习题#include#inelude#definepi4.0*atan(1.

2、0)intmain()intn;scanf(“d,&n);printf(%lfn,/sin(pi*n)A80);printf(,%lfn,I/cos(pi*n)/180);return0;习题1-5#includeintmain()doublexl,yl/x2/y2,a;scanf(吆If%lf%lf%lf,/&xl/&yl/&x2/&y2);a=sqrt(xl-x2)*(xl-x2)+(yl-y2)*(yl-y2);printf(%lfn,a);return0;习题1-6#includeintmain()intn;scanf(“d,&n);if(n%2=0)printf(,YESnH)；el

3、seprintf(”NOnJ;return0;习题z#includeintmain()intn;doublea;scanf(%d“,&n);a=n*95.0;if(a300)printf(%2lfn舄a);elseprintf(,%.2lfnla*0.85);return0;习题#include#ineludeintmain()doublen;scanf(“lf“,&n);printf(%.2lf,fabs(n);return0;习题1-9#includeintmain()inta,bzc;scanf(,l%d%d%d,&a,&b/&c);if(a=b&b=c)printfCnoXn)；if(

4、a*a+b*b=c*c)|(a*a+c*c=b*b)|(b*b+c*c=a*a)printf(,yesn,1)；elseprintf(,nonM)；return0;习题1-10#includeintmain()intn;scanf(%d,&n);if(n%4=0)if(n%100!=0)printf(non)；elseif(n%400=0)printf(yesn)；elseprintf(non);elseprintf(non);return0;第二章习题2-1#includeintmain()intn,count=O;scanf(%d“,&n);while(n0)count+;n=n/10;p

5、rintf(%dn1count);return0;习题2-2#includeintmain()inta,bzc;for(inti=100;i=999;i+)a=i%10;b=i/10%10;c=i/100;讦(i=a*a*a+b*b*b+c*c*c)printf(,%dn,/i);return0;习题2-3#includeintmain()intabcjkase=l;while(scanf(%d%d%cf：&a,&b，&c)for(i=10;i=100;i+)if(i%3=a&i%5=b&i%7=c)printf(HCase%d:%dn/kase+,i);elseif(i=100)printf

6、(HCase%d:Noanswern；kase+);return0;习题2-4#includeintmain()intn;while(scanf(%d“,&n)for(inti二n;i=0;i-)for(intj=n-i;j0;j-)printff“);for(intj=2*i-l;j0;j-)printfC#);printfCV);习题2-5文件题，南邮竞赛基本不涉及。习题2-6includeintmain()inti,n;doublesum=1.0;scanf(%d“,&n);for(i=2;i二n;i+)sum+=(1.0/i);printf(”3lfn蔦sum);return0;习题2

7、-7#include#includeintmain()intt=-l;doublea=1.0,sum=1.0;while(fabs=0.000001)a=1.0/(a+2);a=a*t;sum=sum+a;t=t*(-l);printf(,%.9lfn,/sum);return0;习题2-8#includeintmain()intn,m，temp,kase=0;while(zvscanf(,%d%d,/&n/&m)doubles=0;if(nm)temp=n;n二m;m=temp;if(n=0&m=0)break;for(inti=n;i=m;i+)s+=1.0/i/i;printffCase

8、%d:%.5fn,/+kase,s);return0;习题2-9printf的特殊用法:对于m.n的格式可以用如下方法表示charch20;printf(M%*.*snH,m,n,ch);前边的*定义的是总的宽度，后边的定义的是输出的个数。分別对应外而的参数m和n。这种方法的好处是可以在语句之外对参数m和n赋值，从而控制输出格式。#includeintmainOinta,b,c;scanf(，z%d%d%dz&a,&b,&c);printfC%c,(double)a/b);return0;习题2-10#include#defineFOR(i)for(i=l;i10;i+)intmain()in

9、ta,b,c,d,e,f,g,h,i;FOR(a)FOR(b)FOR(c)FOR(d)FOR(e)FOR(f)FOR(g)FOR(h)FOR(i)if(2*(a*100+b*10+c)=(d*100+e*10+f)&3*(a*100+b*10+c)=(g*100+h*10+i)if(a=b)&(a!=c)&(a!=d)&(a!=e)&(a!=f)&(a!弋)&(a!=h)&(a!=i)&(b!=c)&(b!=d)&(b!=e)&(b!=f)&(b!=g)&(b!=h)&(b!=i)&(c!=d)&(c!=d)&(c!=e)&(c!=f)&(c!=g)&(c!=h)&(chi)&(d!=e)&(

10、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(%dn%dn%dn/a*100+b*10+czd*100+e*10+f,g*100+h*10+i);第三章习题3-1#include#includeintmain()intnum80;charstr81;intt;scanfC%cf：&t);while(t-)intsum=O;scanf(,%s,/str);str0=,0,?num0=l:num0=0;for(inti=l;istrlen(

11、str);i+)stri=,O?numi=numi-l+l:numi=0;sum+二numi;printf(%drT：sum+numO);#include#include#includedoubleM(charx)if(x=,C,)return12.01;if(x=H)return1.00&if(x=O,)return16.00;if(x=N)return14.01;intmain()charstr100;intN,i,j;doublesum;scanf(T&N);while(N-)scanf(,%s,/str);sum=0;for(i=0;istrlen(str);i+)if(isalpha

12、(stri)if(stri+l=,ll)if(stri+2=,ll)sum=sum+M(stri)*(stri+l-,0,)*10+stri+2j-,0,);i=i+2;elsesum=sum+M(stri)*(stri+l-lO,)；i+；elsesum+=M(stri);prirrtf(%3lfn蔦sum);习题33#include#includechars1000000;inta10000;intmainOwhile(scanfs)intb10=;for(inti=0;i10000;i+)bsi-oH+；for(inti=0;i9;i+)printfC%d,bi);printfb9);r

13、eturn0;习题3-4#include#includechars85J;intmainOwhileCscanf(%s,s)intlen=strlen(s);for(inti=l:i=len;+i)if(len%i=0)intk;for(k=l;k=len;卄1)if(sk!=sk%il)break;if(k=len)printf(z/%dnz，,i);break;习题3-5#include#includeconstintLEN=5;constintMAX二100;constinty=0,0,1,-1;constintx二T,1,0,0;charmapLEXLEN;inttraEllO;boo

14、llegal(intpos)return0=pos&posLEN;voidPmap()for(intcow=0;cowLEN;cow+)printf(/z%c/z,mapcow：0);for(intcol=l;coKLEN:col+)printfCmapcowcol);printf(n);intmainOtrafA二0;traB=l;traR二2;traL二3;boolfirst=true;intCase=0;intbx,by;while(gets(map0)if(map00=Z)break;for(intcol=l;coKLEN:col+)gets(mapEcol);for(inti=0;i

15、LEN;i+)for(intj=0;jintx,y;intr,c;strlll;intmainOintr,c;while(scanf&r,&c),r,c)for(inti=0;ir;i+)scanfmapi);intnum二0;for(inti=0;ir;i+)for(intj二O;jc;j+)if(ma,pij!二*)strnumy二j;strnumx=i;strnumr=l;num+;elsestrnumr=0;if(mapi-lj=*T|i-l0)strnumx二i;strnumy=j;strnumc=l;num+;elsestrnumc二0;辻(first)first=0;elsepr

16、intf(，zn，z);printf(Across:n);for(inti=0;inum;i+)if(stri.r)for(intj=strZiZ.y;jc;j+)if(mapLstri.xj=*)break;printfmapstri.xj);printf(n);printf(Down：n);for(inti二0;inum;i+)if(stri.c)for(intj=strZiZ.x;jr;j+)if(mapjstri.y=*)break;printfmapjstri.y);printf(n);习题3-7#include#includeconstintN=1005;constintM=105

17、;intfirst=l;intn,m,cntM;chardnaJAN;voidinit0scanf&m,&n);for(inti=0;im;i+)scanf(%s,dnai);voidsolve0intans=0;if(first)first=0;elseprintfCn，z);for(inti=0;in;i+)intMax=0,id;memset(ent,0,sizeof(ent);for(intj=0;jMax)Max=enttmp.;id=tmp;elseif(enttmp.=Max&tmpid)id=tmp;ans+=m-Max;printfid);printf(n%d,ans);in

18、tmainOintcas:scanf&cas);while(cas-)init0;solve0;return0;习题3-8#include#includeusingnamespacestd;constintN=3005;intaN,vN;intmainOintn,m,ent;while(scanf&n,&m)ent二0;memset(v,0,sizeof(v);printfCz%d/%d=%d,n,m,n/m);n=n%m;while(!v.nJ)a+cnt：二(n*10)/m;vn=cnt;n二n*10%m;for(inti=l:i=cnt&i51;+i)if(i=vn)printf();p

19、rintfai);if(i=50)printf()；printfOn%d=numberofdigitsinrepeatingcyclenn,ent-vn+l)；return0;#include#includecstring#includecstdio#defineSIZE1100000usingnamespacestd;charsubSIZE：,baseSIZE;intmainOwhile(scanfCz%s%s/，,base,sub)!=EOF)intlen=strlen(sub);intbase_len=strlen(base);intj=0;if(lenbase_len)printf(N

20、on);continue;for(inti=0;i=len)break;if(j=len)printf(Yesn);elseprintf(Non);return0;习题3-10#includeiostream#includecstdio#includecstring#includeusingnamespacestd;structnodeinth,w;booloperator(constnode&r)constreturnhr0.w)swap(r0h,r0.w);for(inti=l;iri.hri.w;辻(ri.hri.w)swap(rijh,riw);returntrue;returnfal

21、se;boolIs_box()if(rEO.h!二:rlhr0w!=r.1w)returnfalse:if(r2j.h!=r3.hr2.w!=r3.w)returnfalse:if(rE4h!=r5hr4w!=r15w)returnfalse:if(rEOZh!=:r2h)returnfalse:if(rEO.w!=:r4h)returnfalse:if(r2w!=r4.w)returnfalse;returntrue;intmainO/freopenClSS?txt,工、stdin);while(read()sort(r,r+6);if(Is.box0)coutPOSSIBLEendl;el

22、secoutIMPOSSIBLE，zendl:return0;voidsolve0intans=0;voidsolve0intans=0;voidsolve0intans=0;voidsolve0intans=0;#include#includeconstintN=1005;constintM=105;intfirst=l;intn,m,cntM;chardnaMN;voidinit0scanf(/z%d%d/z,&m,&n);for(inti=0;im;i+)scanfdnai);if(first)first=O;习题3-12includeincludeconstintN=1005;cons

23、tintM=105;intfirst=l;intn,m,cntM;chardnaMN;voidinit0scanf(/z%d%d/z,&m,&n);for(inti=0;im;i+)scanfdnai);voidsolve0intans=0;if(first)first=0;习题includeincludeconstintN=1005;constintM=105;intfirst=l;intn,m,cntM;chardnaMN;voidinit0scanf(/z%d%d/z,&m,&n);for(inti=0;im;i+)scanfdnai);辻(first)first=O;习题4-2#inc

24、lude#includeconstintN二1005;constintM二105;intfirst=l:intn,m,cntM;chardnaMN;voidinit0scanf&m,&n);for(inti=0;im;i+)sc&nf(%s,dnai):voidsolve0intans二0;if(first)first=0;习题4-3#include#includeconstintN二1005;constintM二105;intfirst=l;intn,m,cntM;chardnaMN;voidinit0scanf&n);for(inti=0;im;i+)scanf(%s,dnai);if(f

25、irst)first二0;习题4-4includeincludeconstintN=1005;constintM=105;intfirst=l;intn,m,entM:chardnaMN;voidinit0scanf&m,&n);for(inti=0;im;i+)scanf(%s,voidsolve0intans二0;if(first)first二0;习题4-5includeincludeconstintN=1005;constintM二105;intfirst=l;intn,m,cntM;chardnaMN;voidinit0scanf&m,&n);for(inti=0;im;i+)scan

26、fdnai);dnai);if(first)first=O;习题牛6include#includeconstintN二1005;constintM二105;intfirst=l:intn,m,entEM:chardnaMN;voidinit0scanf&m,&n);for(inti=0;im;i+)scanf(%s,voidsolve0intans二0;if(first)first二0;习题4-7includeincludeconstintN=1005;constintM二105;intfirst=l;intn,m,entM;chardnaMN;voidinit0scanf&m,&n);dna

27、Ei);dnai);for(inti=0;im;i+)scanf(s,if(first)first二0;习题4-8includeincludeconstintN=1005;constintM=105;intfirst=l;intn,m,entEM:chardnaMN;voidinit0scanf&m,&n);for(inti=0;im;i+)scanf(%s,voidsolve0intans二0;if(first)first二0;习题4-8includeincludeconstintN=1005;constintM二105;intfirst=l;intn,m,cntM;chardnaMN;voidinit0scanf&m,&n);dnai);dnai);for(inti=0;im;i+)scanf(%s,voidsolve0intans=0;if(first)first=O;习题49includeincludeconstintN=1005;constintM=105;intfirst=l;intn,m,cntM;chardnaJAN;voidinit0scanf&m,&n);for(inti=0;im;i+)scanf(”%s,dnai);voidsolve0intans=0;if(first)first=0;