吸血鬼算法 高效率版本

取自Java 编程思想 第四章 练习10

[java]
import java.util.Arrays;
/**
* 吸血鬼数字,高效率版本.
* 一个4位数字,可以拆分2个2位数数字的乘积,顺序不限。
* 比如 1395 =15 * 93
*
* @author
*/
public class Vampire {
public static void main(String[] arg) {
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 < to; j++) {
i_val = i * j;
//
if (i_val % 100 == 0 || (i_val – i – j) % 9 != 0) {
continue;
}
count++;
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);
}
}
[/java]

假设val = 1000a + 100b + 10c + d, 因为满足val = x * y, 则有x = 10a + b, y = 10c + d
则val – x – y = 990a + 99b + 9c = 9 * (110a + 11b + c), 所以val – x – y能被9整除。
所以满足该条件的数字必定能被9整除,所以可以直接过滤其他数字。

我准许做一下
x*y = val = 1000a + 100b + 10c + d;
我们假设
x = 10a + b, y = 10c + d

x*y-x-y
= val – x-y
= (1000a + 100b + 10c + d) – (10a+b) – (10c +d) = 990a + 99b + 9c
= 9 * (110a + 11b + c);