藍橋杯第八屆真題 ：9數算式

點選檢視：藍橋杯曆年真題 題解目錄

9數算式

1.首先，對1~9進行全排列，然後對每種排列進行"乘号"位置的排列
2.在對乘号位置确定後，要保證"乘号兩邊的乘數"正确
3.用乘數的結果，即等号右邊的值進行判斷 。
   check 1. 長度為9 ；    check 2. 長度為9時不包含數字0，無重複元素。
4. 最終結果除以2，題目已說明兩乘數交換位置 視為一種情況。
           

import java.util.Set;
import java.util.HashSet;
public class Main002_9數算式{
    static int[]a = {1,2,3,4,5,6,7,8,9};
    static int count;
    public static void main(String[] args) {
  	per(0);
  	int ans = count/2;
  	System.out.println(ans);
    }
    private static void per(int k) {
  	if(k==9) {
   	    for(int i=1;i<=8;i++) {
    	    	int x1 = algor(0,i);
    	    	int x2 = algor(i,9);
    	    	if(check(x1*x2)) 
     		    count++;
            }
        }
        // 全排列（遞歸版本）
        for(int i=k;i<9;i++) {
  	    int t = a[i];
   	    a[i] = a[k];
   	    a[k] = t;
   	    per(k+1);
   	    t = a[i];
   	    a[i] = a[k];
   	    a[k] = t;
        }
    }
    //  判斷等号右邊的數是否符合條件
    private static boolean check(int x) {
  	String s=x+"";
  	if(s.length()!=9 || s.indexOf('0')>-1) return false;
  	Set<Character> set = new HashSet<>();
  	for(int i=0;i<s.length();i++) 
   	    set.add(s.charAt(i));
  	return set.size()==9;
    }
    // 将零散的整數 組成乘數
    private static int algor(int i, int j) {
  	int x = 0;
  	int p = 1;
  	for(int k=j-1;k>=i;k--) {
   	    x+=a[k]*p;
   	    p*=10;
  	}
  	return x;
    }
}