第七届蓝桥杯javaB组真题解析-剪邮票（第七题）

题目

/*
剪邮票

如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

请你计算，一共有多少种不同的剪取方法。

请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
*/

　　　　　　　　　　　　图1.jpg

　　　　　　　　　　　　图2.jpg

　　　　　　　　　　图3.jpg

答案

代码

 1 public class Main {
 2     static int cc[][] = {
 3             {1,1,0,0,1,0,0,0,0,0,0,0},
 4             {1,1,1,0,0,1,0,0,0,0,0,0},
 5             {0,1,1,1,0,0,1,0,0,0,0,0},
 6             {0,0,1,1,0,0,0,1,0,0,0,0},
 7             {1,0,0,0,1,1,0,0,1,0,0,0},
 8             {0,1,0,0,1,1,1,0,0,1,0,0},
 9             {0,0,1,0,0,1,1,1,0,0,1,0},
10             {0,0,0,1,0,0,1,1,0,0,0,1},
11             {0,0,0,0,1,0,0,0,1,1,0,0},
12             {0,0,0,0,0,1,0,0,1,1,1,0},
13             {0,0,0,0,0,0,1,0,0,1,1,1},
14             {0,0,0,0,0,0,0,1,0,0,1,1},
15     };
16     public static void main(String[] args) {
17         int a,b,c,d,e,sum=0;
18         for(a=0;a<8;a++) {
19         for(b=a+1;b<9;b++) {
20         for(c=b+1;c<10;c++) {
21         for(d=c+1;d<11;d++) {
22         for(e=d+1;e<12;e++) {
23             int z[] = {a,b,c,d,e};
24             if(f(z)){
25                 System.out.println(a+1+" "+(b+1)+" "+(c+1)+" "+(d+1)+" "+(e+1));
26                 sum++;
27             }
28         }
29         }
30         }
31         }
32         }
33         System.out.println(sum);
34     }
35     private static boolean f(int[] a) {
36         int is[] = new int[5];
37         is[0] = 1;
38         g(a,0,is);
39         int zz=0;
40         for(int i:is){
41             if(i==1)zz++;
42         }
43         if(zz==5) return true;
44         return false;
45     }
46     private static void g(int[] a, int b, int[] c){
47         for(int i=0;i<c.length;i++){
48             if(c[i]==0){
49                 if(cc[a[b]][a[i]]==1){
50                     c[i] = 1;
51                     g(a,i,c);
52                 }
53             }
54         }
55     }
56 }

解析

　　这道题也是属于排列组合的题，只不过不是前面的全排列，而是从12个数中无前后顺序的抽取5个，然后判断抽出的5个是否满足要求，若是则计数++，否则return ；

　　我的解法思路是：用5个for循环嵌套来分别表示这从小到大的5个数，其中的条件也是互相有关联的，用这种方法来抽取5个数并存入数组中，然后用f函数来验证所抽取的是否满足条件，g方法的作用是深度遍历，从数组中第一个数开始按照条件向足相邻条件的那一项遍历，并且用is[]数组来做标记，当这一次遍历结束时，判断是否全部遍历，如果是则满足条件return true，否则没有

return false;

　　在判断是否满足相邻关系的那个地方，因为觉得找出逻辑关系很麻烦，所以就自己手动写了一个二位数组，用来判断从1-12，这12个数的两两相邻情况，1则相邻，0则不相邻。

　　1是因为懒，2是因为方便，省时间

　　可以充分的把一些不是怎么变的东西，用人脑来完成