湊算式——第七屆藍橋杯C語言B組（省賽）第三題

原創

湊算式

       B      DEF
A + --- + ------- = 10
       C      GHI

（如果顯示有問題，可以參見【圖1.jpg】）

這個算式中A~I代表1~9的數字，不同的字母代表不同的數字。

比如：
6+8/3+952/714 就是一種解法，
5+3/1+972/486 是另一種解法。

這個算式一共有多少種解法？

註意：你提交應該是個整數，不要填寫任何多餘的內容或說明性文字。

法一（枚舉）：

開闢9個變數分別代表1~9個數，每個變數在1~9中變化，對於每一個數字都判斷是否包含1~9個數位和滿足湊算式即可。

public class 湊算式 {
    public static void main(String args[]) {
        double arr[]=new double[9];
        long total=0L;
        for(arr[0]=1;arr[0]<=9;arr[0]++) {
            for(arr[1]=1;arr[1]<=9;arr[1]++) {
                for(arr[2]=1;arr[2]<=9;arr[2]++) {
                    for(arr[3]=1;arr[3]<=9;arr[3]++) {
                        for(arr[4]=1;arr[4]<=9;arr[4]++) {
                            for(arr[5]=1;arr[5]<=9;arr[5]++) {
                                for(arr[6]=1;arr[6]<=9;arr[6]++) {
                                    for(arr[7]=1;arr[7]<=9;arr[7]++) {
                                        for(arr[8]=1;arr[8]<=9;arr[8]++) {
                                            int i=0;
                                            int tt=0;
                                            int flag[]=new int[10];
                                            for(i=0;i<=8;i++) {    //判斷是否包含0~9
                                                if(flag[(int)(arr[i])]==1) {
                                                    break;
                                                }
                                                flag[(int)(arr[i])]=1;
                                                tt++;
                                            }
                                            if(tt==9) {
                                                if(arr[0]+arr[1]/arr[2]+(arr[3]*100+arr[4]*10+arr[5])/(arr[6]*100+arr[7]*10+arr[8])==10) {
                                                    total++;
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        System.out.println(total);
    }
}

法二（全排列）：

全排列的思想請看我另外一篇博客：https://www.cnblogs.com/chiweiming/p/8727164.html

每產生一種全排列，就判斷是否滿足湊算式即可。

public class 湊算式{
    static int total=0;
    static int arr[]=new int[9];
    
    static void Swap(int a,int b) {    //交換
        int temp=0;
        temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
    
    static void Full_Sort(int num) {    //全排列
        
        if(num==9) {    //產生一種全排列
            double a=arr[0];
            double b=arr[1];
            double c=arr[2];
            double def=arr[3]*100+arr[4]*10+arr[5];
            double ghi=arr[6]*100+arr[7]*10+arr[8];
            if(a+b/c+def/ghi==10) {
                total++;
            }
            return;
        }
        
        int i=0;
        for(i=num;i<=8;i++) {
            Swap(num,i);
            Full_Sort(num+1);
            Swap(num,i);
        }
    }
    
    public static void main(String args[]) {
        int i=0;
        for(i=0;i<=8;i++) {
            arr[i]=i+1;
        }
        Full_Sort(0);
        System.out.println(total);
    }
}

答案：29

21:10:02

2018-06-07