2017年Java方向C组第三题

标题：纸牌三角形

A,2,3,4,5,6,7,8,9 共9张纸牌排成一个正三角形（A按1计算）。要求每个边的和相等。
下图就是一种排法（如有对齐问题，参看p1.png）。

4.png

      A
     9 6
    4   8
   3 7 5 2

这样的排法可能会有很多。

如果考虑旋转、镜像后相同的算同一种，一共有多少种不同的排法呢？

请你计算并提交该数字。

注意：需要提交的是一个整数，不要提交任何多余内容。

笨笨有话说：
感觉可以暴力破解哦。
麻烦的是，对每个排法还要算出它的旋转、镜像排法，看看有没有和历史重复。

歪歪有话说：
人家又不让你把所有情况都打印出来，只是要算种类数。
对于每个基本局面，通过旋转、镜像能造出来的新局面数目不是固定的吗？

解析方案一(循环嵌套)：

int count = 0;
for (int a = 1; a <= 9; a++) 
{
    for (int b = 1; b <= 9; b++) 
    {
        if(b==a) continue;
        for (int c = 1; c <= 9; c++) 
        {
            if(c==a || c == b) continue;
            for (int d = 1; d <= 9; d++) 
            {
                if(d==a || d==b || d==c) continue;
                for (int e = 1; e <= 9; e++) 
                {
                    if(e==a || e==b || e== c || e==d) continue;
                    for (int f = 1; f <= 9; f++) 
                    {
                        if(f == a || f == b || f==c || f==d || f==e) continue;
                        for (int g = 1; g <= 9; g++) 
                        {
                            if(g == a || g== b || g==c || g==d || g==e || g==f) continue;
                            if(a+b+c+d != d+e+f+g) continue;
                            for (int h = 1; h <= 9; h++) 
                            {
                                if(h == a || h== b || h==c || h==d || h==e || h==f || h==g) continue;
                                for (int i = 1; i <= 9; i++) 
                                {
                                    if(i == a || i== b || i==c || i==d || i==e || i==f || i==g || i==h) continue;
                                    if(a+b+c+d == d+e+f+g && a+b+c+d == g + h + i + a)
                                        count++;                            
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}
//旋转之后有3种一样的情况，旋转之后每种情况还有一个镜像，所以这里除6
System.out.println(count/6);  

答案：144

解析方案二(递归)：

static int count = 0;
public static void main(String[] args)
{
    int[] arr = new int[]{1,2,3,4,5,6,7,8,9};
    fullSort(arr,0,arr.length-1);
    //旋转之后有3种一样的情况，旋转之后每种情况还有一个镜像，所以这里除6
    System.out.println(count/6);
}
public static void fullSort(int[] arr,int start,int end)
{
    if(start == end)
    {
        int a = arr[0] + arr[1] + arr[2] + arr[3];
        int b = arr[3] + arr[4] + arr[5] + arr[6];
        int c = arr[6] + arr[7] + arr[8] + arr[0];
        if(a == b && a == c)
            count++;
    }
    for (int i = start; i <=end; i++) {
        swap(arr,start,i);
        fullSort(arr,start+1,end);
        swap(arr,start,i);
    }
}

public static void swap(int[] arr,int i,int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

答案：144

解析方案二中涉及到一种全排列算法，具体算法举例如下：

下面的代码可以将1，2，3，三个数字的所有排列组合进行打印。

public static void main(String[] args)
{
    int[] arr = new int[]{1,2,3};
    fullSort(arr,0,arr.length-1);
}
public static void fullSort(int[] arr,int start,int end)
{
    if(start == end)
    {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
        System.out.println();
    }
    for (int i = start; i <=end; i++) {
        swap(arr,start,i);
        fullSort(arr,start+1,end);
        swap(arr,start,i);
    }
}

public static void swap(int[] arr,int i,int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}