蓝桥杯决赛编程题汇总含答案.docx
《蓝桥杯决赛编程题汇总含答案.docx》由会员分享，可在线阅读，更多相关《蓝桥杯决赛编程题汇总含答案.docx（84页珍藏版）》请在冰点文库上搜索。
蓝桥杯决赛编程题汇总含答案
一.结果填空题。
1.求最大公约数
//辗转相除，求两个数的最大公约数
publicstaticintgcd（intn,intm）{
if（n==0）returnm;
returngcd（m%n,n）;
}
//最小公倍数=n*m/gcd（n,m）
publicstaticintgbs（intn,intm）{
returnn*m/gcd（n,m）;
}
2.a的n次幂
publicstaticintf（inta,intn）{
intx=1;
for（inti=0;ireturnx;
}
//a%pb%p==（a+b）%p=（a%p+b%p）
//（a*b）%p=（（a%p）*（b%p））%p
//a的n次幂对p取模
publicstaticintf2（inta,intn,intp）{
intx=1;
for（inti=0;ireturnx;
}
3.第n个素数。
素数是不能在进行等分的整数，比如7，11。
而9不是素数，因为它可以平分为3等分，一般认为最小的素数是2，接着是3，5，。
。
请问，第100002（十万零二）个素数是多少。
请注意：
2是第一个素数，3是第二个素数，一次类推
筛法：
publicstaticvoidgetSuShu（intn）{
intN=1000*1000*10;
byte[]a=newbyte[N];
for（inti=2;iif（a[i]==1）continue;
//和数没有资格参加筛法
for（intk=2;kif（i*k}
}
intm=0;
for（inti=2;iif（a[i]==0）{
m++;
if（m==n）
System.out.println（"=="+i+""）;
}
}
System.out.println（"m=="+m）;
}
4.在n个球中，任意去除m个（不放回），有多少种取法？
算法实现：
publicclassTest_01{
//在n个球中，任意去除m个（不放回），有多少种取法？
publicstaticinttest_01（intn,intm）{
//出口设计。
。
。
if（nif（n==m）return1;
if（m==0）return1;
//递归主体。
。
。
/**
*想象，在n个球中有一个是特殊的球X，一定会取到的，
*然后划分为两种情况。
*
*取法划分，是否包含X
*
*/
returntest_01（n-1,m-1）+test_01（n-1,m）;
}
publicstaticvoidmain（String[]args）{
intk=test_01（10,3）;
System.out.println（k）;
}
}
5.用递归实现，求n的阶乘，
算法实现：
publicclassTest_01{
//用递归实现，求n的阶乘，
publicstaticintgetNum（intn）{
if（n==1||n==0）{
returnn;
}else{
returnn*getNum（n-1）;
}
}
publicstaticvoidmain（String[]args）{
System.out.println（getNum（3））;
}
}
6.求n个元素的全排列
publicclassTest_02{
//求n个元素的全排列
//abcacbbacbcacabcba
/**
*规律：
每个元素都可以放到首位，然后排放剩余的元素
*/
//打印所有的全排列
publicstaticvoidmain（String[]args）{
char[]data="ABC".toCharArray（）;
f（data,0）;
}
//k:
当前的交换位置（关注点），与其后的元素交换
privatestaticvoidf（char[]data,intk）{
if（k==data.length-1）{
for（inti=0;iSystem.out.print（data[i]+""）;
System.out.println（）;
}
for（inti=k;i//试探
{chart=data[k];data[k]=data[i];data[i]=t;}
f（data,k+1）;
//回溯
{chart=data[k];data[k]=data[i];data[i]=t;}
}
}
}
7.求两个串的最大公共子序列的长度
publicclassTest_03{
//求两个串的最大公共子序列的长度
//算法：
可解，优化
publicstaticvoidmain（String[]args）{
intk=f（"abc","xbacd"）;
System.out.println（k）;
}
privatestaticintf（Strings1,Strings2）{
if（s1.length（）==0||s2.length（）==0）return0;
if（s1.charAt（0）==s2.charAt（0））
returnf（s1.substring
（1）,s2.substring
（1））+1;
else
returnMath.max（f（s1.substring
（1）,s2）,f（s1,s2.substring
（1）））;
}
}
8.割圆求圆周率
publicstaticvoidf（）{
System.out.println（"标准"+Math.PI）;
doublea=1;//正六边形的变长，也是圆的半径
intn=6;//刚开始有六条边，正六边形
for（inti=0;i<10;i++）{
doubleb=Math.sqrt（1-（a/2）*（a/2））;
a=Math.sqrt（（1-b）*（1-b）+（a/2）*（a/2））;
n=n*2;//填空
System.out.println（n+""+n*a/2）;//填空
}
}
9.打印n---0*打印0---n
//0--n
publicstaticvoidc_begin_dao_end（intbegin,intend）{
if（begin>end）return;
System.out.println（begin）;
c_begin_dao_end（begin+1,end）;
}
//n---0
publicstaticvoidc_end_dao_begin（intn）{
System.out.println（n）;
if（n>0）c_end_dao_begin（n-1）;
}
10.求给定数组的和
//方法一
publicstaticintaddAll1（int[]a,intbegin）{
if（begin==a.length）return0;
intx=addAll1（a,begin+1）;
returnx+a[begin];
}
//方法二
publicstaticintaddAll2（int[]a,intend）{
if（end<0）return0;
intx=addAll2（a,end-1）;
returnx+a[end];
}
11.递归---判断两个字符串相等。
publicstaticbooleanf（Strings1,Strings2）{
if（s1.length（）!
=s2.length（））
returnfalse;
if（s1.length（）==0）
returntrue;
if（s1.charAt（0）!
=s2.charAt（0））
returnfalse;
returnf（s1.substring
（1）,s2.substring
（1））;
}
12.从n个球中，任意取出m个（不放回），*求有多少种取法
publicstaticintf（intn,intm）{
if（nif（n==m）return1;
if（m==0）return1;
returnf（n-1,m-1）+f（n-1,m）;
}
13.求一个字符串的全排列
publicstaticvoidf（char[]a,intk）{
if（k==a.length）{
Stringstr=newString（a）;
//用set集合可以去除重复
//str=str.substring（0,13）;
//str.toUpperCase（）;
//sets.add（str）;
System.out.println（str）;
}
for（inti=k;i{chart=a[k];a[k]=a[i];a[i]=t;}
f（a,k+1）;
{chart=a[k];a[k]=a[i];a[i]=t;}
}
}
14.空瓶换汽水
饮料店搞活动：
不用付费，用3个某饮料的空瓶就可以换一瓶该饮料。
*刚好小明前两天买了2瓶该饮料喝完了，瓶子还在。
*他耍了个小聪明，向老板借了一个空瓶，凑成3个，换了一瓶该饮料，喝完还瓶！
！
*饮料店老板一统计，已经售出该饮料且未还瓶的有12345瓶，
*那么如果这些饮料的买主都如小明一样聪明，老板最多还需要送出多少瓶饮料呢？
显然答案是个正整数。
publicstaticintf（intnum）{
if（num<2）return0;
if（num==2）return1;
returnf（num-2）+1;
}
参考答案：
6172
15.三人年龄
三个神秘蒙面人来访F博士。
博士询问他们年龄时，他们说：
我们中年龄最小的不超过19岁。
我们3人年龄总和为70岁。
且我们三人年龄的乘积是所有可能情况中最大的。
请帮助F博士计算他们的年龄，从小到大排列，用逗号分开。
publicstaticvoidf（）{
for（inti=1;i<20;i++）{
for（intj=i;j<68;j++）{
for（intj2=j;j2<68;j2++）{
if（i+j+j2==70）{
int[]a={i,j,j2};
Arrays.sort（a）;
System.out.println（a[0]+""+a[1]+""+a[2]）;
}
}
}
}
}
参考答案：
19,25,26
16.考察团组成
某饭店招待国外考察团。
按照标准，对领导是400元/人，随团职员200元/人，对司机50元/人。
考察团共36人，招待费结算为3600元，请问领导、职员、司机各几人。
publicstaticvoidf（）{
for（inti=1;i<34;i++）{
for（intj=1;j<34;j++）{
for（intj2=1;j2<34;j2++）{
if（（i+j+j2）==36&&（i*400+j*200+j2*50）==3600）{
System.out.println（i+"，"+j+"，"+j2）;
}
}
}
}
}
参考答案：
3,5,28
17.微生物增殖
假设有两种微生物X和Y.X出生后每隔3分钟分裂一次（数目加倍），Y出生后每隔2分钟分裂一次（数目加倍）。
一个新出生的X，半分钟之后吃掉1个Y，并且，从此开始，每隔1分钟吃1个Y。
现在已知有新出生的X=10,Y=89，求60分钟后Y的数目。
如果X=10，Y=90呢？
本题的要求就是写出这两种初始条件下，60分钟后Y的数目。
两个整数，每个1行。
//t为当前的时间，把每一分钟分为两个半分钟。
//x:
开始时x微生物的数量，y:
开始时y微生物的数量，
publicstaticvoidf（intx,inty,intt）{
if（t>120）{
System.out.println（y）;
}elseif（y-x<0）{
System.out.println（0）;
}else{
if（t%6==0&&t%4==0）{
f（x*2,y*2,t+1）;
}elseif（t%6==0）{
f（x*2,y,t+1）;
}elseif（t%4==0）{
f（x,y*2,t+1）;
}elseif（（t+1）%2==0）{
f（x,y-x,t+1）;
}else{
f（x,y,t+1）;
}
}
}
//解法2
publicstaticvoidf2（）{
inti;
intx=10,y=90;
for（i=1;i<=120;i++）{
if（i%2==0）y=y-x;
if（i%4==0）y=y*2;
if（i%6==0）x=x*2;
}
System.out.println（y）;
}
参考答案：
094371840
18.除去次方数--利用筛法计算次方数
自然数的平方数是：
1491625…
自然数的立方数是：
182764125…
自然数的4次方数是：
11681256…
…
这些数字都可以称为次方数。
1~10000中，去掉所有的次方数，还剩下多少个数字？
publicstaticvoidf（）{
intnum[]=newint[10000];
for（inti=1;ifor（intj=2;jintn=（int）Math.pow（i,j）;
if（n<10000）{
num[n]=1;
}else{
break;
}
}
}
intm=0;
for（inti=0;iif（num[i]==0）m++;
}
//特别注意：
//开始没有算0，所以下标为0的元素值始终未0；
//即num[0]==0;恒成立
System.out.println（m-1）;
}
参考答案：
9875
19.正六面体染色
正六面体用4种颜色染色。
共有多少种不同的染色样式？
要考虑六面体可以任意旋转、翻转。
20.古堡算式
福尔摩斯到某古堡探险，看到门上写着一个奇怪的算式：
ABCDE*?
=EDCBA
他对华生说：
“ABCDE应该代表不同的数字，问号也代表某个数字！
”
华生：
“我猜也是！
”
于是，两人沉默了好久，还是没有算出合适的结果来。
请你利用计算机的优势，找到破解的答案。
把ABCDE所代表的数字写出来。
privatestaticvoidf（）{
for（inta=1;a<=9;a++）{
for（intb=0;b<=9;b++）{
for（intc=0;c<=9;c++）{
for（intd=0;d<=9;d++）{
for（inte=0;e<=9;e++）{
if（a!
=b&&b!
=c&&c!
=d&&d!
=a&&a!
=c&&b!
=d）{
intleft=a*10000+b*1000+c*100+d*10+e;
intreght=e*10000+d*1000+c*100+b*10+a;
for（inti=0;i<=9;i++）{
if（left*i==reght）System.out.println（left）;
}
}
}
}
}
}
}
}
方法二：
巧妙之处在如何获取五个互不相同的数字。
思路：
用五位数的每一位分别代表ABCDE，这样查找范围就是（10000,100000），同样要满足ABCDE*?
=EDCBA，ABCDE*?
的范围同样是（10000,100000）。
而？
代表的数字不可能是1，范围是[2,10）。
1、定义一个长度为五的数组nums，mums[0]代表E，nums[4]代表A，从（10000,100000）中取一个数字，先把这个五位数的每一位上的值赋给这个数组；2、检验这个数组中的数字是否满足两两互不相同，若满足则继续第三步，若不满足则跳回第一步；3、从[2,10）中取一个数字跟满足条件的五位数相乘，检验ABCDE*？
是否超过100000，如果超过则再在[2,10）中找下一个数字检验，如果不超过则继续下一步；4、判断ABCDE*?
=EDCBA，如果相等则找到符合条件的等式，若不相等则调回第一步。
publicclassABCDE_to_EDCBA{
publicstaticfinalintMax=100000;
publicstaticbooleanjudge（intm,intn）//m代表每位上数字都不相同的五位数，n代表？
{
int[]nums=newint[5];
inti=0;
intp=m;
while（p!
=0）
{
nums[i++]=p%10;
p/=10;
}
for（intx=0;x<4;x++）//获得此五位数即ABCDE
for（inty=x+1;y<5;y++）
if（nums[x]==nums[y]）
returnfalse;
p=m*n;
if（p/Max!
=0）//ABCDE*?
不能超过五位数
returnfalse;
//判断ABCDE*?
=EDCBA
intk=4;
while（k!
=0）
{
if（nums[k]!
=p%10）
returnfalse;
p/=10;
k--;
}
returntrue;
}
publicstaticvoidmain（String[]args）{
for（inti=10000;i{
for（intj=2;j<10;j++）
{
if（judge（i,j））
System.out.println（i+"*"+j+"="+i*j）;
}
}
}
}
参考答案：
1098921978
21.海盗比酒量
有一群海盗（不多于20人），在船上比拼酒量。
过程如下：
打开一瓶酒，所有在场的人平分喝下，有几个人倒下了。
再打开一瓶酒平分，又有倒下的，再次重复......直到开了第4瓶酒，坐着的已经所剩无几，海盗船长也在其中。
当第4瓶酒平分喝下后，大家都倒下了。
等船长醒来，发现海盗船搁浅了。
他在航海日志中写到：
“......昨天，我正好喝了一瓶.......奉劝大家，开船不喝酒，喝酒别开船......”
请你根据这些信息，推断开始有多少人，每一轮喝下来还剩多少人没倒下。
如果有多个可能的答案，请列出所有答案，每个答案占一行。
格式是：
人数,人数,...
例如,有一种可能是：
20,5,4,2,0
多个答案排列顺序不重要。
privatestaticvoidf（）{
for（inta=20;a>0;a--）{
for（intb=a-1;b>0;b--）{
for（intc=b-1;c>0;c--）{
for（intd=c-1;d>0;d--）{
if（b*c*d+a*c*d+a*b*d+a*b*c==a*b*c*d）
System.out.println（a+","+b+","+c+","+d）;
}
}
}
}
}
参考答案：
18,9,3,2,0（1分）
15,10,3,2,0（2分）
20,5,4,2,0（0分）
12,6,4,2,0（2分）
22.奇怪的比赛
某电视台举办了低碳生活大奖赛。
题目的计分规则相当奇怪：
每位选手需要回答10个问题（其编号为1到10），越后面越有难度。
答对的，当前分数翻倍；答错了则扣掉与题号相同的分数（选手必须回答问题，不回答按错误处理）。
每位选手都有一个起步的分数为10分。
某获胜选手最终得分刚好是100分，如果不
升级会员 