Java编程思想

Java编程思想-吸血鬼数字

《Java 编程思想》上的一道练习题，虽然看起来简单，但是写一个穷举遍历法都花了好长时间，，真是太渣了。。。

我的穷举遍历法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
 * Created by clearbug on 2017/3/15.
 */
public class VampireNumber {
    public static void main(String[] args) {
        for (int i = 1000; i < 10000; i++) {
            int [] arr = getArr(i);
            //printArray(arr);
            if (check(i, arr)) {
                System.out.println(i);
            }
        }
    }
    public static int[] getArr(int n) {
        int[] result = new int[4];
        for (int i = 0; i < result.length; i++) {
            result[i] = n / (int) Math.pow(10, result.length - 1 - i);
            n = n % (int) Math.pow(10, result.length - 1 - i);
        }
        return result;
    }
    public static boolean check(int n, int[] arr) {
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            int a = arr[i];
            for (int j = 0; j < length; j++) {
                if (j == i) {
                    continue;
                }
                int b = arr[j];
                for (int k = 0; k < length; k++) {
                    if (k == j || k == i) {
                        continue;
                    }
                    int c = arr[k];
                    for (int l = 0; l < length; l++) {
                        if (l == k || l == j || l == i) {
                            continue;
                        }
                        int d = arr[l];
                        if ((a * 10 + b) * (c * 10 + d) == n) {
                            System.out.println(a + ", " + b + ", " + c + ", " +d);
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (i < arr.length - 1) {
                System.out.print(arr[i] + ",");
            } else {
                System.out.println(arr[i]);
            }
        }
    }
}

别人写的利用了Java内置工具类库，效率未必有多高，代码确实简洁了好多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Arrays;
/**
 * Created by clearbug on 2017/3/15.
 */
public class VampireNumberA {
    public static void main(String[] args) {
        int count = 0;
        String[] arr_str1, arr_str2;
        for (int i = 10; i < 100; i++) {
            for (int j = i; j < 100; j++) {
                int val = i * j;
                if (val < 1000 || val > 9999) {
                    continue;
                }
                arr_str1 = String.valueOf(val).split("");
                arr_str2 = (String.valueOf(i) + String.valueOf(j)).split("");
                Arrays.sort(arr_str1);
                Arrays.sort(arr_str2);
                if (Arrays.equals(arr_str1, arr_str2)) {
                    count++;
                    System.out.println("第 " + count + " 组：" + i + " X " + j + " = " + val);
                }
            }
        }
    }
}

官方标准答案，也不过如此啦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Created by clearbug on 2017/3/15.
 */
public class VampireNumberB {
    public static void main(String[] args) {
        int[] startDigit = new int[4];
        int[] productDigit = new int[4];
        for (int num1 = 10; num1 < 100; num1++) {
            for (int num2 = num1; num2 < 100; num2++) {
                if ((num1 * num2) % 9 != (num1 + num2) % 9) {
                    continue;
                }
                int product = num1 * num2;
                startDigit[0] = num1 / 10;
                startDigit[1] = num1 % 10;
                startDigit[2] = num2 / 10;
                startDigit[3] = num2 % 10;
                productDigit[0] = product / 1000;
                productDigit[1] = (product % 1000) / 100;
                productDigit[2] = (product % 1000 % 100) / 10;
                productDigit[3] = product % 1000 % 100 % 10;
                int count = 0;
                for (int x = 0; x < 4; x++) {
                    for (int y = 0; y < 4; y++) {
                        if (startDigit[x] == productDigit[y]) {
                            count++;
                            startDigit[x] = -1;
                            productDigit[y] = -2;
                            if (count == 4) {
                                System.out.println(num1 + " * " + num2 + " = " + product);
                                break;
                            }
                        }
                    }
                }
            }
        }
    }
}

其中利用了一个已知的公理：如果两个数字a，b 是吸血鬼数的尖牙，那么它必然符合：
(a * b) % 9 == (a + b) % 9，但是符合这个条件的却未必就是吸血鬼数的尖牙，所以这个公理只能做一下初期简化！