蓝桥杯决赛编程题汇总(含答案).docx

一.结果填空题。1.求最大公约数/辗转相除，求两个数的最大公约数public static int gcd(int n,int m)if(n = 0) return m;return gcd(m%n,n);/最小公倍数 = n*m/gcd(n,m)public static int gbs(int n,int m)return n*m/gcd(n, m);2.a 的 n 次幂public static int f(int a,int n)int x = 1;for(int i=0;in;i+) x = x*a;return x;/ a%p b%p = (a+b)%p = (a%p+b%p)/ (a*b)%p = (a%p)*(b%p)%p/ a 的 n 次幂 对 p取模public static int f2(int a,int n,int p)int x = 1;for(int i=0;in;i+) x = (x*a)%p;return x;3.第n个素数。素数是不能在进行等分的整数，比如 7，11。而9不是素数，因为它可以平分为3等分， 一般认为最小的素数是2，接着是3，5，。请问，第100002（十万零二）个素数是多少。请注意：2是第一个素数，3是第二个素数，一次类推筛法：public static void getSuShu(int n)int N = 1000*1000*10;byte a = new byteN;for (int i = 2; i N/2; i+) if(ai = 1)continue;/和数没有资格参加筛法for (int k = 2; k N/i; k+) if(i*kN) ai*k = 1;int m = 0;for (int i = 2; i N; i+) if(ai = 0)m+;if(m = n)System.out.println(=+i+ );System.out.println(m = +m);4.在n个球中，任意去除m个（不放回），有多少种取法？算法实现：public class Test_01/ 在n个球中，任意去除m个（不放回），有多少种取法？public static int test_01(int n , int m )/ 出口设计。if(nm) return 0;if(n=m) return 1;if(m=0)return 1;/ 递归主体。/* 想象，在n个球中有一个是特殊的球X，一定会取到的， * 然后划分为两种情况。 * * 取法划分，是否包含X * */return test_01(n-1,m-1)+test_01(n-1,m);public static void main(String args) int k = test_01(10,3);System.out.println(k);5.用递归实现，求n的阶乘，算法实现：public class Test_01 / 用递归实现，求n的阶乘，public static int getNum(int n)if (n=1|n=0) return n;elsereturn n*getNum(n-1);public static void main(String args) System.out.println(getNum(3);6.求n个元素的全排列public class Test_02 / 求n个元素的全排列/ abc acb bac bca cab cba/* * 规律：每个元素都可以放到首位，然后排放剩余的元素 */ 打印所有的全排列public static void main(String args) char data = ABC.toCharArray();f(data,0);/ k: 当前的交换位置（关注点），与其后的元素交换private static void f(char data,int k) if(k=data.length-1)for (int i = 0; i data.length; i+)System.out.print(datai+ );System.out.println();for (int i = k; i data.length; i+) / 试探char t = datak;datak = datai;datai = t;f(data,k+1);/ 回溯char t = datak;datak = datai;datai = t;7.求两个串的最大公共子序列的长度public class Test_03 / 求两个串的最大公共子序列的长度/ 算法 ： 可解 ， 优化public static void main(String args) int k = f(abc,xbacd);System.out.println(k);private static int f(String s1, String s2) if(s1.length()=0|s2.length()=0)return 0;if (s1.charAt(0)=s2.charAt(0)return f(s1.substring(1),s2.substring(1)+1;elsereturn Math.max(f(s1.substring(1),s2),f(s1,s2.substring(1);8.割圆求圆周率public static void f()System.out.println(标准 + Math.PI);double a = 1;/正六边形的变长，也是圆的半径int n = 6; / 刚开始有六条边，正六边形for (int i = 0; i end) return;System.out.println(begin);c_begin_dao_end(begin+1,end);/ n-0public static void c_end_dao_begin(int n)System.out.println(n);if(n0) c_end_dao_begin(n-1);10. 求 给定数组的 和/ 方法一public static int addAll1(int a,int begin)if(begin = a.length)return 0;int x = addAll1(a,begin+1);return x+abegin;/ 方法二public static int addAll2(int a,int end)if(end 0)return 0;int x = addAll2(a,end-1);return x+aend;11. 递归-判断两个字符串相等。public static boolean f(String s1,String s2)if(s1.length()!=s2.length() return false;if(s1.length()=0)return true;if(s1.charAt(0)!=s2.charAt(0) return false;return f(s1.substring(1),s2.substring(1);12. 从 n 个球中，任意取出 m 个（不放回），* 求有多少种取法public static int f(int n,int m)if(nm) return 0;if(n = m) return 1;if(m = 0) return 1;return f(n-1,m-1)+f(n-1,m);13. 求 一个 字符串的 全排列public static void f(chara,int k)if(k = a.length)String str = new String(a);/ 用set集合 可以去除重复/str = str.substring(0, 13);/str.toUpperCase();/sets.add(str);System.out.println(str);for (int i = k; i a.length; i+) char t = ak;ak = ai; ai = t;f(a,k+1);char t = ak;ak = ai; ai = t;14. 空瓶换汽水饮料店搞活动：不用付费，用3个某饮料的空瓶就可以换一瓶该饮料。 * 刚好小明前两天买了2瓶该饮料喝完了，瓶子还在。 * 他耍了个小聪明，向老板借了一个空瓶，凑成3个，换了一瓶该饮料，喝完还瓶！ * 饮料店老板一统计，已经售出该饮料且未还瓶的有12345瓶， * 那么如果这些饮料的买主都如小明一样聪明，老板最多还需要送出多少瓶饮料呢？显然答案是个正整数。public static int f(int num)if(num2)return 0;if(num = 2) return 1;return f(num - 2)+1;参考答案：617215. 三人年龄三个神秘蒙面人来访F博士。博士询问他们年龄时，他们说：我们中年龄最小的不超过19岁。我们3人年龄总和为70岁。且我们三人年龄的乘积是所有可能情况中最大的。请帮助F博士计算他们的年龄，从小到大排列，用逗号分开。public static void f()for (int i = 1; i 20; i+) for (int j = i; j 68; j+) for (int j2 = j; j2 68; j2+) if(i+j+j2 = 70) int a = i,j,j2;Arrays.sort(a);System.out.println(a0+ +a1+ +a2);参考答案：19,25,2616. 考察团组成某饭店招待国外考察团。按照标准，对领导是400元/人，随团职员200元/人，对司机50元/人。考察团共36人，招待费结算为3600元，请问领导、职员、司机各几人。public static void f()for (int i = 1; i 34; i+) for (int j = 1; j 34; j+) for (int j2 = 1; j2 120)System.out.println(y);else if(y-x0)System.out.println(0);elseif(t%6 = 0 & t%4 = 0)f(x*2,y*2,t+1);else if(t%6 = 0)f(x*2,y,t+1); else if(t%4 = 0)f(x,y*2,t+1);else if(t+1)%2=0)f(x,y-x,t+1);elsef(x,y,t+1);/ 解法2public static void f2()int i;int x = 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);参考答案：0 94371840 18. 除去次方数-利用筛法计算 次方数自然数的平方数是：1 4 9 16 25 自然数的立方数是：1 8 27 64 125 自然数的4次方数是：1 16 81 256 这些数字都可以称为次方数。110000中，去掉所有的次方数，还剩下多少个数字？public static void f()int num = new int10000;for (int i = 1; i Math.sqrt(num.length); i+) for (int j = 2; j num.length; j+) int n = (int) Math.pow(i, j);if(n10000)numn = 1;elsebreak;int m = 0;for (int i = 0; i num.length; i+) if(numi = 0) m+;/ 特别注意：/ 开始没有算0，所以下标为0的元素值始终未0；/即 num0 = 0; 恒成立System.out.println(m-1);参考答案：987519. 正六面体染色正六面体用4种颜色染色。共有多少种不同的染色样式？要考虑六面体可以任意旋转、翻转。20. 古堡算式福尔摩斯到某古堡探险，看到门上写着一个奇怪的算式： ABCDE * ? = EDCBA 他对华生说：“ABCDE应该代表不同的数字，问号也代表某个数字！” 华生：“我猜也是！” 于是，两人沉默了好久，还是没有算出合适的结果来。 请你利用计算机的优势，找到破解的答案。 把 ABCDE 所代表的数字写出来。private static void f() for (int a = 1; a = 9; a+) for (int b = 0; b = 9; b+) for (int c = 0; c = 9; c+) for (int d = 0; d = 9; d+) for (int e = 0; e = 9; e+) if(a !=b & b != c & c != d & d != a & a != c & b != d)int left = a*10000+b*1000+c*100+d*10+e;int reght = e*10000+d*1000+c*100+b*10+a;for (int i = 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，mums0代表E，nums4代表A，从（10000,100000）中取一个数字，先把这个五位数的每一位上的值赋给这个数组；2、检验这个数组中的数字是否满足两两互不相同，若满足则继续第三步，若不满足则跳回第一步；3、从2,10）中取一个数字跟满足条件的五位数相乘，检验ABCDE*？是否超过100000，如果超过则再在2,10)中找下一个数字检验，如果不超过则继续下一步；4、判断ABCDE*?=EDCBA，如果相等则找到符合条件的等式，若不相等则调回第一步。public class ABCDE_to_EDCBA public static final int Max=100000; public static boolean judge(int m,int n)/m代表每位上数字都不相同的五位数，n代表？ int nums = new int5; int i = 0; int p = m; while(p!=0) numsi+ = p%10; p/=10; for(int x = 0 ;x4;x+)/获得此五位数即ABCDE for(int y = x+1;y5;y+) if(numsx=numsy) return false; p = m*n; if(p/Max!=0)/ABCDE*?不能超过五位数 return false; /判断ABCDE*?=EDCBA int k = 4; while(k!=0) if(numsk!=p%10) return false; p/=10; k-; return true; public static void main(String args) for(int i = 10000;iMax;i+) for(int j = 2 ;j 0; a-) for (int b = a-1; b 0; b-) for (int c = b-1; c 0; c-) for (int d = 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分，如果不让你看比赛过程，你能推断出他（她）哪个题目答对了，哪个题目答错了吗？如果把答对的记为1，答错的记为0，则10个题目的回答情况可以用仅含有1和0的串来表示。例如：0010110011 就是可能的情况。你的任务是算出所有可能情况。每个答案占一行。多个答案顺序不重要。public static void main(String args) char num = new char10;f(1, 10, num);private static void f(int i,int sc, char a) if(i 10)if (sc = 100)System.out.println(new String(a);elseai-1 = 1;f(i+1,sc+sc,a);ai-1 = 0;f(i+1,sc-i,a);参考答案：10110100000111010000001011001123. 土地测量造成高房价的原因有许多，比如土地出让价格。既然地价高，土地的面积必须仔细计算。遗憾的是，有些地块的形状不规则，比如是如图【1.jpg】中所示的五边形。一般需要把它划分为多个三角形来计算。已知三边求三角形的面积需要用海伦定理，参见【2.jpg】各条边长数据如下：AB = 52.1BC = 57.2CD = 43.5DE = 51.9EA = 33.4EB = 68.2EC = 71.9根据这些数据求五边形地块的面积。四舍五入到小数后两位。只写结果，不要源代码！答案写在“解答.txt”中，不要写在这里！图1图224. 欧拉与鸡蛋大数学家欧拉在集市上遇到了本村的两个农妇，每人跨着个空篮子。她们和欧拉打招呼说两人刚刚卖完了所有的鸡蛋。欧拉随便问：“卖了多少鸡蛋呢？”不料一个说：“我们两人自己卖自己的，一共卖了150个鸡蛋，虽然我们卖的鸡蛋有多有少，但刚好得了同样的钱数。你猜猜看！”欧拉猜不出。另一个补充道：“如果我按她那样的价格卖，可以得到32元；如果她按我的价格卖，可以得到24.5元”。欧拉想了想，说出了正确答案。我们不是数学家，懒得列出公式来分析。但计算机可以“暴力破解”，就是把所有可能情况都试验一遍，撞上为止！请写出每人鸡蛋的数目（顺序不限），用逗号隔开。private static void f() for (int x = 1; x 150; x+) int ap = 2450/x;int bp = 3200/(150-x);if(x*bp = ap*(150-x)System.out.println(x=+x+;y=+(150-x);参考答案：70 8025.巧排扑克小明刚上小学，学会了第一个扑克牌“魔术”，到处给人表演。魔术的内容是这样的：他手里握着一叠扑克牌：A，2，.J，Q，K 一共13张。他先自己精心设计它们的顺序，然后正面朝下拿着，开始表演。只见他先从最下面拿一张放到最上面，再从最下面拿一张翻开放桌子上，是A；然后再从最下面拿一张放到最上面，再从最下面拿一张翻开放桌子上，是2；.如此循环直到手中只有一张牌，翻开放桌子上，刚好是K。这时，桌上牌的顺序是：A,2,3,4,5,6,7,8,9,10,J,Q,K请你计算一下，小明最开始的时候手里牌的顺序是怎样的。把结果写出来，逗号分割，小明“魔术”开始时，最下面的那张牌输出为第一个数据。考场不提供扑克牌，你只能用计算机模拟了，撕碎草稿纸模拟扑克属于作弊行为！另外，你有没有把录像倒着放过？很有趣的！回去试试！/ 解法一：public static void card() int num = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 ;boolean temp = false; / temp表示是否取出牌int count = 0;int middle = new int13;/ 建立中间数据保存卡牌经过处理后的位置变化int index = 0;int lastresult = new int13;while (count = 13) index -= 13;play(middle);System.out.println();/ 由于数组middle保存了卡牌变化后的位置，/ 把A到K即放到他对应的位置，即可得到结果。for (int i = 0; i 13; i+) int k = middlei - 1;lastresultk = i + 1;play(lastresult);private static void play(int num) for (int i = 0; i num.length; i+) int n = numi;switch (n) case 1:System.out.print(A,);break;case 11:System.out.print(J,);break;case 12:System.out.print(Q,);break;case 13:System.out.print(K,);break;default:System.out.print(n + ,);break;/ 方法二/* * 倒推法，翻开一张牌的顺序是： * 先把它前面的那张牌放在队尾然后它在翻开放在队尾， * 这样如果逆过来就是它先到队尾，再让它前面那张牌到队尾。 * 最后一张肯定是K，第一张是A这样逆转过来的顺序便是从K到A。 */public char result, order = new char13;public void operator(char c, int len) orderlen = c;c = order0;for (int i = 0; i len; i+)orderi = orderi + 1;orderlen = c;Testpublic void main2() result = new char K, Q, J, T, 9, 8, 7, 6, 5, 4,3, 2, A ;for (int i = 0; i = 0; j-) if (orderj = T) System.out.print(10,);continue;System.out.print(orderj + ,);结果:7,A,Q,2,8,3,J,4,9,5,K,6,1026.排座位要安排：3个A国人，3个B国人，3个C国人坐成一排。要求不能使连续的3个人是同一个国籍。求所有不同方案的总数？public static int count = 0;public static void main(String args) int a = 1,1,1,2,2,2,3,3,3;f(a,0);System.out.println(count);private static void f(int a, int k) if(k = a.length)if(isTrue(a)count+;for (int i = k; i a.length; i+) int t = ak;ak = ai; ai = t;f(a,k+1);int t = ak;ak = ai; ai = t;private static boolean isTrue(int a) boolean flag = true;for (int i = 0; i a.length-2; i+) if(ai = ai+1&ai = ai+2)return false;return flag;结果：28382427.黄金队列黄金分割数是个无理数，个整数也就是无法表示为两的比值。0.618只是它的近似值，其真值可以通过对5开方减去1再除以2来获得，我们取它的一个较精确的近似值：0.618034有趣的是，一些简单的数列中也会包含这个无理数，这很令数学家震惊！1 3 4 7 11 18 29 47 . 称为“鲁卡斯队列”。它后面的每一个项都是前边两项的和。如果观察前后两项的比值，即：1/3,3/4,4/7,7/11,11/18 . 会发现它越来越接近于黄金分割数！你的任务就是计算出从哪一项开始，这个比值四舍五入后已经达到了与0.618034一致的精度。请写出该比值。格式是：分子/分母。比如：29/47public static void main(String args) for (int i = 2; i = 3) return f(n-1)+f(n-2);return 0;参考答案：1364/2207*28.汉诺塔计数。汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上(可以借助第三根柱子做缓冲)。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。如图【1.jpg】是现代“山寨”版的该玩具。64个圆盘太多了，所以减为7个，金刚石和黄金都以木头代替了.但道理是相同的。据说完成大梵天的命令需要太多的移动次数，以至被认为完成之时就是世界末日！你的任务是精确计算出到底需要移动多少次。很明显，如果只有2个圆盘，需要移动3次。圆盘数为3，则需要移动7次。那么64个呢？答案写在“解答.txt”中，不要写在这里！图1public static int num = 0;public static void main(String args) System.out.println(输入盘子的个数：);Scanner sc=new Scanner(System.in);int n=sc.nextInt();tower(n,A,B,C);System.out.println(num);public static void tower(int n,char a, char b, char c)if(n!=0)num+;tower(n-1,a,c,b);/System.out.println(move disk +n+t+from +a+t+to +c);c=a;tower(n-1,b,a,c);29.猜生日。今年的植树节（2012年3月12日），小明和他的叔叔还有小伙伴们一起去植树。休息的时候，小明的同学问他叔叔多大年纪，他叔叔说：“我说个题目，看你们谁先猜出来！”“把我出生的年月日连起来拼成一个8位数（月、日不足两位前补0）正好可以被今天的年、月、日整除！”他想了想，又补充到：“再给个提示，我是6月出生的。”根据这些信息，请你帮小明算一下，他叔叔的出生年月日。答案写在“解答.txt”中，不要写在这里！格式是年月日连成的8位数。例如，如果是1948年6月12日，就写：19480612public static void main(String args) for (int i = 1932; i 2012; i+) for (int j = 1; j = 30; j+) String s = ;if(j9?j:0+j);参考答案：1955060430.棋盘上的麦子。你一定听说过这个故事。国王对发明国际象棋的大臣很佩服，问他要什么报酬，大臣说：请在第1个棋盘格放1粒麦子，在第2个棋盘格放2粒麦子，在第3个棋盘格放4粒麦子，在第4个棋盘格放8粒麦子，.后一格的数字是前一格的两倍，直到放完所有棋盘格（国际象棋共有64格）。国王以为他只是想要一袋麦子而已，哈哈大笑。当时的条件下无法准确计算，但估算结果令人吃惊：即使全世界都铺满麦子也不够用！请你借助计算机准确地计算，到底需要多少粒麦子。public static void main(String args) BigInteger num = BigInteger.valueOf(1L);for (int i = 2; i = 64; i+) num = num.add(f(i-1);System.out.println(num);public static BigInteger f(int i) BigInteger n = new BigInteger(2+);return n.pow(i);参考答案：1844674407370955161531.国庆星期日。1949年的国庆节（10月1日）是星期六。 今年（2012）的国庆节是星期一。那么，从建国到现在，有几次国庆节正好是星期日呢？只要答案，不限手段！可以用windows日历，windows计算器，Excel公式，。当然，也可以编程！不要求写出具体是哪些年，只要一个数目！千万不要提交源代码！答案不要写在这里，写在“解答.txt”中/ 计算星期几，基姆拉尔森公式，月份，3月到14月。/ 当年的1,2月要转换为前一年的13,14月，相应的年份减1。/ w=y+y/4-y/100+y/400+3*(m+1)/5+d+2*m+1;public static void main(String args) f();private static void f() int num = 0;for (int y = 1949; y = 2012; y+) int d = 1;int w=y+y/4-y/100+y/400+33/5+d+21;if(w%7 = 0)num+;System.out.println(num);参考答案：932.填写算式。看这个算式： + = 如果每个五角星代表 1 9 的不同的数字。这个算式有多少种可能的正确填写方法？173 + 286