MENU

第八届蓝桥杯Java A——9数算式

March 20, 2019 • Read: 140 • 算法

观察如下的算式:

9213 x 85674 = 789314562

左边的乘数和被乘数正好用到了1~9的所有数字,每个1次。
而乘积恰好也是用到了1~9的所有数字,并且每个1次。

请你借助计算机的强大计算能力,找出满足如上要求的9数算式一共有多少个?

注意:

  1. 总数目包含题目给出的那个示例。
  2. 乘数和被乘数交换后作为同一方案来看待。
import java.util.HashSet;
import java.util.Set;

public class Main {

    static boolean[] book = new boolean[9];
    static int[] arr = new int[9];
    static int ans;

    public static void main(String[] args) {
        dfs(0);
        System.out.println(ans / 2);
    }

    static void dfs(int idx) {
        if (idx == 9) {
            for (int i = 0; i <= 7; i++) {
                int a = atoi(0, i);
                int b = atoi(i + 1, 8);
                if (check(a * b))
                    ans++;
            }
        } else {
            for (int i = 1; i <= 9; i++) {
                if (!book[i - 1]) {
                    book[i - 1] = true;
                    arr[idx] = i;
                    dfs(idx + 1);
                    book[i - 1] = false;
                }
            }
        }
    }

    static boolean check(int res) {
        String str = "" + res;
        if (str.indexOf('0') != -1)
            return false;
        else {
            Set<Character> set = new HashSet<Character>();
            for (int i = 0; i < str.length(); i++)
                set.add(str.charAt(i));
            return set.size() == 9;
        }
    }

    static int atoi(int s, int e) {
        StringBuilder str = new StringBuilder("");
        for (int i = s; i <= e; i++)
            str.append(arr[i]);
        return Integer.parseInt(str.toString());
    }
}
Archives Tip
QR Code for this page
Tipping QR Code