ACM软件大赛之编程大赛题目附部分答案.docx
《ACM软件大赛之编程大赛题目附部分答案.docx》由会员分享,可在线阅读,更多相关《ACM软件大赛之编程大赛题目附部分答案.docx(23页珍藏版)》请在冰点文库上搜索。
ACM软件大赛之编程大赛题目附部分答案
ACM软件大赛之编程大赛
比赛注意事项:
●比赛时间为3小时(180分钟);比赛分两个阶段:
第一阶段限时30分钟,完成公示的3题,第二阶段限时150分钟(事先完成第一阶段题目的小组可提前进入第二阶段);
●比赛第一阶段的3道题目将在前期宣传中告知参赛选手,比赛第二阶段的题目将由赛事主席当场公布竞赛题目;
●前两阶段题目分为三个分值(5分、10分、15分),第一阶段3道公示题都为5分;第二阶段总共15道题,根据不同的难度分值不同,分别为5道5分题,5道10分题,5道15分题;第一阶段参赛队员不可参考任何相关资料;第二阶段参赛队员可以携带诸如书,手册,程序清单等参考资料。
比赛过程中队员不得携带任何电子媒质的资料;参赛者可以选择自己擅长的语言(C,C++,JAVA等等)进行编写
●考虑到大一和大二学生的知识掌握程度,大一参加选手一开始就会有10分的分数,最后总分是由所做题目与初始的10分相加得到。
●每组队员根据安排使用电脑,小组人数为两人的使用一台电脑,超过两人的使用两台电脑,每台的电脑配置完全一样;
●各小组每做完一题或几题,必须交予评委老师运行,评委老师当场给分;
●如在比赛中发现作弊等行为,将取消比赛资格。
第一阶段公示题目:
题目一:
(5分)
打印以下图形,纵遵从字母顺序,行字符数遵从斐波那契数列
A
B
CC
DDD
EEEEE
FFFFFFFF
GGGGGGGGGGGGG
#include
intf(intx){
inta=1,b=0;
intmax_=x;
intsum=0;
for(inti=0;isum=a+b;
a=b;
b=sum;
}
returnsum;
}
voidloop_print(intnum,charchr){
for(inti=0;istd:
:
cout<std:
:
cout<<"\n";
}
intmain(){
intline_max=7;
charchr='A';
for(intline=0;lineloop_print(f(line+1),chr);
chr++;
}
return0;
}
题目二:
(5分)
有个电子钟,12点显示为12:
00(即12小时制),那么请问一天24时间,出现连续3个一样数字的钟点有几个?
#include
usingnamespacestd;
boolcheck(inttime){
inth=time/100;
intm=time-100*h;
returnh<=12&&m<=59&&h>0?
true:
false;//12小时制
}
intmain(){
inttime=0;
intj(0);//总计数器
while(time<1270){//max12:
59
intt=time;
intn[4];
for(inti=0;i<4;i++){
n[i]=t%10;
t/=10;
}
if(n[1]==n[2]&&(n[0]==n[1]||n[3]==n[1])&&check(time)){
//cout<"<j++;
}
time++;
}
cout<<"total:
"<<}
题目三:
(5分)
10进制的四位数中有几个符合如下特征:
将其分别表示为16进制、10进制、12进制,在每种状态下,分别将各个位上的数相加,能得到3个相等10进制数。
例如2992
10进制:
29922+9+9+2=22
12进制:
18941+8+9+4=22
16进制:
BB011+11+0=22
2992-2999
#include
#include
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<
j++;
}
}
cout<return0;
}
第二阶段题目:
题目一:
(5分)
不引入临时变量写出swap(a,b)功能
voidswap(int&a,int&b){
a+=b;
b=a-b;
a-=b;
}
题目二:
(5分)
she分别代表3个数字,已知:
(he)^2=she
she=?
#include
intmain(){
for(inthe=15;he<=96;he++)
for(ints=1;s<=9;s++)
if(he*he==100*s+he)
std:
:
cout<return0;
}
题目三:
(5分)
有4条狗A、B、C、D,他们分别在一条100m的公路上步行,速率均为5m/s,A初始在30m处,B初始在65m处,C初始在75m处,D初始在95m处,初始左右方向是随意的,任意两狗相遇则各自掉头(掉头时间不计,速率保持5m/s)。
请问,4条狗最终都离开公路的最大时间是几秒?
#include
intmain(){
std:
:
cout<<95/5;
return0;
}
题目四:
(5分)
BigBang中的高级石头剪刀布问题
Scissors-Paper
Paper-Rock
Rock-Scissors
Rock-Lizard
Lizard-Spock
Spock-Scissors
Scissors-Lizard
Lizard-Paper
Paper-Spock
Spock-Rock
规则是左边的手势赢右边的手势,现有玩家P1、P2,输入各自选择的手势,得出胜负。
#include
#include
usingnamespacestd;
intmain()
{
intp2,p1;
cout
<<"1.Paper"<<<"2.Rock"<<<"3.Lizard"<<<"4.Spock"<<<"5.Scissors"<cin>>p1>>p2;
floatn=p1-p2;
if(n*pow(-1,fabs(n))<0)//此算法由yaozizi提供
cout<<"p2win";
elseif(n==0)
cout<<"duce";
else
cout<<"p1win";
return0;
}
题目五:
(5分)
游戏规则:
21根火柴,每次取1-4根,谁取走最后一根判输。
现在人和计算机博弈,设计一个程序保证计算机必胜,要求每回合人与计算机各输入(或返回)一个代表取走火柴根数的数,直到游戏结束。
#include
usingnamespacestd;
intmain(){
intn=21;
intp,c;
while(n!
=0){
cin>>p;
while(p>4||p<=0||n-p<0){
cout<<"err,inputagain"<cin>>p;
}
if(n!
=0){
if(n!
=1)cout<<5-p<else{
cout<<"PCwins";
break;
}
if(n>=5)n-=5;
}
}
}
题目六:
(10分)
下列式子:
2+3+4=9
1+2+3+4=10
显然右边的数都能表示为n(n>2)个连续自然数之和(1开始),暂称之为囧数
但似乎23、32等数都不能写成几个数之和的形式,所以它们不是囧数
这里有个可行的判断方法为:
上限为N,则测试
1+2+3
1+2+3+4
……
1+2+3+4……+N
2+3+4
……
2+3+4+……+N
……
(N-2)+(N-1)+N
是否等于N
这是一种可行但非常暴力的穷举
实际上囧数还是有一些规律可循的,请设计一个优于之前提到的算法
要求输入一个数,并判断它是否为囧数
/*
1.如果一个数能被奇数(>=3)整除,则必能写成X=平均数*中间数的形式,所以是囧数
2.如果一个数是合数,如果其中有奇数因子,则回到1,为囧数;如果它是2的乘方,则不是囧数
证明:
它无法写成奇数个相加,因为除不尽奇数;也不能写成偶数个相加,中间数有两个,和必为奇数,这个奇数必然是欲判断数的一个因子
3.如果一个数是素数,则必须是6、10、14、18……个数相加得来,这样才能得到奇数,根据高斯求和公式,这样的和必有奇数因子
综上:
只有2的乘方、素数、小于6的自然数,不是囧数
*/
#include
usingnamespacestd;
boolcheck(longtar){
boolflag=false;
if(tar<6)flag=false;
else{
if(tar%2==0){//偶数是否是2的阶乘
while(tar%2==0)tar/=2;
tar==1?
flag=false:
flag=true;
}
else{//奇数是否是素数
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<return0;
}
题目七:
(10分)
现有一个固定的正方形区域,可以把它看作是一个数据库中的特别的二维码
11101
01001
01101
11011
00100
其中每一位表示黑和白,假设这种二维码容错性只有5%,即只要有1位以上不符合要求就无法识别。
现在输入一个5*5的类似区域(相当于扫描一个二维码),如果在容错围,则认为它可识别。
如果不是精确匹配,需输出错误位的位置。
#include
#include
usingnamespacestd;
intmain(){
interr=0,j=0;
chara[26];
charb[26]="01100100";
for(inti=0;i<25;i++){
cin>>a[i];
if(a[i]!
=b[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<<'('<}
return0;
}
题目八:
(10分)
每个人每天早上都要思考一个问题,这个问题的历史已经悠久得无法追溯,那就是:
今天午饭吃什么。
现在有个腻歪的人,他已经妥协于人工智能来解决日常问题,妄图找出吃饭问题的通解
已知:
根据区域定位有以下地方可去:
围1:
a品尝坊、b三疯、c南区食堂
围2:
d北区食堂、e咪哆
围3:
f大小姐的店
根据远近程度和价格因素,希望一周5天去围1的几率为20%,去围2的几率为70%,去围3的几率为10%(理论值)。
请写一段程序,随机输出15个字母(实际值),确定半个月的吃饭问题(不考虑跨平台)
注意:
以上概率是指[如果]取输出个数趋近于无穷时的概率,而不是指15次*20%等式四舍五入得到的输出结果。
#include
#include//linux/dev/random
//#include
usingnamespacestd;
/*
floatset_rand(){
srand(time_t(time(NULL)));//低精度取种,需循环辅助
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个战友(共41人)被罗马军队包围在洞中。
他们讨论是自杀还是被俘,最终决定自杀。
自杀规则规定,所有人围成一个圈,由一人开始报数,报到3的被杀死,下面的人继续从1报数,约瑟夫终和他的朋友活了下来。
问:
最初约瑟夫和他的朋友占据这个队伍的位置各为第几个?
无脑穷举,结果16、31
#include
usingnamespacestd;
intmain(){
intj=0;
ints=0;//jmp3
intn[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<
return0;
}
题目十:
(10分)
设计一个算法,计算输出1至这个自然数间‘1’共出现了几次,如1-11间‘1’出现了4次。
假设数在int围,不考虑效率。
(若算法效率足够高可先至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;
}
题目十一:
(15分)
假设5*4的代表一个逆时针旋转的字母区域,输入长宽,打印一个类似的字母区域,乘积若超过26继续由新一组的A、B、C……填充,不要求输出边框,例如5*4的样式如下:
ABCDE
NOPQF
MTSRG
LKJIH
#include
#include
#defineN100
chara[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{
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{
for(j=0;jprintf("%4c",a[i][j]);
printf("\n");
}
}
return0;
}
题目十二:
(15分)
设计一个函数f($a,$b),其中“$a,$b”代替一个无限循环小数,$a为固定部分,$b为循环体。
要求输出一个“x/y”的最简分数表达这个有理数,并测试-13.14(135)=-48623/3700
#include
#include
usingnamespacestd;
intcal(intx,inty){
return(!
y)?
x:
cal(y,x%y);
}//辗转相除
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[]tousignedlong
longm3=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<
}
intmain(){
f(-13.14,"135");
return0;
}
题目十三:
(15分)
输入4个坐标(前3个互不一样,且不共线),判断第4个点与前3个点所组成的三角形的位置关系(、外、上)。
#include
#include
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));//vector
doublea=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<returnabs(ABD+ACD+BCD-ABC)>=1E-5?
-1:
(ABD||ACD||BCD?
1:
0);
/*
相加与ABC不等在ABC外,返回-1
此处表示ABD+ACD+BCD与ABC误差超过10^-5,则说明在外
由于double开根导致精度损失,如要克服可以用行列式算法
相加与ABC相等,如果其中一个面积为0,则在线上,返回0
相加与ABC相等,如面积为0,则在ABC,返回1
*/
}
intmain(){
pointA,B,C,D;
cin>>A.x>>A.y;cout<