148
2011年全國軟件大賽模擬題及參考答案（Java本科組）
非官方標注答案，如有不妥，請指出。
2011 模擬 java 本科
注意：
本套模擬題主要模擬命題形式與考核範圍。真實競賽題的數量、難度可能與此套模擬題有差異。
說明：
本試卷包含兩種題型：“代碼填空”與“程序設計”。
填空題要求參賽選手在弄清給定代碼工作原理的基礎上填寫缺失的部分，使得程序邏輯正確、完整。所填寫的代碼不多於一條語句（即不能出現分號）。
編程題要求選手設計的程序對於給定的輸入能給出正確的輸出結果。注意：在評卷時使用的輸入數據與試卷中給出的實例數據可能是不同的。選手的程序必須是通用的，不能隻對試卷中給定的數據有效。
1. 代碼填空（滿分2分）
在A B C D E F 六人中隨機抽取3人中獎，要求中獎人不能重複。請完善以下代碼：
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分）
不同進製的數值間的轉換是軟件開發中很可能會遇到的常規問題。下麵的代碼演示了如何把鍵盤輸入的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 = ______________________; 3*n+(c-'0')
}
System.out.println(n);
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=array[0];
if(index<array.length-1)
{
max=____________________ findMax(array,index+1);
}
if(max<array[index]) max= array[index];
return max;
}
}
4. 代碼填空（滿分5分）
電視台開寶箱節目：打進電話的人可以開啟一個寶箱。箱子中有一件禮品。禮品是iphone的機率為1/12；是mp3 的機率為1/5；是洗衣粉的機率為1/2；剩餘是KFC優惠券。
每次打進電話，寶箱會重置。
以下程序模擬了該抽獎過程。請填寫缺失的部分。
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優惠券");
}
}
5. 代碼填空（滿分6分）
下列代碼求出一個二進製串中連續的1或連續的0出現的最大次數。請填缺失代碼。
例如：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連續的次數
int n_0 = 0; // 當前0連續的次數
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進製表示的串轉換為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. 代碼設計（滿分5分）
625這個數字很特別，625的平方等於390625，剛好其末3位是625本身。除了625，還有其它的3位數有這個特征嗎？
請編寫程序，尋找所有這樣的3位數：它的平方的末3位是這個數字本身。
輸出結果中，從小到大，每個找到的數字占一行。比如那個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. 代碼設計（滿分11分）
考慮方程式：a^3 + b^3 = c^3 + d^3
其中：“^”表示乘方。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行。比如，剛才的解輸出為：
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. 代碼設計（滿分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 （範圍1~10）
程序輸出該整數的所有劃分。
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));
// 查找是否已經存在
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);
}
}
}
/*
* 調整順序，例如 3+1+2+1 調整後 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. 代碼設計（滿分20分）
一個N位的十進製正整數，如果它的每個位上的數字的N次方的和等於這個數本身，則稱其為花朵數。
例如：
當N=3時，153就滿足條件，因為 1^3 + 5^3 + 3^3 = 153，這樣的數字也被稱為水仙花數（其中，“^”表示乘方，5^3表示5的3次方，也就是立方）。
當N=4時，1634滿足條件，因為 1^4 + 6^4 + 3^4 + 4^4 = 1634。
當N=5時，92727滿足條件。
實際上，對N的每個取值，可能有多個數字滿足條件。
程序的任務是：求N=21時，所有滿足條件的花朵數。注意：這個整數有21位，它的各個位數字的21次方之和正好等於這個數本身。
如果滿足條件的數字不隻有一個，請從小到大輸出所有符合條件的數字，每個數字占一行。因為這個數字很大，請注意解法時間上的可行性。要求程序在3分鍾內運行完畢。
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位數字的21次方之和是否等於這個數字本身，算法需要處理10的21次方，時間肯定不能滿足要求
* 所以要減少遍曆的次數，有些數字明顯不合適：
* 考慮：21個1，他們的21次方的和才21，所以肯定不合適，不可能到21位數。
* 考慮：21個2,2的21次方大概是200萬，再乘上21也才4000萬，10的7次方，
* 哪個數字必須出現呢？可以算一下，使用下麵的test方法測試。從結果可以看出如果21位數字中不包含8和9是沒有辦法組成21數字的，如果沒有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);
}
// 需要繼續處理返回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+"個");
}
}
/*
* 運行結果：
*
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);
}
}
// 記錄各位數字的21次方的和
BigInteger sum ;
// 記錄各位數字出現的次數，最後一個單元記錄所有的數字的個數
int count[] = new int[11];
// 記錄需要處理的數字，從9開始處理到0
int index;
// 根據當前情況，考慮下一層可能的情況，例如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];
// 創建可能的情況
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秒，使用遞歸，代碼能夠寫的更少一些。
最後更新：2017-04-03 22:15:30