Java 吸血鬼数字(高效版详解)

先来看题


吸血鬼数字是指位数为偶数的数字,可以由一堆数字相乘而得到,而这对数字各包含乘积的一半位数的数字,其中从最初的数字中选取的数字可以任意排序。以两个0结尾的数字是不允许的,例如,下列数字都是“吸血鬼”数字:
1260 = 21 * 60
1827 = 21 * 87
2187 = 27 * 81
写出一个程序,找出4位数的所有吸血鬼数字。

再看代码


实现方法有很多种,我主要解析一下网上流传的不知是哪位大牛写的高效率版本。
代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
   public class VampireNum {
public static void main(String[] args) {
String[] ar_str1, ar_str2;
int sum = 0;
int from;
int to;
int i_val;
int count = 0;
//双重循环穷举
for (int i = 10; i < 100; i++) {
//j=i+1避免重复
from = Math.max(1000 / i, i + 1);
// to = Math.min(10000 / i, 100);
for (int j = from; j < 100; j++) {
i_val = i * j;
//如果对100取余等于0,则该4位数位数为00,不符合要求
//或i_val-i-j对9取余不等于0,也不符合要求
//不符合要求就从新开始循环,继续查找
if (i_val % 100 == 0 || (i_val - i - j) % 9 != 0) {
continue;
}
count++;
//将i_val转换成字符串,然后排序,并进行比较,如果比较结果相等,进行sum+1
ar_str1 = String.valueOf(i_val).split("");
ar_str2 = (String.valueOf(i) + String.valueOf(j)).split("");
Arrays.sort(ar_str1);
Arrays.sort(ar_str2);
if (Arrays.equals(ar_str1, ar_str2)) {
sum++;
System.out.println("第" + sum + "组: " + i + " * " + j + " = " + i_val);
}
}
}
System.out.println("共找到" + sum + "组吸血鬼数");
System.out.println(count);
}
}

运行结果


第1组: 15 * 93 = 1395
第2组: 21 * 60 = 1260
第3组: 21 * 87 = 1827
第4组: 27 * 81 = 2187
第5组: 30 * 51 = 1530
第6组: 35 * 41 = 1435
第7组: 80 * 86 = 6880
共找到7组吸血鬼数 232

解析


因:

吸血鬼数字是四位数的。

得出取值范围:

10 <= i < 100
10 <= j < 100
1000 <= i * j < 10000
1000 / i <= j < 10000/i

为避免重复,j 的起始值应等于 i + 1:

i + 1 < = j

1000 / i < i+1 时:

i +1 <= j

1000 / i > i+1 时:

1000/i <= j

所以区间最小值应该在 j + 11000 / i 中取最大值:

1
from = Math.max(1000 / i, i + 1);

j < 100j < 10000 / i

100 < 10000 / i 时:

j < 100

100 > 1000 / i 时:

j < 1000 / i

所以区间最大值应在 10010000 / i 中取最小值:

1
//			to = Math.min(10000 / i, 100);

为什么这句可以注销呢?

i < 100,所以100 永远小于 10000 / i。
得出:

j 始终小于 100。

再看看代码的主体算法部分:

1
i_val % 100 == 0 || (i_val - i - j) % 9 != 0

因:

末尾两位不能为0

所以能整除100的就过滤掉:

1
i_val % 100 == 0

假设:

i_val = 1000 * a + 100 * b + 10 * c + d
i_val = i * j
i = 10 * a + b
j = 10 * c + d

得出:

i_val - i - j = 990 * a + 99 * b = 9 * (110 * a + 11 * b)

所以 i_val - i - j 一定能被9整除,不能整除的就过滤掉:

1
(i_val - i - j) % 9 != 0

总结


从结果可以看出,该算法循环次数仅为232次,的确是非常高效率的一个精致的小算法,值得品味和学习。
注:以上解析均为个人理解,如有不妥或错误望指正。同时,有不理解的地方请评论或联系我。

评论