第七届蓝桥杯javaB组真题解析-方格填数(第六题)

题目

/*
方格填数 如下的10个格子
+--+--+--+
| | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | |
+--+--+--+ (如果显示有问题,也可以参看【图1.jpg】) 填入0~9的数字。要求:连续的两个数字不能相邻。
(左右、上下、对角都算相邻) 一共有多少种可能的填数方案? 请填写表示方案数目的整数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。*/

答案

1580

第七届蓝桥杯javaB组真题解析-方格填数(第六题)

代码

 public class Main {
static int sum = 0 ;
public static void main(String[] args) {
int a[] = {0,1,2,3,4,5,6,7,8,9};
int b[] = new int[10];
String s = "";
f(a,b,0,s);
System.out.println(sum);
}
private static void f(int[] a,int[] b,int k,String s) {
if(k!=0 && k!=1 && k!=4 && k!=8 ){
if(Math.abs(b[k-1]-b[k-2])==1) return;
}
if(k>=4 && k<=10 && k!=7){
if(Math.abs(b[k-1]-b[k-4])==1) return;
}
if(k>=5 && k<=10){
if(Math.abs(b[k-1]-b[k-5])==1) return;
}
if(k==6 || k==7 || k==9 || k==10){
if(Math.abs(b[k-1]-b[k-6])==1) return;
} if(k==a.length) {
sum++;
System.out.println(s);
return;
}
for(int i=0;i<a.length;i++){
String ss = s;
if(a[i]==-1) continue;
b[k] = a[i];
ss += a[i];
a[i] = -1;
f(a,b,k+1,ss);
a[i] = b[k];
} }
}

分析

  这又是一道涉及到排列组合的算法题,我用的是比较简单和常见的解法,利用循环递归,开始依次向方格里面填数, 每填一个数都会判断一下这个数是不是符合条件,如果符合条件则递归进去填下一个,如果不符合条件则return,当满足在满足条件的情况下数填完之后(k==10),则sum++,计数加一

  因为判断条件对方格有所依赖,所以想在短时间内写出一个比较完美通用的算法是有点困难的,我们可以把情况细分,使得条件结构更清晰一点,

  再说一个我觉得比较有创意的一点,这也是我最近学到的,就是用一个字符串,让这个字符串也参与递归,就可以巧妙的可以把每次的情况都输出来了,我很喜欢。

private static void f(int[] a,int[] b,int k,String s) {
11 if(k!=0 && k!=1 && k!=4 && k!=8 ){
12 if(Math.abs(b[k-1]-b[k-2])==1) return;
13 }
14 if(k>=4 && k<=10 && k!=7){
15 if(Math.abs(b[k-1]-b[k-4])==1) return;
16 }
17 if(k>=5 && k<=10){
18 if(Math.abs(b[k-1]-b[k-5])==1) return;
19 }
20 if(k==6 || k==7 || k==9 || k==10){
21 if(Math.abs(b[k-1]-b[k-6])==1) return;
22 }
23
24 if(k==a.length) {
25 sum++;
26 System.out.println(s);
27 return;
28 }
29 for(int i=0;i<a.length;i++){
30 String ss = s;
31 if(a[i]==-1) continue;
32 b[k] = a[i];
33 ss += a[i];
34 a[i] = -1;
35 f(a,b,k+1,ss);
36 a[i] = b[k];
37 }
38
39
40 }
上一篇:eclipse中使用git技巧总结


下一篇:jdk+tomcat+mysql一键安装脚本