2011年全国软件大赛模拟题及参考答案（Java本科组）
非官方標注答案，如有不妥，請指出。
2011?模擬?java?本科
注意：
本套模擬題主要模擬命題形式與考核范圍。真實競賽題的數(shù)量、難度可能與此套模擬題有差異。
說明：
本試卷包含兩種題型：“代碼填空”與“程序設(shè)計”。
填空題要求參賽選手在弄清給定代碼工作原理的基礎(chǔ)上填寫缺失的部分，使得程序邏輯正確、完整。所填寫的代碼不多于一條語句（即不能出現(xiàn)分號）。
編程題要求選手設(shè)計的程序?qū)τ诮o定的輸入能給出正確的輸出結(jié)果。注意：在評卷時使用的輸入數(shù)據(jù)與試卷中給出的實例數(shù)據(jù)可能是不同的。選手的程序必須是通用的，不能只對試卷中給定的數(shù)據(jù)有效。
?
1.??????代碼填空（滿分2分）
在A B C D E F?六人中隨機抽取3人中獎，要求中獎人不能重復(fù)。請完善以下代碼：
public class MyTest
{
????public 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 = ____________________________;
?(new Random()).nextInt(a.size());
????????????System.out.println(a.remove(d));
????????}
????}
}
?
2.??????代碼填空（滿分3分）
不同進制的數(shù)值間的轉(zhuǎn)換是軟件開發(fā)中很可能會遇到的常規(guī)問題。下面的代碼演示了如何把鍵盤輸入的3進制數(shù)字轉(zhuǎn)換為十進制。試完善之。
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 = ______________________;?3*n+(c-'0')
}
System.out.println(n);
3.??????代碼填空（滿分4分）
有如下程序，完成的功能為：找出數(shù)組中的最大元素。請?zhí)顚懗绦虻闹锌瞻?#xff0c;使程序運行正確。
?
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=array[0];
????????if(index<array.length-1)
????????{
?????????????max=____________________?findMax(array,index+1);
????????}
????????if(max<array[index]) max= array[index];
???
????????return max;
????}
}
?
4.??????代碼填空（滿分5分）
電視臺開寶箱節(jié)目：打進電話的人可以開啟一個寶箱。箱子中有一件禮品。禮品是iphone的機率為1/12；是mp3?的機率為1/5；是洗衣粉的機率為1/2；剩余是KFC優(yōu)惠券。
???????每次打進電話，寶箱會重置。
???????以下程序模擬了該抽獎過程。請?zhí)顚懭笔У牟糠帧?/p>
????public static void main(String[] args)
{
????????int i = (int) Math.random() * _____________;?60
????????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優(yōu)惠券");
????????}
????}
?
5.??????代碼填空（滿分6分）
下列代碼求出一個二進制串中連續(xù)的1或連續(xù)的0出現(xiàn)的最大次數(shù)。請?zhí)钊笔Тa。
例如：s = “101100111100011”
則返回：4
又例如：s=”0111100000”
則返回：5
public static int getMaxContinuity(String s)
{
????????int max_1 = 0;?
????????int max_0 = 0;?????
????????int n_1 = 0;??//?當前1連續(xù)的次數(shù)
????????int n_0 = 0;??//?當前0連續(xù)的次數(shù)
???????
????????for(int i=0; i<s.length(); i++)
????????{
????????????if(s.charAt(i)=='0')
????????????{
????????????????n_0++;
????????????????________;?n_1=0
????????????}
????????????else
????????????{
????????????????n_1++;
????????????????_________;?n_0 = 0
????????????}
???????????
????????????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);
}
?
6.??????代碼填空（滿分9分）
?
下列代碼把16進制表示的串轉(zhuǎn)換為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));??//?填空?16*n
????????}
???????
???????
????????String t = "";
????????for(;;)
????????{
????????????if(n==0) break;
????????????t = (n % 3) + t;?
????????????_____________;??//?填空?n=n/3
????????}
???????
????????return t;
????}
?
7.??????代碼設(shè)計（滿分5分）
625這個數(shù)字很特別，625的平方等于390625，剛好其末3位是625本身。除了625，還有其它的3位數(shù)有這個特征嗎？
請編寫程序，尋找所有這樣的3位數(shù)：它的平方的末3位是這個數(shù)字本身。
輸出結(jié)果中，從小到大，每個找到的數(shù)字占一行。比如那個625就輸出為：
625
public class MyTest {
???????public static void main(String[] args) {
??????????????for(int i=100;i<1000;i++){
?????????????????????if(i*i%1000 == i){
????????????????????????????System.out.println(i);
?????????????????????}
??????????????}
???????}
}
8.??????代碼設(shè)計（滿分11分）
?
考慮方程式：a^3 + b^3 = c^3 + d^3
其中：“^”表示乘方。a、b、c、d是互不相同的小于30的正整數(shù)。
這個方程有很多解。比如：
a = 1，b=12，c=9，d=10?就是一個解。因為：1的立方加12的立方等于1729，而9的立方加10的立方也等于1729。
當然，a=12，b=1，c=9，d=10?顯然也是解。
如果不計abcd交換次序的情況，這算同一個解。
你的任務(wù)是：找到所有小于30的不同的正整數(shù)解。把a b c d按從小到大排列，用逗號分隔，每個解占用1行。比如，剛才的解輸出為：
1,9,10,12
不同解間的順序可以不考慮。
public class MyTest {
???????public static void main(String[] args) {
??????????????for(int a=1;a<=26;a++){
?????????????????????for(int b=a+1;b<=27;b++){
????????????????????????????for(int c=b+1;c<=28;c++){
???????????????????????????????????for(int d=c+1;d<=29;d++){
??????????????????????????????????????????if(a*a*a+d*d*d==b*b*b+c*c*c){
?????????????????????????????????????????????????System.out.println(a+","+b+","+c+","+d);
??????????????????????????????????????????}
???????????????????????????????????}
????????????????????????????}
?????????????????????}
??????????????}
???????}
}
9.??????代碼設(shè)計（滿分18分）
整數(shù)的分劃問題。
如，對于正整數(shù)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
現(xiàn)在的問題是，對于給定的正整數(shù)n,編寫算法打印所有劃分。
用戶從鍵盤輸入?n?（范圍1~10）
程序輸出該整數(shù)的所有劃分。
?
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
?
public class MyTest {
???????public static void main(String[] args) {
??????????????Scanner in = new Scanner(System.in);
??????????????int x = in.nextInt();
??????????????List expressions[] = new List[x];
??????????????for(int i=1;i<=x;i++){
?????????????????????if(i==1){
????????????????????????????expressions[i-1] = new ArrayList();
????????????????????????????expressions[i-1].add("1");
?????????????????????}else{
????????????????????????????expressions[i-1] = new ArrayList();
????????????????????????????expressions[i-1].add(String.valueOf(i));
????????????????????????????//expressions[i-1].add(String.valueOf(i-1)+"+1");
????????????????????????????for(int j=i-1;j>=i/2;j--){
???????????????????????????????????for(int k=0;k<expressions[j-1].size();k++){
??????????????????????????????????????????//?原來的表達式
??????????????????????????????????????????String str1=(String)expressions[j-1].get(k);
??????????????????????????????????????????//?排序后的表達式
??????????????????????????????????????????String str2=process(str1+"+"+(i-j));
??????????????????????????????????????????//?查找是否已經(jīng)存在
??????????????????????????????????????????boolean b=false;
??????????????????????????????????????????for(int kk=0;kk<expressions[i-1].size();kk++){
?????????????????????????????????????????????????if(expressions[i-1].get(kk).toString().equals(str2)){
????????????????????????????????????????????????????????b = true;
????????????????????????????????????????????????????????break;
?????????????????????????????????????????????????}
??????????????????????????????????????????}
??????????????????????????????????????????if(!b){
?????????????????????????????????????????????????expressions[i-1].add(str2);
??????????????????????????????????????????}
???????????????????????????????????}
????????????????????????????}
?????????????????????}
??????????????}
?????????????
?????????????????????Collections.sort(expressions[x-1]);
?????????????????????String temp=null;
?????????????????????for(int i=expressions[x-1].size()-1;i>=0;i--){
????????????????????????????String value = expressions[x-1].get(i).toString();
????????????????????????????if(temp==null){
???????????????????????????????????System.out.print(value);
???????????????????????????????????temp = value.substring(0,1);
????????????????????????????}else{
???????????????????????????????????if(value.startsWith(temp)){
??????????????????????????????????????????System.out.print(",");
???????????????????????????????????}else{
??????????????????????????????????????????System.out.println();
??????????????????????????????????????????temp = value.substring(0,1);
???????????????????????????????????}
???????????????????????????????????System.out.print(value);
????????????????????????????}
?????????????????????}
?????????????
???????}
???????/*
????????*?調(diào)整順序，例如?3+1+2+1?調(diào)整后?3+2+1+1
????????*/
???????static String process(String exp){
??????????????exp = exp.replace("+"," ");
??????????????String str[] = exp.split(" ");
??????????????Arrays.sort(str);
??????????????StringBuffer sb = new StringBuffer();
??????????????for(int i=str.length-1;i>=0;i--){
?????????????????????sb.append(str[i]+"+");
??????????????}
??????????????sb.deleteCharAt(sb.length()-1);
??????????????return sb.toString();
???????}
??????
}
10.?代碼設(shè)計（滿分20分）
一個N位的十進制正整數(shù)，如果它的每個位上的數(shù)字的N次方的和等于這個數(shù)本身，則稱其為花朵數(shù)。
例如：
當N=3時，153就滿足條件，因為?1^3 + 5^3 + 3^3 = 153，這樣的數(shù)字也被稱為水仙花數(shù)（其中，“^”表示乘方，5^3表示5的3次方，也就是立方）。
當N=4時，1634滿足條件，因為?1^4 + 6^4 + 3^4 + 4^4 = 1634。
當N=5時，92727滿足條件。
實際上，對N的每個取值，可能有多個數(shù)字滿足條件。
?
程序的任務(wù)是：求N=21時，所有滿足條件的花朵數(shù)。注意：這個整數(shù)有21位，它的各個位數(shù)字的21次方之和正好等于這個數(shù)本身。
如果滿足條件的數(shù)字不只有一個，請從小到大輸出所有符合條件的數(shù)字，每個數(shù)字占一行。因為這個數(shù)字很大，請注意解法時間上的可行性。要求程序在3分鐘內(nèi)運行完畢。
?
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;
import java.util.List;
?
public class ShuiXianHua {
??????
???????// 449177399146038697307 9-4 8-1 7-4 6-2 5-0 4-3 3-3 2-??1-2 0-2
???????// 128468643043731391252 9-1 8-2 7-1 6-2 5-1 4-3 3-4 2-3 1-3 0-1
???????/*
????????*?思路：如果從000...000(21個)到99...99(21個）進行遍歷，然后看21位數(shù)字的21次方之和是否等于這個數(shù)字本身，算法需要處理10的21次方，時間肯定不能滿足要求
????????*?所以要減少遍歷的次數(shù)，有些數(shù)字明顯不合適：
????????*?考慮：21個1，他們的21次方的和才21，所以肯定不合適，不可能到21位數(shù)。
????????*?考慮：21個2,2的21次方大概是200萬，再乘上21也才4000萬，10的7次方，
????????*?哪個數(shù)字必須出現(xiàn)呢？可以算一下，使用下面的test方法測試。從結(jié)果可以看出如果21位數(shù)字中不包含8和9是沒有辦法組成21數(shù)字的，如果沒有9則最少需要11個8，分這些情況考慮就可以了。
????????*/
???????public static void main(String[] args) {
??????????????//System.out.print(BigInteger.valueOf(10).pow(50).divide(BigInteger.valueOf(200)));
??????????????long l1 = System.nanoTime();
??????????????Date d1 = new Date();
??????????????// test();
??????????????List<State> allStates = new ArrayList<State>();
??????????????//?考慮9的情況
??????????????for(int i=1;i<=9;i++){
?????????????????????State newState = new State();
?????????????????????newState.sum = State.a21[9].multiply(BigInteger.valueOf(i));
?????????????????????newState.count = new int[11];
?????????????????????// Arrays.fill(newState.count,0);
?????????????????????newState.count[9] = i;
?????????????????????newState.count[10] = i;
?????????????????????newState.index = 8;
?????????????????????allStates.add(newState);
??????????????}
??????????????//?考慮8的情況
??????????????for(int i=10;i<=21;i++){
?????????????????????State newState = new State();
?????????????????????newState.sum = State.a21[8].multiply(BigInteger.valueOf(i));
?????????????????????newState.count = new int[11];
?????????????????????// Arrays.fill(newState.count,0);
?????????????????????newState.count[8] = i;
?????????????????????newState.count[10] = i;
?????????????????????newState.index = 7;
?????????????????????allStates.add(newState);
??????????????}
??????????????while(allStates.size()>0){
?????????????????????State tempState = allStates.get(allStates.size()-1);
//???????????????????if(tempState.count[9]==4 && tempState.count[8]==1 &&tempState.count[7]==4
//?????????????????????????????????&& tempState.count[6]==2&& tempState.count[5]==0&& tempState.count[4]==3
//?????????????????????????????????&& tempState.count[3]==3){
//??????????????????????????System.out.println("true");
//???????????????????}
?????????????????????// System.out.println(allStates.size()+"-----"+tempState.index);
?????????????????????if(check(tempState)){
????????????????????????????List<State> tt = tempState.nextState();
????????????????????????????allStates.remove(allStates.size()-1);
????????????????????????????allStates.addAll(tt);
?????????????????????}else{
????????????????????????????allStates.remove(allStates.size()-1);
?????????????????????}
??????????????}
??????????????Date d2 = new Date();
??????????????long l2 = System.nanoTime();
??????????????System.out.println((d2.getTime()-d1.getTime()));
??????????????System.out.println((l2-l1)/1000);
???????}
??????
???????//?需要繼續(xù)處理返回true，否則返回false
???????public static boolean check(State state){
??????????????if(state.count[10]>21){
?????????????????????return false;
??????????????}
??????????????if(state.count[10] == 21){
?????????????????????String result = state.sum.toString();
?????????????????????if(result.length()!=21)
????????????????????????????return false;
?????????????????????int tempCount[] = new int[10];
?????????????????????// Arrays.fill(tempCount,0);
?????????????????????for(int i=0;i<21;i++){
????????????????????????????tempCount[result.charAt(i)-'0'] = tempCount[result.charAt(i)-'0']+1;
?????????????????????}
?????????????????????for(int i=0;i<10;i++){
????????????????????????????if(tempCount[i]!=state.count[i]){ //?錯誤解
???????????????????????????????????return false;
????????????????????????????}
?????????????????????}
?????????????????????System.out.println(result);
?????????????????????return false;
??????????????}
?
??????????????return true;
???????}
??????
???????public static void test(){
??????????????BigInteger max = BigInteger.valueOf(10).pow(21).subtract(BigInteger.valueOf(1));
??????????????BigInteger min = BigInteger.valueOf(10).pow(20);
??????????????for(int i=1;i<10;i++){
?????????????????????BigInteger temp = BigInteger.valueOf(i).pow(21);
?????????????????????int count1 = max.divide(temp).intValue();
?????????????????????int count2 = min.subtract(BigInteger.valueOf(1)).divide(temp).intValue()+1;
?????????????????????System.out.println(i+":最多需要"+count1+"個，最少需要"+count2+"個");
??????????????}
???????}
???????/*
????????*?運行結(jié)果：
????????*
1:最多需要-559939585個，最少需要1661992960個
2:最多需要1299066612個，最少需要988900121個
3:最多需要1109785847個，最少需要969972044個
4:最多需要227373675個，最少需要22737368個
5:最多需要2097151個，最少需要209716個
6:最多需要45585個，最少需要4559個
7:最多需要1790個，最少需要180個
8:最多需要108個，最少需要11個
9:最多需要9個，最少需要1個
????????*/
??????
??????
}
//?先考慮9，然后考慮8，然后...，state是中間的一個臨時情況
class State{
???????//?最大值和最小值
???????static BigInteger max = BigInteger.valueOf(10).pow(21).subtract(BigInteger.valueOf(1));
???????//?記錄0..9的21次方
???????static BigInteger a21[] = new BigInteger[10];
???????static{
??????????????for(int i=0;i<10;i++){
?????????????????????a21[i] = BigInteger.valueOf(i).pow(21);
??????????????}
???????}
??????
???????//?記錄各位數(shù)字的21次方的和
???????BigInteger sum ;
???????//?記錄各位數(shù)字出現(xiàn)的次數(shù)，最后一個單元記錄所有的數(shù)字的個數(shù)
???????int count[] = new int[11];
???????//?記錄需要處理的數(shù)字，從9開始處理到0
???????int index;
?
???????//?根據(jù)當前情況，考慮下一層可能的情況，例如9個9的情況下，8有哪些可能
???????List<State> nextState(){
??????????????List<State> states = new ArrayList<State>();
??????????????if(index==0){
?????????????????????State newState = new State();
?????????????????????newState.sum = sum.add(BigInteger.valueOf(0));
?????????????????????newState.count = Arrays.copyOf(count,11);
?????????????????????newState.count[index] = 21-newState.count[10];
?????????????????????newState.count[10] = 21;
?????????????????????newState.index = -1;
?????????????????????states.add(newState);
?????????????????????return states;
??????????????}
??????????????int maxCount = max.subtract(sum).divide(a21[index]).intValue();
??????????????if(maxCount>21-count[10] || maxCount<0){
?????????????????????maxCount = 21-count[10];
??????????????}
??????????????// int maxCount = 21-count[10];
??????????????//?創(chuàng)建可能的情況
??????????????for(int i=0;i<maxCount;i++){
//???????????????????if(a21[index].multiply(BigInteger.valueOf(i)).add(sum).compareTo(max)==1)
//??????????????????????????continue;
?????????????????????State newState = new State();
?????????????????????newState.sum = sum.add(a21[index].multiply(BigInteger.valueOf(i)));
?????????????????????newState.count = Arrays.copyOf(count,11);
?????????????????????newState.count[index] = newState.count[index]+i;
?????????????????????newState.count[10] = newState.count[10]+i;
?????????????????????newState.index = index-1;
?????????????????????process(newState);
?????????????????????states.add(newState);
??????????????}
??????????????return states;
???????}
??????
???????/*
????????*?為了提高效率，如果不處理，運行時間能夠增加6、7倍。
????????*/
???????static void process(State state){
??????????????if(state.index<9){
?????????????????????BigInteger maxSum=state.sum.add(State.a21[state.index].multiply(BigInteger.valueOf(21-state.count[10])));
?????????????????????String result = state.sum.toString();
?????????????????????String maxResult = maxSum.toString();
?????????????????????int tempCount[] = new int[10];
?????????????????????// Arrays.fill(tempCount,0);
?????????????????????if(result.length()==maxResult.length()){
????????????????????????????for(int i=0;i<result.length();i++){
???????????????????????????????????char c1=result.charAt(i);
???????????????????????????????????char c2=maxResult.charAt(i);
???????????????????????????????????if(c1-c2==0){
??????????????????????????????????????????tempCount[c1-'0']=tempCount[c1-'0']+1;
???????????????????????????????????}else{
??????????????????????????????????????????break;
???????????????????????????????????}
????????????????????????????}
????????????????????????????for(int i=0;i<=state.index;i++){
???????????????????????????????????int sub = tempCount[i]-state.count[i];
???????????????????????????????????if(sub>0){
??????????????????????????????????????????state.sum = state.sum.add(State.a21[i].multiply(BigInteger.valueOf(sub)));
??????????????????????????????????????????state.count[i] = state.count[i]+sub;
??????????????????????????????????????????state.count[10] = state.count[10]+sub;
???????????????????????????????????}
????????????????????????????}
?????????????????????}
??????????????}
???????}
}
我的筆記本（09年）上運行時間小于3秒，臺式機（06年）不到7秒，使用遞歸，代碼能夠?qū)懙母僖恍?/p>
?
總結(jié)
以上是生活随笔為你收集整理的2011年全国软件大赛模拟题及参考答案（Java本科组）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 账户系统db服务器为创建快照,Mysql
- 下一篇： 2011年全国软件大赛模拟题及参考答案（