对上一篇吸血鬼数算法的优化
这是我在博客园的博客中的文章。
下面是原文（未大改，稍作了一些格式上的调整）：
在本人上一篇拙作中，介绍了吸血鬼数的概念并实现了一种算法，但正如末尾所说，在计算从0到 Integer.MAX_VALUE 之间的吸血鬼数时，其计算时间达到了12分钟之长。因此，该算法有待优化。
先说一下该算法的基本思想：比方说要求四位数、即求1000~9999之间的吸血鬼数，那么两个乘数的位数为2，则乘数的范围即可定为[10, 99]，于是，对两个乘数进行从10到99的双层循环，计算其积，在满足相关限制条件的情况下，将积所包含的数字和乘数所包含的数字进行比较，如果数字完全相同，那么该积即为吸血鬼数。对于其它偶数位的整数，可按上述方法类推。
在修改之前的算法基本流程如下：
- 获得要求的整数区间[m, n]的最小偶数位数a和最大偶数位数b；
- 因为要分为两个数，所以取a/2位数的最小值min作为初始计数值，取b/2位数的最大值 max作为终止计数值；
- 从min到max进行双层循环；
- 判断循环数是否符合要求（末尾不能全为0，etc.）；
- 将双层循环的数进行相乘；
- 判断积的大小及位数是否符合要求；
- 将积的数字和乘数的数字进行比较，如果满足条件则为吸血鬼数。
实际上，由于偶数位之间存在奇数位，上一篇中由于未去除奇数位，从而导致奇数位也加入了循环，故计算时间大大增加。优化后，算法的基本流程如下：
- 获得要求的整数区间[m, n]的最小数m及最大数n的位数，分别为a、b；
- 取出[a, b]之间的偶数列表，记为L（在此之前要判断a、b的大小是否合法）；
- 对L进行循环，每取出其中一个偶数x，就根据x求得对应x位偶数的乘数范围[p, q]；
- 从p到q进行双层循环；
- 相关条件判断及积的计算；
- 积的数字和乘数的数字比较，满足条件则为吸血鬼数。
- 继续对L的循环。
从上述流程可以看出，虽然循环加了一层，但避开了对奇数位的循环，所以可以猜想整个计算时间应该是第一种的一半左右。经实际测试，计算从0到 Integer.MAX_VALUE 之间的吸血鬼数的时间消耗为380699ms，大约为6分多钟，确实节省了一半时间。
附：整个算法的Java代码实现
import java.util.List;
import java.util.ArrayList;
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 >= elen) {
System.out.println("No suitable number exists in this region.");
return;
}
// 该线性表用作偶数位数存放列表
List<Integer> lenList = new ArrayList<Integer>((elen - slen + 1) / 2 + 1);
for(int n = slen; n <= elen; n++) {
if(n % 2 == 0) {
lenList.add(n);
}
}
// 开始对列表循环
for(int len : lenList) {
int begin = (int)Math.pow(10, len / 2 - 1); // 对应len位偶数的、满足位数要求的最小乘数
int finish = begin * 10; // 对应len位偶数的、满足位数要求的最大乘数
for(int i = begin; i < finish; i++) {
boolean boundryReached = false; // ①（见②和处③的解释）
for(int j = i; j < finish; j++) { // j从i开始计数，避免出现(i, j)为(17, 27)、(27, 17)这样的重复情况
if(i % 10 == 0 && j % 10 == 0) { // 两个乘数末尾都为0的情况不满足条件，跳过
continue;
}
int value = i * j;
if(value < 0 || value > end) { // 如果积已经溢出或者超过最大值
if(j == i) { // ② 如果j等于i，说明从此之后，无论i的增长或者j的增长都不会再满足条件，所以需要跳出两层循环（见①和③）
boundryReached = true;
}
break;
}
if(value < start) { // 如果积小于最小值，则继续
continue;
}
if(VampireNumber.getIntegerLength(value) != len) { // 如果积的位数不是期望位数
continue;
}
int[] numList = new int[10]; // 十个数字的计数数组，索引0~9分别代表数字0~9出现的次数
VampireNumber.getNumberCountList(numList, i, j); // 一个数字出现了几次，就将该计数数组对应索引的值加1
while(value != 0) {
numList[value % 10]--; // 将积中出现的数字在数组中对应索引的值减1
value /= 10;
}
boolean isVampireNumber = true;
for(int a = 0; a < numList.length / 2 + 1; a++) { // 循环，用于判断计数数组的每一项是否都为0，如果都为0，说明积是吸血鬼数
if(numList[a] != 0 || numList[numList.length - a - 1] != 0) {
isVampireNumber = false;
break;
}
}
if(isVampireNumber) { // 如果是吸血鬼数，则打印出来
System.out.println("A vampire number found: " + i * j + ", (" + i + ", " + j + ").");
}
}
if(boundryReached) { // ③ 在出现溢出或者超过最大值、并且j等于i的情况下跳出外层循环，因为内层循环的初始条件是j=i，所以此时i再增长的话肯定会溢出或者超过最大值（见①和②）
break;
}
}
}
}
public static int[] getNumberCountList(int[] list, int... nums) {
for(int num : nums) {
do {
list[num % 10]++;
num /= 10;
}while(num != 0);
}
return list;
}
public static int getIntegerLength(int num) {
int len = 0;
do {
len++;
num /= 10;
}while(num != 0);
return len;
}
public static void main(String[] args) {
System.out.println("-------------- Now start computing... --------------");
long s = System.currentTimeMillis();
VampireNumber.find(0, Integer.MAX_VALUE); // 调用find()函数来求从0到Integer.MAX_VALUE之间的所有吸血鬼数
//VampireNumber.find(0, 900000);
long f = System.currentTimeMillis();
System.out.println("------- Computing finished, time used: " + (f - s) + " ms. -------");
}
}