2015年第6届蓝桥杯Java B组省赛试题解析
1、三角形面积
如图1所示。图中的所有小方格面积都是1。
那么，图中的三角形面积应该是多少呢？
请填写三角形的面积。不要填写任何多余内容或说明性文字。
image.png
计算方法：
8 * 8 - （8 * 2 / 2 + 6 * 4 / 2 + 8 * 4 / 2）= 64 - (8+ 12 + 16) =64-36=28
2、立方变自身
观察下面的现象,某个数字的立方，按位累加仍然等于自身。
1^3 = 1
8^3 = 512 5+1+2=8
17^3 = 4913 4+9+1+3=17
...
请你计算包括1,8,17在内，符合这个性质的正整数一共有多少个？
请填写该数字，不要填写任何多余的内容或说明性的文字。
public class CubeEqual {
public static void main(String[] args) {
int count = 0;
for (int i = 1; i < 100; i++) {
int s = i * i * i;
if (i == fun(s)) {
System.out.println("i = " + i);
System.out.println("s = " + s);
System.out.println("fun(s) = " + fun(s));
count++;
}
}
System.out.println("count = " + count);
}
static int fun(int a) {
if (a < 10) {
return a;
}
return fun(a / 10) + a % 10;
}
}
答案：6
3、三羊献瑞
观察下面的加法算式
image.png
其中，相同的汉字代表相同的数字，不同的汉字代表不同的数字。
请你填写“三羊献瑞”所代表的4位数字（答案唯一），不要填写任何多余内容。
容易推测得到：
三 => 1
羊 => 0
祥 => 9
羊等于0，各个汉字不同，所以：生=瑞+1；
由于
生+献=瑞 即： 瑞+1 +献=瑞 => 献等于8，或9，但是已经有祥等于9了，所献等于8.
辉和瑞相加一定大与等于10，由以上推出的数字可得：
辉，瑞 在[5,7 ] , [6, 7]两种可能之中。
大约四种情况：代入等式去试一下，就能得出答案。
答案：1085
4、循环节长度
两个整数做除法，有时会产生循环小数，其循环部分称为：循环节。
比如，11/13=6=>0.846153846153..... 其循环节为[846153] 共有6位。
下面的方法，可以求出循环节的长度。
请仔细阅读代码，并填写划线部分缺少的代码。
public static int f(int n, int m)
{
n = n % m;
Vector v = new Vector();
for(;;)
{
v.add(n);
n *= 10;
n = n % m;
if(n==0) return 0;
if(v.indexOf(n)>=0) _________________________________ ; //填空
}
}
注意，只能填写缺少的部分，不要重复抄写已有代码。不要填写任何多余的文字。
答案: return v.size()-v.index(n)
这一题非常容易漏掉v.index(n); 主要的原因是，比如20/7，和200/7 的循环节其实是一样的，但是v.size()是不一样的。
5、 九数组分数
1,2,3…9 这九个数字组成一个分数，其值恰好为1/3，如何组法？
下面的程序实现了该功能，请填写划线部分缺失的代码。
public class A
{
public static void test(int[] x)
{
int a = x[0]*1000 + x[1]*100 + x[2]*10 + x[3];
int b = x[4]*10000 + x[5]*1000 + x[6]*100 + x[7]*10 + x[8];
if(a*3==b) System.out.println(a + " " + b);
}
public static void f(int[] x, int k)
{
if(k>=x.length){
test(x);
return;
}
for(int i=k; i<x.length; i++){
{int t=x[k]; x[k]=x[i]; x[i]=t;}
f(x,k+1);
_______________________________________ // 填空
}
}
public static void main(String[] args)
{
int[] x = {1,2,3,4,5,6,7,8,9};
f(x,0);
}
}
咋一看，这一题好像很难，但是其实如果熟悉排列的写法，这题很简单。我们来看一下对一组数字进行排列的示例代码：
/**
* 该类主要用户打印排列
*
* @author yunqing_shui@163.com
*/
public class Main {
public static int count = 0;
public static void main(String[] args) {
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
per(a, 0, 4);
System.out.println(count);
}
public static void swapTwoNumber(int a[], int i, int j) {
if (i != j) {
a[i] ^= a[j];
a[j] ^= a[i];
a[i] ^= a[j];
}
}
/**
* @param a
* @param index 数组的起始位置
* @param len 要排列的长度
*/
public static void per(int a[], int index, int len) {
if (index == len) {
print(a, len);
}
for (int i = index; i < len; i++) {
// 交换两个数
swapTwoNumber(a, index, i);
per(a, index + 1, len);
// 交换两个数
swapTwoNumber(a, index, i);
}
}
public static void print(int a[], int len) {
for (int i = 0; i < len; i++) {
System.out.print(a[i]);
}
count++;
System.out.println();
}
}
该题的题目意思很简单，由函数test(int[] x)得出，取出4个作为分子，取出五个作为分母。然后验证是否等于三分之一，所以本质上就是对9个数字作排列，前4个作为分子，后5个作为分母。那么分析到这里。就很简单了。我们对比以下排列的核心代码
for (int i = index; i < len; i++) {
// 交换两个数
swapTwoNumber(a, index, i);
per(a, index + 1, len);
// 交换两个数
swapTwoNumber(a, index, i);
}
for(int i=k; i<x.length; i++){
{int t=x[k]; x[k]=x[i]; x[i]=t;}
f(x,k+1);
_______________________________________ // 填空
}
就能得出横线部分就是交换数组中的两个数。
答案：{int t=x[k]; x[k]=x[i]; x[i]=t;}
6、加法变乘法
我们都知道：1+2+3+ … + 49 = 1225
现在要求你把其中两个不相邻的加号变成乘号，使得结果为2015
比如：
1+2+3+…+10 * 11+12+…+27*28+29+…+49 = 2015
就是符合要求的答案。
请你寻找另外一个可能的答案，并把位置靠前的那个乘号左边的数字提交（对于示例，就是提交10）。
注意：需要你提交的是一个整数，不要填写任何多余的内容。
这一题没有什么技术含量，暴力破解就行。
/**
*
* @author yunqing_shui@163.com
*/
public class Main6 {
public static void main(String[] args) {
int a[] = new int[49];
for (int i = 0; i < 49; i++) {
a[i] = i+1;
}
int b[] = new int[47];
for (int x = 0; x < 46; x++) {
for (int y = x + 2; y <= 48; y++) {
for (int i = 0, j = 0; i < 47 && j < 49; i++, j++) {
if (i == x || i == y) {
int s = a[j] * a[j + 1];
b[i] = s;
j++;
} else {
b[i] = a[j];
}
}
if (sum(b) == 2015) {
System.out.println("x = " + (x+1));
System.out.println("y = " + (y+2));
System.out.println("Arrays.toString(a) = " + Arrays.toString(a));
System.out.println("Arrays.toString(b) = " + Arrays.toString(b));
}
}
}
System.out.println("sum = " + sum(b));
}
public static int sum(int a[]) {
int s = 0;
for (int i = 0; i < a.length; i++) {
s += a[i];
}
return s;
}
}
答案：16
7、牌型种数
小明被劫持到X赌城，被迫与其他3人玩牌。
一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。
这时，小明脑子里突然冒出一个问题：
如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序，自己手里能拿到的初始牌型组合一共有多少种呢？
请填写该整数，不要填写任何多余的内容或说明文字。
在网上发现了dfs的方法，非常简洁
public class Seven3 {
public static int ans = 0;
static void dfs(int type, int sum) {
if (sum > 13) return;
if (type == 13) {
if (sum == 13) ans++;
return;
}
for (int i = 0; i < 5; i++) {
dfs(type + 1, sum + i);
}
}
public static void main(String[] args) {
dfs(0, 0);
System.out.println("ans = " + ans);
}
}
2、线性规划的解法
在网上看到有大神用线性规划来求解问题，佩服不已，代码简洁高效，贴出代码以供观摩。
public class Seven {
public static void main(String[] args) {
int[][] dp = new int[14][14];
dp[0][0] = 1;
for (int i = 1; i < 14; i++)
for (int j = 0; j < 14; j++)
for (int k = 0; k < 5; k++)
if (j + k <= 13)
dp[i][j + k] += dp[i - 1][j];
System.out.println(dp[13][13]);
}
}
还有另外一种写法：
public class Seven2 {
public static void main(String[] args) {
int dp[][] = new int[14][14];
dp[1][0] = dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = 1;
for (int i = 2; i <= 13; i++) {
for (int j = 0; j <= 13; j++) {
if (j - 4 >= 0) dp[i][j] += dp[i-1][j-4];
if (j - 3 >= 0) dp[i][j] += dp[i-1][j-3];
if (j - 2 >= 0) dp[i][j] += dp[i-1][j-2];
if (j - 1 >= 0) dp[i][j] += dp[i-1][j-1];
dp[i][j] += dp[i-1][j];
}
}
System.out.println(dp[13][13]);
}
}
主要的思路是：
假设牌是从1到13按顺序取的，dp[i][j]表示取到牌数为i的牌，j表示目前一共取了多少张牌。
比如d[3][4] ， 则i=3, j = 4 , 表示从A,2,3三种(i=3)牌中（每种4张，红桃、方块、黑桃、梅花）取出4（j=4）张 。
我们最重要的是确认递归方程：从第一张牌开始，每种牌都有5种可能：
1、这种牌取0个
2、这种牌取1个
3、这种牌取2个
4、这种牌取3个
5、这种牌取4个
首先我们需要推导出状态转换方程。
决策过程如下图：
决策过程
由上图我们看出:
dp[1][0] = dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = 1;
dp[2][0] = dp[1][0] =1 ;
image.png
由上图我们得到：
dp[2][1] = dp[1][0] +dp[1][1] ;
image.png
同样的对于dp[2][2]
dp[2][2] = dp[1][0] +dp[1][1]+dp[1][2] ;
image.png
dp[2][3] = dp[1][0] +dp[1][1]+dp[1][2]+d[1][3] ;
类似的：
dp[2][4] = dp[1][0] + dp[1][1] + dp[1][2] + dp[1][3] + d[1][4] ;
dp[2][5] = dp[1][1] + dp[1][2] + dp[1][3] + dp[1][4] + d[1][5] ;
说明：dp[1][5]为不可能事件，所以为0. dp[1][5]就是一种牌里取出5个的意思。
由此我们归纳得出状态转移方程如下（没有加限制条件）：
状态转移方程
得出转移方程，我们就知道如何决策了。d[13][13]即13种牌，取出13张的总数。
回头看一看代码，基本明白了作者的思路：
public class Seven2 {
public static void main(String[] args) {
int dp[][] = new int[14][14];
dp[1][0] = dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = 1;
for (int i = 2; i <= 13; i++) {
for (int j = 0; j <= 13; j++) {
if (j - 4 >= 0) dp[i][j] += dp[i-1][j-4];
if (j - 3 >= 0) dp[i][j] += dp[i-1][j-3];
if (j - 2 >= 0) dp[i][j] += dp[i-1][j-2];
if (j - 1 >= 0) dp[i][j] += dp[i-1][j-1];
dp[i][j] += dp[i-1][j];
}
}
System.out.println(dp[13][13]);
}
}
第三种解法
以下是我的方法，思路是先求牌的个数，如单张的有多少个，对子有多少个，三个的有多少个，四个的有多少个，0个的有多少个。
然后求排列，比较繁琐一些，但是也能解决问题。
import java.util.ArrayList;
import java.util.List;
/**
* @author yunqing_shui@163.com
*/
public class Main7 {
public static int S = 0;
public static void main(String[] args) {
ArrayList<Integer> list0 = new ArrayList<>();
for (int i = 0; i < 4; i++) {
ArrayList<Integer> list1 = new ArrayList<>(list0);
for (int j = 0; j < 5; j++) {
ArrayList<Integer> list2 = new ArrayList<>(list1);
for (int k = 0; k < 7; k++) {
ArrayList<Integer> list3 = new ArrayList<>(list2);
for (int l = 0; l < 14; l++) {
sumList(list3);
list3.add(1);
}
list2.add(2);
}
list1.add(3);
}
list0.add(4);
}
System.out.println("S = " + S);
}
public static void sumList(List<Integer> list) {
int sum = 0;
for (int i : list) {
sum += i;
}
int a4 = 0;
int a3 = 0;
int a2 = 0;
int a1 = 0;
if (sum == 13) {
for (int it : list) {
if (it == 1) {
a1++;
} else if (it == 2) {
a2++;
} else if (it == 3) {
a3++;
} else if (it == 4) {
a4++;
}
}
int number = getCNM(13, a1) * getCNM(13 - a1, a2) * getCNM(13 - a1 - a2, a3) * getCNM(13 - a1 - a2 - a3, a4);
S += number;
}
}
public static int getANM(int a, int b) {
int s = 1;
for (int i = a; i > Math.max(b, a - b); i--) {
s *= i;
}
return s;
}
public static int getCNM(int a, int b) {
return getANM(a, b) / getN(Math.min(b, a - b));
}
public static int getN(int a) {
if (a == 1 || a == 0) {
return 1;
}
return a * getN(a - 1);
}
}
