記一次簡單高效的吸血鬼算法

• • 什麼是吸血鬼數字
  • 擷取四位數的吸血鬼數字的代碼實作
  • 輸出結果
  • 代碼分析

什麼是吸血鬼數字

吸血鬼數字是指位數為偶數的數字，可以由一對數字相乘而得到，而這對數字各包含乘積的一半位數的數字，其中從最初的數字中選取的數字可以任意排序，以兩個0結尾的數字是不允許的。

• 例如下列數字都是吸血鬼數字

  1260=21 * 60

  1827=21 * 87

  2187=27 * 81

擷取四位數的吸血鬼數字的代碼實作

public class Test {
    public static void main(String[] args) {
        //初始化比較次數
        int i = 0;
        //a是第一個一半位數的數字
        for (int a = 10; a < 100; a++) {
            //b是第二個一半位數的數字
            for (int b = a; b < 100; b++) {
                //兩個一半位數的數字的乘積
                int result = a * b;
                //判斷是否符合條件需求
                //result > 9999 || result < 1000 判斷是否是四位數
                //result % 100 == 0 判斷最後兩位數是否是：00
                //(result - a - b) % 9 != 0 判斷是否可以被9整除（這個判斷是在網上看到别人介紹的）
                if ((result > 9999 || result < 1000) || result % 100 == 0 || (result - a - b) % 9 != 0) {
                    continue;
                }
                //建立乘積的字元集合
                List<Character> resultList = String.valueOf(result).chars().mapToObj(c -> (char) c).collect(Collectors.toList());
                //建立第一個一半位數的數字的字元集合
                List<Character> aList = String.valueOf(a).chars().mapToObj(c -> (char) c).collect(Collectors.toList());
                //建立第二個一半位數的數字的字元集合
                List<Character> bList = String.valueOf(b).chars().mapToObj(c -> (char) c).collect(Collectors.toList());
                //往乘積字元集合移除第一個一半位數的數字的字元集合的成員
                resultList.remove(aList.get(0));
                resultList.remove(aList.get(1));
                //往乘積字元集合移除第二個一半位數的數字的字元集合的成員
                resultList.remove(bList.get(0));
                resultList.remove(bList.get(1));
                //如果乘積集合的成員全部移除，則說明為吸血鬼數字
                if (resultList.size() == 0) {
                    //輸出吸血鬼數字
                    System.out.println(a + " * " + b + " = " + result);
                }
                //自增比較次數
                i++;
            }
        }
        //輸出比較次數
        System.out.println("比較次數：  " + i);
    }
}
           

輸出結果

代碼分析

因為這裡要的是一個四位數，是以根據階層：4 * 3 * 2 * 1 = 24，可以知道一共有24種排列方式

下面羅列其中一部份的情況

假設：
result = 1000x + 100y + 10z + k
(1)a = 10x + y		b=10z + k	result - a - b = 990x + 99y
(2)a = 10x + y		b=10k + z	result - a - b = 990x + 99y + 9z - 9k
(3)a = 10x + z		b=10y + k	result - a - b = 990x + 90y + 9z
(4)a = 10x + z		b=10k + y	result - a - b = 990x + 99y + 9z - 9k
(5)a = 10x + k		b=10y + z	result - a - b = 990x + 90y + 9z
(6)a = 10x + k		b=10z + y	result - a - b = 990x + 99y
(7)a = 10y + x		b=10z + k	result - a - b = 999x + 90y
(8)a = 10y + x		b=10k + z	result - a - b = 999x + 90y + 9z - 9k
......
(24)a = 10k + x		b=10y + z	result - a - b = 999x + 90y + 9z - 9k
同時需要滿足：
result = a * b
           

觀察上面資料，經過分析和推敲，可以得知：result - a - b可以被9整除，是以如果：(result - a - b) % 9 != 0，則說明條件不符合要求！