首页 > 代码库 > 算法笔记_211:第七届蓝桥杯软件类决赛部分真题(Java语言A组)
算法笔记_211:第七届蓝桥杯软件类决赛部分真题(Java语言A组)
目录
1 阶乘位数
2 凑平方数
3 棋子换位
4 机器人塔
前言:以下代码仅供参考,若有错误欢迎指正哦~
1 阶乘位数
阶乘位数 9的阶乘等于:362880 它的二进制表示为:1011000100110000000 这个数字共有19位。 请你计算,9999 的阶乘的二进制表示一共有多少位? 注意:需要提交的是一个整数,不要填写任何无关内容(比如说明解释等) 答案:118445
1 import java.math.BigInteger; 2 3 public class Main { 4 5 public static void main(String[] args) { 6 BigInteger result = new BigInteger("1"); 7 for(int i = 1;i <= 9999;i++) { 8 BigInteger temp = new BigInteger(""+i); 9 result = result.multiply(temp); 10 } 11 long count = 0; 12 BigInteger a = new BigInteger("2"); 13 while(result.compareTo(BigInteger.ZERO) > 0) { 14 count++; 15 result = result.divide(a); 16 //System.out.println("count = "+count); 17 } 18 System.out.println(count); 19 } 20 }
2 凑平方数
凑平方数 把0~9这10个数字,分成多个组,每个组恰好是一个平方数,这是能够办到的。 比如:0, 36, 5948721 再比如: 1098524736 1, 25, 6390784 0, 4, 289, 15376 等等... 注意,0可以作为独立的数字,但不能作为多位数字的开始。 分组时,必须用完所有的数字,不能重复,不能遗漏。 如果不计较小组内数据的先后顺序,请问有多少种不同的分组方案? 注意:需要提交的是一个整数,不要填写多余内容。 答案:300
1 import java.util.Arrays; 2 import java.util.HashSet; 3 4 public class Main { 5 public static HashSet<String> set = new HashSet<String>(); 6 7 public void swap(int[] A, int i, int j) { 8 int temp = A[i]; 9 A[i] = A[j]; 10 A[j] = temp; 11 } 12 13 public void dfsAllSort(int[] A, int step) { 14 if(step == A.length) { 15 long[] B = new long[A.length]; 16 dfsSqrtNum(A, 0, B, 0); 17 return; 18 } else { 19 for(int i = step;i < A.length;i++) { 20 swap(A, i, step); 21 dfsAllSort(A, step + 1); 22 swap(A, i, step); 23 } 24 } 25 } 26 27 public void dfsSqrtNum(int[] A, int step, long[] B, int num) { 28 if(step == A.length) { 29 StringBuffer s = new StringBuffer(""); 30 long[] arrayA = new long[num]; 31 for(int i = 0;i < num;i++) 32 arrayA[i] = B[i]; 33 Arrays.sort(arrayA); 34 for(int i = 0;i < num;i++) { 35 s.append(arrayA[i]); 36 if(i != num - 1) 37 s.append("-"); 38 } 39 set.add(s.toString()); 40 return; 41 } 42 43 if(A[step] == 0) { 44 B[num] = 0; 45 dfsSqrtNum(A, step + 1, B, num + 1); 46 } else { 47 long sum = 0; 48 for(int i = step;i < A.length;i++) { 49 sum = sum * 10 + A[i]; 50 double son = Math.sqrt(sum * 1.0); 51 long a = (long) son; 52 if(a == son) { 53 B[num] = sum; 54 dfsSqrtNum(A, i + 1, B, num + 1); 55 } 56 } 57 } 58 59 } 60 61 public static void main(String[] args) { 62 Main test = new Main(); 63 int[] A = {0,1,2,3,4,5,6,7,8,9}; 64 test.dfsAllSort(A, 0); 65 System.out.println(set.size()); 66 } 67 }
3 棋子换位
棋子换位 有n个棋子A,n个棋子B,在棋盘上排成一行。 它们中间隔着一个空位,用“.”表示,比如: AAA.BBB 现在需要所有的A棋子和B棋子交换位置。 移动棋子的规则是: 1. A棋子只能往右边移动,B棋子只能往左边移动。 2. 每个棋子可以移动到相邻的空位。 3. 每个棋子可以跳过相异的一个棋子落入空位(A跳过B或者B跳过A)。 AAA.BBB 可以走法: 移动A ==> AA.ABBB 移动B ==> AAAB.BB 跳走的例子: AA.ABBB ==> AABA.BB 以下的程序完成了AB换位的功能,请仔细阅读分析源码,填写划线部分缺失的内容。 public class Main { static void move(char[] data, int from, int to) { data[to] = data[from]; data[from] = ‘.‘; } static boolean valid(char[] data, int k) { if(k<0 || k>=data.length) return false; return true; } static void f(char[] data) { while(true){ boolean tag = false; for(int i=0; i<data.length; i++){ int dd = 0; // 移动方向 if(data[i]==‘.‘) continue; if(data[i]==‘A‘) dd = 1; if(data[i]==‘B‘) dd = -1; if(valid(data, i+dd) && valid(data,i+dd+dd) && data[i+dd]!=data[i] && data[i+dd+dd]==‘.‘){ // 如果能跳... move(data, i, i+dd+dd); System.out.println(new String(data)); tag = true; break; } } if(tag) continue; for(int i=0; i<data.length; i++){ int dd = 0; // `移动方向 if(data[i]==‘.‘) continue; if(data[i]==‘A‘) dd = 1; if(data[i]==‘B‘) dd = -1; if(valid(data, i+dd) && data[i+dd]==‘.‘){ // 如果能移动... if( _____________________ ) continue; //填空位置 move(data, i, i+dd); System.out.println(new String(data)); tag = true; break; } } if(tag==false) break; } } public static void main(String[] args) { char[] data = "http://www.mamicode.com/AAA.BBB".toCharArray(); f(data); } } 注意:只提交划线部分缺少的代码,不要复制已有代码或填写任何多余内容。 答案:valid(data,i+dd+dd) && valid(data, i-dd) && data[i-dd] == data[i+dd+dd]
4 机器人塔
机器人塔 X星球的机器人表演拉拉队有两种服装,A和B。 他们这次表演的是搭机器人塔。 类似: A B B A B A A A B B B B B A B A B A B B A 队内的组塔规则是: A 只能站在 AA 或 BB 的肩上。 B 只能站在 AB 或 BA 的肩上。 你的任务是帮助拉拉队计算一下,在给定A与B的人数时,可以组成多少种花样的塔。 输入一行两个整数 M 和 N,空格分开(0<M,N<500),分别表示A、B的人数,保证人数合理性。 要求输出一个整数,表示可以产生的花样种数。 例如: 用户输入: 1 2 程序应该输出: 3 再例如: 用户输入: 3 3 程序应该输出: 4 资源约定: 峰值内存消耗 < 256M CPU消耗 < 1000ms 请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。 所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。 注意:不要使用package语句。不要使用jdk1.7及以上版本的特性。 注意:主类的名字必须是:Main,否则按无效代码处理。
1 import java.util.Scanner; 2 3 public class Main { 4 public static int m, n; 5 public static int[][] value; //此处用数字1代表A,数字2代表B 6 public static int len, count = 0; 7 8 public void check() { 9 for(int i = len - 2, t = 1;i >= 0;i--, t++) 10 for(int j = 0;j < len - t;j++) { 11 if(value[i + 1][j] == value[i + 1][j + 1]) 12 value[i][j] = 1; 13 else 14 value[i][j] = 2; 15 } 16 int sumA = 0, sumB = 0; 17 for(int i = 0, t = len - 1;i < len;i++, t--) 18 for(int j = 0;j < len - t;j++) { 19 if(value[i][j] == 1) 20 sumA++; 21 else if(value[i][j] == 2) 22 sumB++; 23 } 24 if(sumA == m && sumB == n) 25 count++; 26 } 27 28 public void dfs(int step) { 29 if(step == len) { 30 check(); 31 return; 32 } else { 33 for(int i = 1;i <= 2;i++) { 34 value[len - 1][step] = i; //确定三角形最底层一行,即可确定整个三角形 35 dfs(step + 1); 36 } 37 } 38 } 39 40 41 public static void main(String[] args) { 42 Main test = new Main(); 43 Scanner in = new Scanner(System.in); 44 m = in.nextInt(); 45 n = in.nextInt(); 46 for(int i = 1;i < 100;i++) { //满足三角形规则,可知i层,则(i + 1) * i / 2 = m + n 47 int a = (i + 1) * i / 2; 48 if(a == m + n) { 49 len = i; 50 value = http://www.mamicode.com/new int[a][a]; 51 break; 52 } 53 } 54 test.dfs(0); 55 System.out.println(count); 56 } 57 }
算法笔记_211:第七届蓝桥杯软件类决赛部分真题(Java语言A组)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。