ACM軟件大賽之編程大賽題目(附部分答案)

參考參考AC楸件大賽之編程大賽比賽注意事項：比賽時間為3小時（180分鐘）；比賽分兩個階段：第一階段限時 30分鐘，完成公示的3題，第二階段限時150分鐘（事先完成第一階段題目的小組可提前進入第二階段） ；比賽第一階段的3道題目將在前期宣傳中告知參賽選手， 比賽第二階段的題目將由賽事主席當場公布競賽題目；前兩階段題目分為三個分值（5分、10分、15分），第一階段3道公示題都為5分；第二階段總共15道題，根據(jù)不同的難度分值不同，分別為 5道5分題，5道10分題，5道15分題；第一階段參賽隊員不可參考任何相關資料；第二階段參賽隊員可以攜帶諸如書，手冊，程序清單等參考資料。 比賽過程中隊員不得攜帶任何電子媒質(zhì)的資料；參賽者可以選擇自己擅長的語言（C,C++,JAVA等等）進行編寫考慮到大一和大二學生的知識掌握程度，大一參加選手一開始就會有 10分的分數(shù)，最后總分是由所做題目及初始的 10分相加得到。每組隊員根據(jù)安排使用電腦， 小組人數(shù)為兩人的使用一臺電腦， 超過兩人的使用兩臺電腦，每臺的電腦配置完全相同；各小組每做完一題或幾題，必須交予評委老師運行，評委老師當場給分；如在比賽中發(fā)現(xiàn)作弊等行為，將取消比賽資格。第一階段公示題目：題目一：（5分）打印以下圖形，縱遵從字母順序，行字符數(shù)遵從斐波那契數(shù)列ABCCDDDEEEEEFFFFFFFFGGGGGGGGGGGGG#include<iostream>intf（intx）｛inta=1,b=0;intmax_=x;intsum=0;for(inti=0;i<max_;i++){sum=a+b;a=b;b=sum;}returnsum;}voidloop_print(intnum,charchr){for(inti=0;i<num;i++)std::cout<<chr;std::cout<<"\n";}intmain(){intline_max=7;charchr='A';for(intline=0;line<line_max;line++){loop_print(f(line+1),chr);chr++;}return0;}題目二：(5分)有個電子鐘，12點顯示為12:00(即12小時制)，那么請問一天24時間內(nèi)，出現(xiàn)連續(xù)3個相同數(shù)字的鐘點有幾個？#include<iostream>usingnamespacestd;boolcheck(inttime){inth=time/100;intm=time-100*h;returnh<=12&&m<=59&&h>0?true:false;//12小時制}intmain(){inttime=0;intj(0);// 總計數(shù)器while(time<1270){〃max12:59intt=time;intn[4];for(inti=0;i<4;i++){n[i]=t%10;t/=10;}if(n[1]==n[2]&&(n[0]==n[1]11n[3]==n[1])&&check(time)){〃cout<<n[3]<<n[2]<<":"<<n[1]<<n[0]<<"'n";//testj++；}time++;}cout<<"total:"<<j*2<<endl;}題目三：(5分)10進制的四位數(shù)中有幾個符合如下特征：將其分別表示為 16進制、10進制、12進制，在每種狀態(tài)下，分別將各個位上的數(shù)相加，能得到3個相等10進制數(shù)。例如299210進制：29922+9+9+2=2212進制：18941+8+9+4=2216進制：BB011+11+0=222992-2999#include<iostream>#include<cmath>usingnamespacestd;intconvert(intn,intc){floathigh_p=0;intsum=0;inta[4]={0,0,0,0};for(inti=0;;i++){floattestN=pow(c,(float)i);if(n>=testN)high_p=i;elsebreak;}for(inti=0;high_p!=-1;i++){a[i]=n/pow(c,high_p);n-=a[i]*pow(c,high_p);high_p--;}for(inti=0;i<4;i++){sum+=a[i];}returnsum;}intmain(){intj=0;for(inti=1000;i<=9999;i++){if((convert(i,16)==convert(i,10))&&(convert(i,10)==convert(i,12))){cout<<i<<endl;j++;}}cout<<j;return0;}第二階段題目：題目一：(5分)不引入臨時變量寫出 swap(a,b)功能voidswap(int&a,int&b){a+=b;b=a-b;a-=b;}題目二：(5分)she分別代表3個數(shù)字，已知：(he)A2=sheshe=?#include<iostream>intmain(){for(inthe=15;he<=96;he++)for(ints=1;s<=9;s++)if(he*he==100*s+he)std::cout<<he*he<<endl;return0;}題目三：(5分)有4條狗A、RCD,他們分另?J在一條100m的公路上步行，速率均為 5m/s,A初始在30m處，B初始在65m處，C初始在75m處，D初始在95m處，初始左右方向是隨意的，任意兩狗相遇則各自掉頭(掉頭時間不計，速率保持 5m/s)。請問，4條狗最終都離開公路的最大時間是幾秒？#include<iostream>intmain(){std::cout<<95/5;return0;}題目四：(5分)BigBang中的高級石頭剪刀布問題Scissors-PaperPaper-RockRock-ScissorsRock-LizardLizard-SpockSpock-ScissorsScissors-LizardLizard-PaperPaper-SpockSpock-Rock規(guī)則是左邊的手勢贏右邊的手勢，現(xiàn)有玩家P1、P2,輸入各自選擇的手勢，得出勝負。#include<iostream>#include<cmath>usingnamespacestd;intmain(){intp2,p1;cout<"1.Paper"<<endl<"2.Rock"<<endl<"3.Lizard"<<endl<"4.Spock"<<endl<<"5.Scissors"<<endl;cin>>p1>>p2;floatn=p1-p2;if(n*pow(-1,fabs(n))<0)// 此算法由@yaozizi提供cout<<"p2win";elseif(n==0)cout<<"duce";elsecout<<"p1win";return0;}題目五：(5分)游戲規(guī)則：21根火柴，每次取1-4根，誰取走最后一根判輸?，F(xiàn)在人和計算機博弈，設計一個程序保證計算機必勝， 要求每回合人與計算機各輸入 (或返回)一個代表取走火柴根數(shù)的數(shù)，直到游戲結(jié)束。#include<iostream>usingnamespacestd;intmain(){intn=21;intp,c;while(n!=0){cin>>p;while(p>4||p<=0||n-p<0){cout<<"err,inputagain"<<endl;cin>>p;}if(n!=0){if(n!=1)cout<<5-p<<endl;else{cout<<"PCwins";break;}if(n>=5)n-=5;}}}題目六：(10分)下列式子：2+3+4=91+2+3+4=10顯然右邊的數(shù)都能表示為 n(n>2)個連續(xù)自然數(shù)之和(1開始)，暫稱之為冏數(shù)但似乎23、32等數(shù)都不能寫成幾個數(shù)之和的形式，所以它們不是冏數(shù)這里有個可行的判斷方法為：上限為N,則測試1+2+31+2+3+41+2+3+4……+N2+3+42+3+4+??…+N(N-2)+(N-1)+N是否等于N這是一種可行但非常暴力的窮舉實際上冏數(shù)還是有一些規(guī)律可循的，請設計一個優(yōu)于之前提到的算法要求輸入一個數(shù)，并判斷它是否為冏數(shù)/*.如果一個數(shù)能被奇數(shù)(>=3)整除，則必能寫成X=平均數(shù)*中間數(shù)的形式，所以是冏數(shù).如果一個數(shù)是合數(shù)，如果其中有奇數(shù)因子，則回到1,為冏數(shù)；如果它是2的乘方，則不是冏數(shù)證明：它無法寫成奇數(shù)個相加， 因為除不盡奇數(shù)；也不能寫成偶數(shù)個相加， 中間數(shù)有兩個，和必為奇數(shù)，這個奇數(shù)必然是欲判斷數(shù)的一個因子3.如果一個數(shù)是素數(shù)，則必須是 6、10、14、18……個數(shù)相加得來，這樣才能得到奇數(shù)，根據(jù)高斯求和公式，這樣的和必有奇數(shù)因子綜上：只有2的乘方、素數(shù)、小于6的自然數(shù)，不是冏數(shù)*/#include<iostream>usingnamespacestd;boolcheck(longtar){boolflag=false;if(tar<6)flag=false;else{if(tar%2==0){// 偶數(shù)是否是2的階乘while(tar%2==0)tar/=2;tar==1?flag=false:flag=true;}else{// 奇數(shù)是否是素數(shù)doubleend=tar;for(inti=3;i<=sqrt(end);i+=2){if(tar%i==0){flag=true;break;}elsecontinue;}}}returnflag;}intmain(){inttar;cin>>tar;boolflag=check(tar);cout<<flag;return0;}題目七：(10分)現(xiàn)有一個固定的正方形區(qū)域，可以把它看作是一個數(shù)據(jù)庫中的特別的二維碼1110101001011011101100100其中每一位表示黑和白，假設這種二維碼容錯性只有 5%即只要有1位以上不符合要求就無法識別。現(xiàn)在輸入一個5*5的類似區(qū)域(相當于掃描一個二維碼) ，如果在容錯范圍內(nèi)，則認為它可識別。如果不是精確匹配，需輸出錯誤位的位置。#include<iostream>#include<cmath>usingnamespacestd;intmain(){interr=0,j=0;chara[26];charb[26]="1110101001011011101100100";for(inti=0;i<25;i++){cin>>a[i];if(a[i]!閩i]){j=i;err++;}}if(err==2)cout<<"fail";elseif(err==0)cout<<"matched";else{inty=(j+1)/5+1;intx=j%5+1;cout<<'('<<x<<','<<y<<')';}return0;}題目八：（10分）每個人每天早上都要思考一個問題， 這個問題的歷史已經(jīng)悠久得無法追溯， 那就是：今天午飯吃什么。現(xiàn)在有個膩歪的人，他已經(jīng)妥協(xié)于人工智能來解決日常問題，妄圖找出吃飯問題的通解已知：根據(jù)區(qū)域定位有以下地方可去：范圍1：a品嘗坊、b張三瘋、c南區(qū)食堂范圍2：d北區(qū)食堂、e咪哆范圍3:f大小姐的店根據(jù)遠近程度和價格因素，希望一周 5天去范圍1的幾率為20%去范圍2的幾率為70%去范圍3的幾率為10%（理論值）。請寫一段程序，隨機輸出15個字母（實際值），確定半個月的吃飯問題（不考慮跨平臺）注意：以上概率是指【如果】取輸出個數(shù)趨近于無窮時的概率， 而不是指15次*20%等式四舍五人得到的輸出結(jié)果。#include<iostream>#include<windows.h>〃linux/dev/random〃#include<ctime>usingnamespacestd;/*floatset_rand(){srand(time_t(time(NULL)));// 低精度取種，需循環(huán)輔助floatr=rand()%1000;returnr/10;〃.000-.999}*/floatSetRand(){LARGE_INTEGERStart;QueryPerformanceCounter(&Start);srand((long)Start.LowPart);//高精度取種longRndNum=rand()%1000;return(float)RndNum/1000;〃.000-.999}intmain(){for(inti=0;i<15;i++){if(SetRand()<=.2){if(SetRand()<=1/3)cout<<'a';elseif(SetRand()>2/3)cout<<'c';elsecout<<'b';}elseif(SetRand()>.9)cout<<'f;else{if(SetRand()<=.5)cout<<'d';elsecout<<'e';}}return0;}題目九：(10分)約瑟夫是一名猶太歷史學家。他在自己的日記中寫道，他和他朋友與 39個戰(zhàn)友(共41人)被羅馬軍隊包圍在洞中。他們討論是自殺還是被俘，最終決定自殺。自殺規(guī)則規(guī)定，所有人圍成一個圈，由一人開始報數(shù)，報到3的被殺死，下面的人繼續(xù)從 1報數(shù)，約瑟夫終和他的朋友活了下來。問：最初約瑟夫和他的朋友占據(jù)這個隊伍的位置各為第幾個？無腦窮舉，結(jié)果16、31#include<iostream>usingnamespacestd;intmain(){intj=0;ints=0;//jmp3intn[41];for(inti=0;i<41;i++)n[i]=1;for(inti=0;j<39;i++){if(i==41)i=0;s+=n[i];if(s==3){s=0;n[i]=0；j++；}}for(inti=0;i<41;i++)if(n[i]==1)cout<<i+1<<endl;return0;}題目十：(10分)設計一個算法，計算輸出 1至這個自然數(shù)間'1'共出現(xiàn)了幾次，如1-11間’1’出現(xiàn)了4次。假設數(shù)在int范圍內(nèi)，不考慮效率。(若算法效率足夠高可先至 14題)intcount(intn){inti=0;while(n!=0){i+=(n%10==1)?1:0;n/=10;}returni;}intf(intn){intc=0;for(inti=1;i<=n;i++){c+=count(i);}returnc;}題目H■:(15分)假設5*4的代表一個逆時針旋轉(zhuǎn)的字母區(qū)域， 輸入長寬，打印一個類似的字母區(qū)域， 乘積若超過26繼續(xù)由新一組的 A、B、C……填充，不要求車^出邊框，例如5*4的樣式如下：ABCDENOPQFMTSRGLKJIH#include<iostream>#include<cstring>#defineN100chara[N][N];intdirection[4][2]={{0,1},{1,0},{0,-1},{-1,0}};〃 左、右、下、上的順序intmain(){//freopen("in.txt","r",stdin);inti,j,n,m,next_i,next_j,x,ch,count;while(scanf("%d%d",&n,&m)!=EOF){i=j=next_i=next_j=x=ch=count=0;memset(a,'',sizeof(a));while(count<n*m){a[i][j]='A'+ch%26;next_i=i+direction[x][0];next_j=j+direction[x][1];if(a[next_i][next_j]!=''||next_i<0||next_i>=n||next_j<0||next_j>=m){x=(x+1)%4;〃 按順序向其他方向next_i=i+direction[x][0];next_j=j+direction[x][1];}ch++;count++;i=next_i;j=next_j;}for(i=0;i<n;i++){for(j=0;j<m;j++)printf("%4c",a[i][j]);printf("\n");}}return0;}題目十二：(15分)設計一個函數(shù)f($a,$b)，其中“$a,$b”代替一個無限循環(huán)小數(shù)， $a為固定部分，$b為循環(huán)體。要求輸出一個“x/y”的最簡分數(shù)表達這個有理數(shù)， 并測試-13.14(135)=-48623/3700#include<iostream>#include<cmath>usingnamespacestd;intcal(intx,inty){return(!y)?x:cal(y,x%y);}//輾轉(zhuǎn)相除voidf(floats,charloop口兒intsign=1;abs(s)==s?NULL:sign=-1;longn3=0;inti=0;for(;loop[i]!='\0';i++)n3=loop[i]-'0'+n3*10;〃char口tousignedlonglongm3=pow(10,(float)i)-1;s=abs(s);longn2=1,m2=1;floattemp=s;for(intj=0;;j++){longdj=(long)temp;if(temp==(long)dj)break;temp=s*pow(10,(float)j);m2=pow(10,(float)(j));}n2=temp;；longm1=m2*(m2*m3);longn1=n3*m2+n2*(m2*m3);longh=cal(m1,n1);m1/=h;n1/=h*sign;s*=sign;cout<<s<<"("<<loop<<"尸"<<n1<<"/"<<m1<<endl;}intmain(){f(-13.14,"135");return0;}題目十三：(15分)輸入4個坐標(前3個互不相同，且不共線)，判斷第4個點與前3個點所組成的三角形的位置關系(內(nèi)、外、上)。#include<iostream>#include<cmath>usingnamespacestd;structpoint{doublex,y;}；doublelen(pointA,pointB){returnsqrt(pow((A.x-B.x),2)+pow((A.y-B.y),2));}doublearea(pointA,pointB,pointC){// 海倫公式1/2*abs((A.x*B.y+B.x*C.y+C.x*A.y)-(A.x*C.y+B.x+A.y+C.x*B.y));//vectordoublea=len(B,C);doubleb=len(C,A);doublec=len(A,B);doublep=.5*(a+b+c);returnsqrt((p-a)*(p-b)*(p-c)*p);}intflag(pointA,pointB,pointC,pointD){doubleABC=area(A,B,C);doubleABD=area(A,B,D);doubleACD=area(A,C,D);doubleBCD=area(B,C,D);cout<<endl<<ABD+ACD+BCD-ABC<<endl;returnabs(ABD+ACD+BCD-ABC)>=1E-5?-1:(ABD||ACD||BCD?1:0);/*相加與ABC不等在ABC外，返回-1此處表示ABD+ACD+BCDABC吳差超過10人