2016年第七届蓝桥杯javaB组 试题 答案 解析
生活随笔
收集整理的這篇文章主要介紹了
2016年第七届蓝桥杯javaB组 试题 答案 解析
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
1.煤球數(shù)目
- 有一堆煤球，堆成三角棱錐形。具體：
- 第一層放1個(gè)，
- 第二層3個(gè)（排列成三角形），
- 第三層6個(gè)（排列成三角形），
- 第四層10個(gè)（排列成三角形），
- ....
- 如果一共有100層，共有多少個(gè)煤球？
- 請(qǐng)?zhí)畋硎久呵蚩倲?shù)目的數(shù)字。
- 注意：你提交的應(yīng)該是一個(gè)整數(shù)，不要填寫任何多余的內(nèi)容或說明性文字。
答案: 171700
?
2.生日蠟燭
- 某君從某年開始每年都舉辦一次生日party，并且每次都要吹熄與年齡相同根數(shù)的蠟燭。
- 現(xiàn)在算起來，他一共吹熄了236根蠟燭。
- 請(qǐng)問，他從多少歲開始過生日party的？
- 請(qǐng)?zhí)顚懰_始過生日party的年齡數(shù)。
- 注意：你提交的應(yīng)該是一個(gè)整數(shù)，不要填寫任何多余的內(nèi)容或說明性文字。
答案: 26
?
3.湊算式
B DEF A + --- + ------- = 10C GHI- 這個(gè)算式中A~I代表1~9的數(shù)字，不同的字母代表不同的數(shù)字。
- 比如:
- 6+8/3+952/714 就是一種解法，
- 5+3/1+972/486 是另一種解法。
- 這個(gè)算式一共有多少種解法?
答案: 29
?
4. 分小組
- 9名運(yùn)動(dòng)員參加比賽，需要分3組進(jìn)行預(yù)賽。
- 有哪些分組的方案呢？
- 我們標(biāo)記運(yùn)動(dòng)員為 A,B,C,... I
- 下面的程序列出了所有的分組方法。
仔細(xì)閱讀代碼，填寫劃線部分缺少的內(nèi)容。
答案: s + " " + (char)(i + 'A') + (char)(j + 'A') + (char)(k + 'A') + " " + remain(a)
?
5.抽簽
- X星球要派出一個(gè)5人組成的觀察團(tuán)前往W星。
- 其中：
- A國(guó)最多可以派出4人。
- B國(guó)最多可以派出2人。
- C國(guó)最多可以派出2人。
- ....
- 那么最終派往W星的觀察團(tuán)會(huì)有多少種國(guó)別的不同組合呢？
- 下面的程序解決了這個(gè)問題。
- 數(shù)組a[] 中既是每個(gè)國(guó)家可以派出的最多的名額。
- 程序執(zhí)行結(jié)果為：
仔細(xì)閱讀代碼，填寫劃線部分缺少的內(nèi)容。
答案: f(a, k + 1, n - i, s2);
?
6.方格填數(shù)
- 如下的10個(gè)格子
- 填入0~9的數(shù)字。要求：連續(xù)的兩個(gè)數(shù)字不能相鄰。
（左右、上下、對(duì)角都算相鄰） - 一共有多少種可能的填數(shù)方案？
- 請(qǐng)?zhí)顚懕硎痉桨笖?shù)目的整數(shù)。
這道題的遞歸策略類似八皇后問題, 也就說當(dāng)來到第一個(gè)格子后, 下一個(gè)要填的數(shù)不是連接著下一個(gè)位置的, 也就是說每個(gè)位置要填的數(shù)字來自于整個(gè)樣本, 而且要注意回溯, 保證其他遞歸過程沒有出錯(cuò).
public class Six {public static int[][] dp = new int[5][6];public static int[] arr = new int[10];public static int res = 0;public static void main(String[] args) {initDp();process(1, 2);System.out.println(res);}public static void process(int x, int y){if(x == 3 && y == 4){res++;return;}for(int n = 0; n <= 9; n++){if(arr[n] == 0 && canFill(x, y, n)){dp[x][y] = n;arr[n] = 1;if(y == 4){process(x + 1, 1);}else{process(x, y + 1);}arr[n] = 0;dp[x][y] = -11;}}}public static boolean canFill(int x, int y, int n){boolean ans = true;for(int i = -1; i <= 1; i++){for(int j = -1; j <= 1; j++){if(i == 0 && j == 0) continue;if(Math.abs(dp[x + i][y + j] - n) <= 1){ans = false;}}}return ans;}public static void initDp(){for(int i = 0; i < 5; i++){for(int j = 0; j < 6; j++){dp[i][j] = -11;}}} }答案: 1580
?
7.剪郵票
- 如【圖1.jpg】, 有12張連在一起的12生肖的郵票
- 現(xiàn)在你要從中剪下5張來，要求必須是連著的
- （僅僅連接一個(gè)角不算相連）
- 比如，【圖2.jpg】，【圖3.jpg】中，粉紅色所示部分就是合格的剪取。
- 請(qǐng)你計(jì)算，一共有多少種不同的剪取方法。
- 請(qǐng)?zhí)顚懕硎痉桨笖?shù)目的整數(shù)。
首先通過5層for循環(huán)枚舉選出5數(shù), 難點(diǎn)在于判斷這5個(gè)數(shù)是否是相連的, 可以利用圖中標(biāo)有編號(hào)的特性進(jìn)行判斷. 可以直觀地看到一個(gè)數(shù)上面聯(lián)通的數(shù)可-4得到, 下面的數(shù)可+4得到, 同理左邊是-1, 右邊是+1. 但是, 有特殊情況, 比如4+1為5, 理論上4的右邊是5, 但是由于換行的原因, 4和5不是聯(lián)通的. 但是這個(gè)方法是好的, 可以通過修改圖中的編號(hào)繼續(xù)使用這個(gè)方法.
可以把圖改成: 1 2 3 4 6 7 8 9 10 11 12 13 public class Seven {public static int res = 0;public static int[] arr = {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14};public static int[] p = new int[5];public static boolean[] visit = new boolean[5];public static int[] c = {5, -5, 1, -1};public static void main(String[] args) {for(int a = 0; a < 12; a++){for(int b = a + 1; b < 12; b++){for(int c = b + 1; c < 12; c++){for(int d = c + 1; d < 12; d++){for(int e = d + 1; e < 12; e++){p[0] = arr[a];p[1] = arr[b];p[2] = arr[c];p[3] = arr[d];p[4] = arr[e];process(0);boolean flag = true;for(int i = 0; i < 5; i++){if(!visit[i]){flag = false;}}if(flag){res++;}cleanVisit();}}}}}System.out.println(res);}public static void process(int n){for(int i = 0; i < 4; i++){int t = p[n] + c[i];if(t < 1 || t > 14 || t == 5 || t == 10){continue;}for(int j = 0; j < 5; j++){if(!visit[j] && p[j] == t){visit[j] = true;process(j);}}}}public static void cleanVisit(){for(int i = 0; i < 5; i++){visit[i] = false;}} }答案: 116
?
8.四平方和
- 四平方和定理，又稱為拉格朗日定理：
- 每個(gè)正整數(shù)都可以表示為至多4個(gè)正整數(shù)的平方和。
- 如果把0包括進(jìn)去，就正好可以表示為4個(gè)數(shù)的平方和。
- 比如：
- 5 = 0^2 + 0^2 + 1^2 + 2^2
- 7 = 1^2 + 1^2 + 1^2 + 2^2
- （^符號(hào)表示乘方的意思）
- 對(duì)于一個(gè)給定的正整數(shù)，可能存在多種平方和的表示法。
- 要求你對(duì)4個(gè)數(shù)排序：
- 0 <= a <= b <= c <= d
- 并對(duì)所有的可能表示法按 a,b,c,d 為聯(lián)合主鍵升序排列，最后輸出第一個(gè)表示法
- 程序輸入為一個(gè)正整數(shù)N (N<5000000)
- 要求輸出4個(gè)非負(fù)整數(shù)，按從小到大排序，中間用空格分開
這道題是常規(guī)的暴力枚舉題, 難在如何降低時(shí)間復(fù)雜度跑過所有的用例, 如果a, b, c, d每個(gè)數(shù)都窮舉以便, 按照最大的輸入5000000, 每個(gè)數(shù)要枚舉的次數(shù)為10^3級(jí), 一共就是10^12. 太大了, 會(huì)超時(shí). 為了能減少次數(shù), 把枚舉分成兩半, 一半的數(shù)據(jù)是a * a + b * b, 這一半的數(shù)據(jù)用哈希表存儲(chǔ), 另外一半的數(shù)據(jù)是c * c + d * d = n - a * a + b * b. 這樣能把枚舉的規(guī)模縮小一半.
public class Eight {static HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();for(int c = 0; c * c <= n / 2; c++){for(int d = c; c * c + d * d <= n; d++){if(!map.containsKey(c * c + d * d)){map.put(c * c + d * d, c);}}}for(int a = 0; a * a <= n / 4; a++){for(int b = a; a * a + b * b <= n; b++){if(map.containsKey(n - a * a - b * b)){int c = map.get(n - a * a - b * b);int d = (int) Math.sqrt(n - a * a - b * b - c * c);System.out.println(a + " " + b + " " + c + " " + d);return;}}}}}?
9.取球博弈
- 兩個(gè)人玩取球的游戲。
- 一共有N個(gè)球，每人輪流取球，每次可取集合{n1,n2,n3}中的任何一個(gè)數(shù)目。
- 如果無法繼續(xù)取球，則游戲結(jié)束。
- 此時(shí)，持有奇數(shù)個(gè)球的一方獲勝。
- 如果兩人都是奇數(shù)，則為平局。
- 假設(shè)雙方都采用最聰明的取法，
- 第一個(gè)取球的人一定能贏嗎？
- 試編程解決這個(gè)問題。
- 輸入格式：
- 第一行3個(gè)正整數(shù)n1 n2 n3，空格分開，表示每次可取的數(shù)目 (0<n1,n2,n3<100)
- 第二行5個(gè)正整數(shù)x1 x2 ... x5，空格分開，表示5局的初始球數(shù)(0<xi<1000)
- 輸出格式：
- 一行5個(gè)字符，空格分開。分別表示每局先取球的人能否獲勝。
- 能獲勝則輸出+，
- 次之，如有辦法逼平對(duì)手，輸出0，
- 無論如何都會(huì)輸，則輸出-
思路
- 首先要明確每一局的情況, 假設(shè)一局有x個(gè)球, 取球情況的數(shù)組為n.
- 在每一局中, 某一方取球都會(huì)根據(jù)取球情況數(shù)組進(jìn)行試探, 如上圖.
- 在每次遞歸中, 需要的參數(shù)有當(dāng)前剩下的球, 我摸的球數(shù), 對(duì)手摸的球數(shù).
- 如何才能判斷一局的勝負(fù)? 在所有情況中, 只要對(duì)手輸過, 結(jié)果就是贏; 如果對(duì)手沒輸過, 但是平過, 結(jié)果就是平; 否則, 結(jié)果就是輸. (因?yàn)轭}目條件: 雙方都采取最聰明的辦法)
- 最大的難點(diǎn)在于在于遞歸的過程中, 不是每次都是我摸, 而是我摸一次, 對(duì)手摸一次, 這里恰好就是這種類型遞歸的魅力所在.
- 具體落實(shí)到代碼中
優(yōu)化
- 作為編程大題, 如果不優(yōu)化是過不了極端的數(shù)據(jù)樣本的.
- 這題可以用數(shù)組記錄重復(fù)出現(xiàn)的情況, 進(jìn)行記憶型遞歸, 用空間換時(shí)間.
- 問題來了: me和you是不斷交換的, 怎樣才算是一種情況?
- 在base case中, 最后決定輸贏的, 不是你我手上有多少個(gè)球, 而是你我的球數(shù)的奇偶情況, 所以我們把每一種情況記錄為: 剩余的球數(shù)和雙方球數(shù)的奇偶情況.
?
10.壓縮變換
- 小明最近在研究壓縮算法。
- 他知道，壓縮的時(shí)候如果能夠使得數(shù)值很小，就能通過熵編碼得到較高的壓縮比。
- 然而，要使數(shù)值很小是一個(gè)挑戰(zhàn)。
- 最近，小明需要壓縮一些正整數(shù)的序列，這些序列的特點(diǎn)是，后面出現(xiàn)的數(shù)字很大可能是剛出現(xiàn)過不久的數(shù)字。對(duì)于這種特殊的序列，小明準(zhǔn)備對(duì)序列做一個(gè)變換來減小數(shù)字的值。
- 變換的過程如下：
- 從左到右枚舉序列，每枚舉到一個(gè)數(shù)字，如果這個(gè)數(shù)字沒有出現(xiàn)過，剛將數(shù)字變換成它的相反數(shù)，如果數(shù)字出現(xiàn)過，則看它在原序列中最后的一次出現(xiàn)后面（且在當(dāng)前數(shù)前面）出現(xiàn)了幾種數(shù)字，用這個(gè)種類數(shù)替換原來的數(shù)字。
- 比如，序列(a1, a2, a3, a4, a5)=(1, 2, 2, 1, 2)在變換過程為：
- a1: 1未出現(xiàn)過，所以a1變?yōu)?1；
- a2: 2未出現(xiàn)過，所以a2變?yōu)?2；
- a3: 2出現(xiàn)過，最后一次為原序列的a2，在a2后、a3前有0種數(shù)字，所以a3變?yōu)?；
- a4: 1出現(xiàn)過，最后一次為原序列的a1，在a1后、a4前有1種數(shù)字，所以a4變?yōu)?；
- a5: 2出現(xiàn)過，最后一次為原序列的a3，在a3后、a5前有1種數(shù)字，所以a5變?yōu)?。
- 現(xiàn)在，給出原序列，請(qǐng)問，按這種變換規(guī)則變換后的序列是什么。
按照題目的思路, 使用HashMap記錄數(shù)的下標(biāo), 使用HashSet記錄不同種的的數(shù)字, 時(shí)間復(fù)雜度O(N^2), 暴力做法能得30分.
public class Ten {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();long[] arr = new long[n];for(int i = 0; i < arr.length; i++){arr[i] = sc.nextInt();}long[] former = Arrays.copyOf(arr, arr.length);HashMap<Long, Integer> map = new HashMap<Long, Integer>();for(int i = 0; i < arr.length; i++){if(!map.containsKey(arr[i])){map.put(arr[i], i);arr[i] = -arr[i];}else{int types = getTypes(map.get(arr[i]), i, former);map.put(arr[i], i);arr[i] = types;}}for(int i = 0; i < arr.length; i++){System.out.print(arr[i] + " ");}}public static int getTypes(int begin, int last, long[] former){HashSet<Long> set = new HashSet<Long>();int index = begin + 1;while(index < last){set.add(former[index++]);}return set.size();} }優(yōu)化
- 未完待續(xù)...
轉(zhuǎn)載于:https://www.cnblogs.com/tanshaoshenghao/p/10542723.html
《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀總結(jié)
以上是生活随笔為你收集整理的2016年第七届蓝桥杯javaB组 试题 答案 解析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： I/O：OutputStream
- 下一篇： 个人简介2