吸血鬼數是指位數為偶數的數字，可以由一 對數字相乘而得到，而這對數字各包含乘積的一半 位數的數字，其中從最初的數字中選取的數字可以任意排序，以兩個0結尾的數字是不允許的，例如，下列數字都是 “吸血鬼”數字:
1260=21 * 60
1827=21 * 87
2187= 27 * 81
那么，開始
由于判斷四位數是否能分解為兩個兩位數的乘積，比判斷兩位數的乘積所得四位數的，要麻煩得多，因此思路為后者，
import java.util.ArrayList; import java.util.Arrays; /** * 先從1001開始到9999開始判斷，是否能分解為兩個二位數，如果可以，二維數是否包含所有四個數字 * 把四位數分解成二位數乘積過于麻煩，而且一個四位數可能存在多種分解方式，加大了設計的難度 * 但是反過來，二位數乘以二位數簡單得多，此時再去判斷即可 * 將積分解成四個數位，存入陣列，兩個乘數分別分解成兩個數位，存入一個陣列 * 將兩個陣列排序，按照下標逐個比較，如果兩個陣列相同，回傳true * @author zhaoke * */ public class Vampire { //冒泡排序法 public void sort(int[] array) { for (int i = 0; i < array.length-1; i++) { for (int j = i+1; j < array.length; j++) { if (array[i] > array[j]) { //交換兩個數的位置 array[i] = array[i] - array[j]; array[j] = array[i] + array[j]; array[i] = array[j] - array[i]; } } } } /** * 判斷四位數分解后的數位(存在陣列里)，是否恰好包含兩個乘積因子的所有數位 * 為了簡單起見，方法是先排序，然后比較兩個陣列是否相同 */ public boolean check(int[] digits, int num1, int num2) { this.sort(digits); // System.out.println(Arrays.toString(digits)); int[] factors = new int[4]; //分離第一個乘數的兩個數位 int[] numArray = this.divideNumber(num1); for (int i = 0; i < 2; i++) { factors[i] = numArray[i]; } //分離第二個乘數的兩個數位 numArray = this.divideNumber(num2); for (int i = 2; i < 4; i++) { factors[i] = numArray[i-2]; } this.sort(factors); // System.out.println(Arrays.toString(factors)); for (int i = 0; i < digits.length; i++) { if (digits[i] != factors[i]) { return false; } } return true; } public int[] divideNumber(int number) { int[] digits = new int[2]; digits[0] = number/10; digits[1] = number - 10*(number/10); return digits; } /** * 獲得每個位的數字 */ public int[] divideArray(int number) { int[] digits = new int[4]; int factor = 1000; for (int i = 0; i < digits.length; i++) { digits[i] = number/factor; number -= digits[i] * factor; factor /= 10; } return digits; } ArrayList<Integer> result = new ArrayList<Integer>(); /** * 10*99小于1000，因此從11開始回圈 */ public void start() { int count = 0; //計數器而已 for (int i = 11; i < 100; i++) { for (int j = 11; j < 100; j++) { if (i*j <1000) continue; if (i*j%100==0) { //根據題目,如果最后兩位是0,也不可 continue; } int[] digits = divideArray(i*j); if (this.check(digits, i, j)) { if (this.result.contains(i*j)) continue; this.result.add(i*j); System.out.printf("第%d個吸血鬼數: %d = %d x %d \n",++count,i*j,i,j); } } } } public static void main(String[] args) { Vampire v = new Vampire(); v.start(); } }
結果如下:
第1個吸血鬼數: 1395 = 15 x 93 第2個吸血鬼數: 1260 = 21 x 60 第3個吸血鬼數: 1827 = 21 x 87 第4個吸血鬼數: 2187 = 27 x 81 第5個吸血鬼數: 1530 = 30 x 51 第6個吸血鬼數: 1435 = 35 x 41 第7個吸血鬼數: 6880 = 80 x 86
總結:逆向思維，模塊化設計
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/69646.html
標籤：其他