========================================
此为传送门：关于本篇吸血鬼算法的介绍及相应优化
========================================
昨天晚上在看Thinking in Java时，作者在第四章第八节的练习10里面提到了一种有趣的数字：吸血鬼数。以下是来自wikipedia的定义：
從合成數v開始,該合成數需有偶數n個位,然後用v的各個數字組成兩個n/2個位的正整數x和y(x和y不能同時以0為個位數).若x和y的積，剛好就是v，那麼v就是吸血鬼數（vampire number），而x和y則稱為尖牙。
例如1260是吸血鬼數，21和60是其尖牙，因為21×60=1260。可是126000=210×600卻非，因為210和600都以0為個位數。又例如1023是31和33的積，但31和33並沒有用到原數的所有數字(並沒有用到0)，所以1023不是吸血鬼數。
看起来挺有趣，于是自己也写了一个求吸血鬼数的算法，原练习要求的是求四位数，我改进了一下，可以求任意int型整数，代码如下：
import java.util.List;
import java.util.LinkedList;
public class VampireNumber {
public static void find(int start, int end) {
System.out.println("start: " + start + ", end: " + end);
int slen = VampireNumber.getIntegerLength(start);
int elen = VampireNumber.getIntegerLength(end);
if(slen % 2 != 0) {
slen++;
}
if(elen % 2 == 0) {
elen++;
}
if(slen >= elen) {
System.out.println("No suitable number exists in this section.");
return;
}
// 根据范围确定下面循环开始和结束的数字
int begin = (int)Math.pow(10, slen / 2 - 1);
int finish = (int)Math.pow(10, (elen - 1) / 2);
System.out.println("begin: " + begin + ", finish: " + finish);
for(int i = begin; i < finish; i++) {
for(int j = i; j < finish; j++) { // 从i开始，避免出现(17, 27)、(27, 17)这样的重复
// 如果两个数结尾都是0，则继续
if(i % 10 == 0 && j % 10 == 0) {
continue;
}
int first = VampireNumber.getIntegerLength(i);
int second = VampireNumber.getIntegerLength(j);
if(second > first) {
break;
} else if(second < first) {
continue;
}
int value = i * j;
// 检测value是否已溢出
if(value < 0) {
break;
}
if(value < start) {
continue;
}
if(value > end) {
break;
}
int len = VampireNumber.getIntegerLength(value);
if(len != first + second) {
continue;
}
// 将两个乘数的数字放入List
List<Integer> numList = new LinkedList<Integer>();
VampireNumber.getNumberList(i, first, numList);
VampireNumber.getNumberList(j, second, numList);
boolean isVampireNumber = true;
// 将乘积的数字和List中存放的乘数的数字进行比较
while(value != 0) {
int current = value % 10;
value /= 10;
if(!numList.contains(current)) {
isVampireNumber = false;
break;
}
numList.remove(new Integer(current));
}
// 如果乘积的数字和List中存放的乘数的数字吻合，则是吸血鬼数
if(isVampireNumber) {
System.out.println("A vampire number found: " + i * j + ", (" + i + ", " + j + ").");
}
}
}
}
// 将num的各个位的数字放入list
public static void getNumberList(final int num, int length, List<Integer> list) {
int copy = num;
for(int i = 0; i < length; i++) {
list.add(copy % 10);
copy /= 10;
}
}
// 取得num的位数
public static int getIntegerLength(final int num) {
int len = 0;
int copy = num;
if(copy == 0) {
return ++len;
}
while(copy != 0) {
copy /= 10;
len++;
}
return len;
}
public static void main(String[] args) {
System.out.println("----------- Now start computing... -----------");
long s = System.currentTimeMillis();
VampireNumber.find(0, Integer.MAX_VALUE);
long f = System.currentTimeMillis();
System.out.println("----- Computing finished, time used: " + (f - s) + " ms. -----");
}
}
上述程序用于求出0与Integer.MAX_VALUE之间的所有吸血鬼数，经实际测试（机器为四核3.3G的CPU，4G内存），运行时间为746259ms，超过了12分钟，在这么高配置的机器中运行速度还这么慢，可见整个算法的低效程度，有待优化~~~ ^_^
本人冒天下之大不韪，在各位算法大牛面前班门弄斧，如果各位要喷的话，请轻点喷，谢谢~~~ ^_^