全国软件设计大赛java模拟题及答案.doc

2011 模拟 java 本科注意：本套模拟题主要模拟命题形式与考核范围。真实竞赛题的数量、难度可能与此套模拟题有差异。说明：本试卷包含两种题型：“代码填空”与“程序设计”。填空题要求参赛选手在弄清给定代码工作原理的基础上填写缺失的部分，使得程序逻辑正确、完整。所填写的代码不多于一条语句（即不能出现分号）。编程题要求选手设计的程序对于给定的输入能给出正确的输出结果。注意：在评卷时使用的输入数据与试卷中给出的实例数据可能是不同的。选手的程序必须是通用的，不能只对试卷中给定的数据有效。1. 代码填空（满分2分）在A B C D E F 六人中随机抽取3人中奖，要求中奖人不能重复。请完善以下代码：public class MyTestpublic static void main(String args)Vector a = new Vector();for(char i=A; i<=F; i+) a.add("" + i);for(int k=0; k<3; k+)int d = _;System.out.println(a.remove(d);int d = (int) (6-1-k)* Math.random();2. 代码填空（满分3分）不同进制的数值间的转换是软件开发中很可能会遇到的常规问题。下面的代码演示了如何把键盘输入的3进制数字转换为十进制。试完善之。BufferedReader br = new BufferedReader(new InputStreamReader(System.in);String s = br.readLine();int n = 0;for(int i=0; i<s.length(); i+)char c = s.charAt(i);if(c<0 | c > 2) throw new RuntimeException("Format error");n = _;System.out.println(n);(int) (n+(c-0)*Math.pow(3, (s.length()-i-1);3. 代码填空（满分4分）有如下程序，完成的功能为：找出数组中的最大元素。请填写程序的中空白，使程序运行正确。public class test public static void main(String args) int array=0,34,67,90,21,-9,98,1000,-78;System.out.println(new test().findMax (array, 0);public int findMax(int array,int index)if(array=null | array.length=0)return 0;int max=array0;if(index<array.length-1) max=_if(max<arrayindex) max= arrayindex;return max;max=findMax(array, index+1);4. 代码填空（满分5分）电视台开宝箱节目：打进电话的人可以开启一个宝箱。箱子中有一件礼品。礼品是iphone的机率为1/12；是mp3 的机率为1/5；是洗衣粉的机率为1/2；剩余是KFC优惠券。每次打进电话，宝箱会重置。以下程序模拟了该抽奖过程。请填写缺失的部分。public static void main(String args) int i = (int) Math.random() * _;if (i < 5) System.out.println("恭喜中了：iphone手机");else if (i < 17) System.out.println("恭喜中了：mp3"); else if (i < 47) System.out.println("恭喜中了：洗衣粉"); else System.out.println("恭喜中了：KFC优惠券");605. 代码填空（满分6分）下列代码求出一个二进制串中连续的1或连续的0出现的最大次数。请填缺失代码。例如：s = “101100111100011”则返回：4又例如：s=”0111100000”则返回：5public static int getMaxContinuity(String s)int max_1 = 0; int max_0 = 0; int n_1 = 0; / 当前1连续的次数int n_0 = 0; / 当前0连续的次数for(int i=0; i<s.length(); i+)if(s.charAt(i)=0)n_0+;_;elsen_1+;_;if(n_1 > max_1) max_1 = n_1;if(n_0 > max_0) max_0 = n_0;return max_1>max_0? max_1 : max_0);n_1=0;n_0=0;6. 代码填空（满分9分）下列代码把16进制表示的串转换为3进制表示的串。试完善之。例如：x=“5”则返回：“12”又例如：x=”F”则返回：“120”private static int getRealValue(char x)if(x>=0 && x<=9) return x-0;if(x>=a && x<=f) return x-a+10;if(x>=A && x<=F) return x-A+10;return 0;public static String jin_zhi_16_3(String x)int n = 0; / 累加真值for(int i=0; i<x.length(); i+)n = _ + getRealValue(x.charAt(i); / 填空String t = ""for(;)if(n=0) break;t = (n % 3) + t; _; / 填空return t;n n=n/3;7. 代码设计（满分5分）625这个数字很特别，625的平方等于390625，刚好其末3位是625本身。除了625，还有其它的3位数有这个特征吗？请编写程序，寻找所有这样的3位数：它的平方的末3位是这个数字本身。输出结果中，从小到大，每个找到的数字占一行。比如那个625就输出为：625代码设计（满分11分）考虑方程式：a3 + b3 = c3 + d3其中：“”表示乘方。a、b、c、d是互不相同的小于30的正整数。这个方程有很多解。比如：a = 1，b=12，c=9，d=10 就是一个解。因为：1的立方加12的立方等于1729，而9的立方加10的立方也等于1729。当然，a=12，b=1，c=9，d=10 显然也是解。如果不计abcd交换次序的情况，这算同一个解。你的任务是：找到所有小于30的不同的正整数解。把a b c d按从小到大排列，用逗号分隔，每个解占用1行。比如，刚才的解输出为：static void calculate() for (int i = 100; i < 10000; i+) int j = i * i;String st = String.valueOf(j);if (Integer.valueOf(st.substring(st.length() - 3) = i) System.out.println(i);1,9,10,12不同解间的顺序可以不考虑。static void calculateAnswer() for (int i = 1; i < 30; i+) for (int j = i; j < 30; j+) for (int k = 1; k < 30; k+) for (int l = k; l < 30; l+) if (Math.pow(i, 3)+Math.pow(j, 3)=Math.pow(k, 3)+Math.pow(l, 3)output(i, j, k, l);private static void output(int i, int j, int k, int l) int num=i,j,k,l;Arrays.sort(num);for (int m = 0; m < num.length; m+) System.out.print(numm);if(m<num.length-1)System.out.print(","); elseSystem.out.println();8. 代码设计（满分18分）整数的分划问题。 如，对于正整数n=6，可以分划为： 6 5+1 4+2, 4+1+1 3+3, 3+2+1, 3+1+1+1 2+2+2, 2+2+1+1, 2+1+1+1+1 1+1+1+1+1+1+1 现在的问题是，对于给定的正整数n,编写算法打印所有划分。用户从键盘输入 n （范围110）程序输出该整数的所有划分。import java.util.Scanner;public class Mytest public void p(int t1) p2(t1, ""); private void p2(int t1, String t2) if(t2.equals("") System.out.println(t1); for (int i = 1; i <= t1 / 2; i+) if (t2.length() > 0) if (i<Integer.parseInt(t2.charAt(1)+"") continue; System.out.println(t1 - i) + "+" + i + t2); p2(t1 - i), "+" + i + t2); else System.out.println(t1 - i) + "+" + i); p2(t1 - i), "+" + i); public static void main(String args) Mytest x = new Mytest(); System.out.println("please input a number:"); Scanner s=new Scanner(System.in); int t1 = s.nextInt();x.p(t1); 9. 代码设计（满分20分）一个N位的十进制正整数，如果它的每个位上的数字的N次方的和等于这个数本身，则称其为花朵数。例如：当N=3时，153就满足条件，因为 13 + 53 + 33 = 153，这样的数字也被称为水仙花数（其中，“”表示乘方，53表示5的3次方，也就是立方）。当N=4时，1634满足条件，因为 14 + 64 + 34 + 44 = 1634。当N=5时，92727满足条件。实际上，对N的每个取值，可能有多个数字满足条件。程序的任务是：求N=21时，所有满足条件的花朵数。注意：这个整数有21位，它的各个位数字的21次方之和正好等于这个数本身。如果满足条件的数字不只有一个，请从小到大输出所有符合条件的数字，每个数字占一行。因为这个数字很大，请注意解法时间上的可行性。要求程序在3分钟内运行完毕。public class Main private static final int SIZE = 21;private int countArray = new int10; / 个数列表private int countSumArray = new int10; / 个数总数private BigInteger sumArray = new BigInteger10;/ 值总数private int offset = 0;/ 浮标/* * 设置当前浮标对应的个数，个数的总数，值总数 * * param num * 个数 */private void setValue(int num) countArrayoffset = num;if (offset = 0) countSumArrayoffset = num;sumArrayoffset = p(9 - offset).multiply(n(num); else countSumArrayoffset = countSumArrayoffset - 1 + num;sumArrayoffset = sumArrayoffset - 1.add(p(9 - offset).multiply(n(num);/* * 检验当前数据是否匹配 * * return */private boolean checkPersentArray() BigInteger minVal = sumArrayoffset;/ 当前已存在值BigInteger maxVal = sumArrayoffset.add(p(9 - offset).multiply(n(SIZE - countSumArrayoffset);/ 当前已存在值+可能存在的最大值/ 最小值匹配if (minVal.compareTo(MAX) > 0) return false;/ 最大值匹配if (maxVal.compareTo(MIN) < 0) return false;String minStr = minVal.compareTo(MIN) > 0 ? minVal.toString() : MIN.toString();String maxStr = maxVal.compareTo(MAX) < 0 ? maxVal.toString() : MAX.toString();/ 找到最小值与最大值间首部相同的部分int sameCountArray = new int10;for (int i = 0; i < SIZE; i+) char c;if (c = minStr.charAt(i) = maxStr.charAt(i) sameCountArrayc - 0 = sameCountArrayc - 0 + 1; else break;/ 判断如果相同部分有数据大于现在已记录的位数，返回falsefor (int i = 0; i <= offset; i+) if (countArrayi < sameCountArray9 - i) return false;/ 如果当前值的总数为SIZE位，那么判断该值是不是需要查找的值if (countSumArrayoffset = SIZE) String sumStr = sumArrayoffset.toString();BigInteger sum = ZERO;for (int i = 0; i < sumStr.length(); i+) sum = sum.add(p(sumStr.charAt(i) - 0);return sum.compareTo(sumArrayoffset) = 0;return true;/* * 退出循环，打印 * * return */private void success() System.out.println("find a match number:" + sumArrayoffset);/* * 将浮标指向下一位数 * * return */private void next() offset+;setValue(SIZE - countSumArrayoffset - 1);/* * * 回退浮标，找到最近的浮标，并减一 * * return */private boolean back() / 回退浮标，找到最近的浮标，并减一if (countArrayoffset = 0) while (countArrayoffset = 0) if (offset > 0) offset-; else return true;if (offset > 0) setValue(countArrayoffset - 1);return false; else return true;/* * 测试程序 * * param startValue * 测试匹配数中包含9的个数 * param startTime * 程序启动时间 */private void test(int startValue, long startTime) / 设置9的个数offset = 0;setValue(startValue);while (true) if (checkPersentArray() / 检查当前提交数据是否匹配/ 匹配且总数正好为SIZE的位数，那么就是求解的值if (countSumArrayoffset = SIZE) success();/ 总数不为SIZE，且当前值不在第10位（即不等于0）if (offset != 9) next();continue;/ 总数不为SIZE，且当前值在第10位。if (back() break; else if (back() break;System.out.println(Thread.currentThread() + " End,Spend time "+ (System.currentTimeMillis() - startTime) / 1000 + "s");/* * 主函数 */public static void main(String args) final long startTime = System.currentTimeMillis();int s = MAX.divide(p(9).intValue();for (int i = 0; i <= s; i+) / new Main().test(i, startTime);/ 启动十个线程同时运算final int startValue = i;new Thread(new Runnable() public void run() new Main().test(startValue, startTime);).start();private static final BigInteger ZERO = new BigInteger("0");private static final BigInteger MIN;private static final BigInteger MAX;/* * 0-SIZE间的BigInteger */private static final BigInteger n(int i) return (BigInteger) ht.get("n_" + i);/* * 0-9的次方的BigInteger */private static final BigInteger p(int i) return (BigInteger) ht.get("p_" + i);/* * 用于缓存BigInteger数据，并初始化0-SIZE间的BigInteger和0-9的次方的BigInteger */private static Hashtable<String, Object> ht = new Hashtable<String, Object>();static int s = SIZE < 10 ? 10 : SIZE;for (int i = 0; i <= s; i+) ht.put("n_" + i, new BigInteger(String.valueOf(i);for (int i = 0; i <= 10; i+) ht.put("p_" + i, new BigInteger(String.valueOf(i).pow(SIZE);MIN = n(10).pow(SIZE - 1);MAX = n(10).pow(SIZE).subtract(n(1);第 12/12 页