2016年Java方向C组第七题

搭积木

小明最近喜欢搭数字积木，
一共有10块积木，每个积木上有一个数字，0~9。

搭积木规则：
每个积木放到其它两个积木的上面，并且一定比下面的两个积木数字小。
最后搭成4层的金字塔形，必须用完所有的积木。

下面是两种合格的搭法：

   0
  1 2
 3 4 5
6 7 8 9

   0
  3 1
 7 5 2
9 8 6 4    

请你计算这样的搭法一共有多少种？

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

解析：

方案一：循环嵌套

假设数字分别是a,b,c,d,e,f,g,h,i,j。

   a
  b c
 d e f
g h i j

int ans = 0;
for (int a = 0; a <= 9; a++) {
    for (int b = 0; b <= 9; b++) {
        if(b==a) continue;
        for (int c = 0; c <= 9; c++) {
            if(c==a || c==b) continue;
            for (int d = 0; d <= 9; d++) {
                if(d==a ||d==b || d==c) continue;
                for (int e = 0; e <= 9; e++) {
                    if(e==a || e==b || e==c || e==d) continue;
                    for (int f = 0; f <= 9; f++) {
                        if(f==a || f==b || f==c || f==d || f==e) continue;
                        for (int g = 0; g <= 9; g++) {
                            if(g==a || g==b || g==c || g==d || g==e || g==f) continue;
                            for (int h = 0; h <= 9; h++) {
                                if(h==a || h==b || h==c || h==d || h==e || h==f || h==g) continue;
                                for (int i = 0; i <= 9; i++) {
                                    if(i==a || i==b || i==c || i==d || i==e || i==f || i==g || i==h) continue;
                                    for (int j = 0; j <= 9; j++) {
                                        if(j==a || j==b || j==c || j==d || j==e || j==f || j==g || j==h || j==i) 
                                            continue;
                                        if( a < b && a < c && 
                                                b < d && b < e && c < e && c < f && 
                                                d <g && d<h && e<h && e<i && f<i && f<j)
                                            ans++;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }           
}
System.out.println(ans);

答案：768

方案二：全排列递归

static int count = 0;  //计算排列方案的数量
public static void main(String[] args)
{
    int[] arr = new int[]{0,1,2,3,4,5,6,7,8,9};
    fullSort(arr,0,arr.length-1);
    System.out.println(count);
}

public static void fullSort(int[] arr,int start,int end)
{
    if(start == end)  //此处为true则证明排列完成一次
    {
        if(arr[0]<arr[1] && arr[0]<arr[2] &&
                arr[1]<arr[3] && arr[1]<arr[4] && 
                arr[2]<arr[4] && arr[2]<arr[5] && 
                arr[3]<arr[6] && arr[3]<arr[7] && 
                arr[4]<arr[7] && arr[4]<arr[8] &&
                arr[5]<arr[8] && arr[5]<arr[9])
            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;
}