《Thinking in Java》习题——吸血鬼数字-白红宇

最近在看《Java编程思想》，这本书非常棒，不愧是Java程序员的圣经。看到第四章，后面有道题目很有意思，于是就自己做了做。

1. 我的思路很简单，但是算法效率非常之低。就是把4位数拆成4个数字，比如1260--->1,2,6,0。然后4位数字组合成两个2位数，计算它们

的乘积，相等则就是吸血鬼数字。

1 public class Test2 { 2     /* 3      * 将4位数拆分成4个数 4      * */ 5   public int [] array(int num){ 6       int [] a = new int [4]; 7       int i=0; 8       while(num!=0){ 9         a[i++]=num%10;10         num=num/10;11      }12     return a;13   } 14   /*15    * 将4给数组合成两个数，相乘与4位数比较。相等就是吸血鬼数字16    * 17    * */18     public boolean equal(int num,int [] a){19         for(int i=0;i<4;i++){20             for(int j=0;j<4;j++){21                 if(i==j){22                     continue;23                 }else{24                     if(6-i-j==5){
   //i,j=0或125                         if((a[i]*10+a[j])*(a[3]*10+a[2])==num||(a[i]+a[j]*10)*(a[3]*10+a[2])==num){26                             return true;27                         }28                     }29                     else if(6-i-j==4){
   //i,j=0或2  30                         if((a[i]*10+a[j])*(a[3]*10+a[1])==num||(a[i]+a[j]*10)*(a[3]*10+a[1])==num){31                             return true;32                     }33                      }34                     else if(6-i-j==3&&(i==3||j==3)){ //i,j或0,3 35                         if((a[i]*10+a[j])*(a[2]*10+a[1])==num||(a[i]+a[j]*10)*(a[2]*10+a[1])==num){36                             return true;37                      }38                         }39                         else if(6-i-j==3&&(i==1||j==1)){
   //i,j=1或240                          if((a[i]*10+a[j])*(a[3]*10+a[0])==num||(a[i]+a[j]*10)*(a[3]*10+a[0])==num){41                                 return true;42                      }43                         } 44                         else if(6-i-j==2){
   //i,j=1或3 45                          if((a[i]*10+a[j])*(a[2]*10+a[0])==num||(a[i]+a[j]*10)*(a[2]*10+a[0])==num){46                                 return true;47                      }48                         }49                         else if(6-i-j==1){
   //i,j=2或3 50                          if((a[i]*10+a[j])*(a[1]*10+a[0])==num||(a[i]+a[j]*10)*(a[1]*10+a[0])==num){51                                 return true;52                        }53                       }54                      }55                    }56                 }57              return false;58             }59       public static void main(String[] args) {60           Test2 t2 = new Test2();61          for(int i =1001;(i<=9999);i++){62              if(t2.equal(i, t2.array(i))){63                  System.out.println(i);64              }65          }66     }67         68    }

运行结果：

结果是对的，但是算法效率太低。将近要循环9000*4*4=14400次。

在网上找了找，有很多高效的算法。贴出来研究一下别人的思路。

1 public class XiXueGui {    2     /**   3      * 吸血鬼数字算法   4      * 如：12*60=1260   5      * YangL.   6      */    7     public static void main(String[] args) {    8         String[] ar_str1 = null, ar_str2;    9         int sum = 0;   10         int count=0;11         for (int i = 10; i < 100; i++) {   12             for (int j = i + 1; j < 100; j++) {   13                 int i_val = i * j;   14                 if (i_val < 1000 || i_val > 9999)   15                     continue; // 积小于1000或大于9999排除,继续下一轮环   16                 count++;17                 ar_str1 = String.valueOf(i_val).split("");   18                 ar_str2 = (String.valueOf(i) + String.valueOf(j)).split("");   19                 java.util.Arrays.sort(ar_str1);   20                 java.util.Arrays.sort(ar_str2);   21                 if (java.util.Arrays.equals(ar_str1, ar_str2)) {   22                     // 排序后比较,为真则找到一组   23                     sum++;   24                     System.out.println("第" + sum + "组: " + i + "*" + j + "="   25                             + i_val);   26                 }   27             }   28         }   29         System.out.println("共找到" + sum + "组吸血鬼数"+"\ncount"+count);30        31     }   32 }

这个算法非常棒，基本思路是：4位数字的吸血鬼数字只能拆分成两个2位数。于是就计算两个2位数相乘（11，12行）。用String.valueOf(j)).split("");的方法来把数字转换为字符串，排序，比较4位数的字符串和两个2位数的字符串，若相等，就是吸血鬼数字。把数字的比较，转换为对字符串的比较，非常棒。

这个算法循环了3721次。

运行结果：

3.《Thinking in Java》官方答案

1 //: control/E10_Vampire.java 2 /****************** Exercise 10 ********************* 3 * A vampire number has an even number of digits and 4 * is formed by multiplying a pair of numbers containing 5 * half the number of digits of the result. The digits 6 * are taken from the original number in any order. 7 * Pairs of trailing zeroes are not allowed. Examples 8 * include: 9 * 1260 = 21 * 6010 * 1827 = 21 * 8711 * 2187 = 27 * 8112 * Write a program that finds all the 4-digit vampire13 * numbers. (Suggested by Dan Forhan.)14 ****************************************************/15 public class E10_Vampire {16 public static void main(String[] args) {17     int[] startDigit = new int[4];18     int[] productDigit = new int[4];19     for(int num1 = 10; num1 <= 99; num1++)20         for(int num2 = num1; num2 <= 99; num2++) {21             // Pete Hartley's theoretical result:22             // If x·y is a vampire number then23             // x·y == x+y (mod 9)24             if((num1 * num2) % 9 != (num1 + num2) % 9)25                 continue;26     int product = num1 * num2;27     startDigit[0] = num1 / 10;28     startDigit[1] = num1 % 10;29     startDigit[2] = num2 / 10;30     startDigit[3] = num2 % 10;31     productDigit[0] = product / 1000;32     productDigit[1] = (product % 1000) / 100;33     productDigit[2] = product % 1000 % 100 / 10;34     productDigit[3] = product % 1000 % 100 % 10;35     int count = 0;36     for(int x = 0; x < 4; x++)37       for(int y = 0; y < 4; y++) {38           if(productDigit[x] == startDigit[y]) {39               count++;40               productDigit[x] = -1;41               startDigit[y] = -2;42               if(count == 4)43                   System.out.println(num1 + " * " + num244                           + " : " + product);45                 }46             }47         }48     }49 }

运行结果：

原文地址：http://www.cnblogs.com/JohnTsai/p/4103051.html