吸血鬼数字

    今天在看《Java编程思想》的时候遇到求“吸血鬼数字”的问题。

    吸血鬼数字是指位数为偶数的数字，可以由一对数字相乘而得到，这对数字各包含乘积的一半的数字，例如：1260=21*60,1827=21*87……，1260、1827这样的数字就叫做吸血鬼数字。以两个0结尾的数字不是吸血鬼数字。

    我在网上看到了一个比较高效的算法（http://topic.csdn.net/u/20090123/10/8dc0c939-20ae-41f1-a7c1-d05b897b27c7.html）：

import java.util.Arrays;

public class Vampire {

	public static void main(String[] args) {
		int count = 0;//4位的吸血鬼数字的个数
		int product;//乘积
		char[] pArray;//乘积的字符数组
		char[] nArray;//数字的字符数组
		int num = 0;//内层循环体的执行次数
        for(int i = 11;i < 100;i++)
        	for(int j = 1000 / i + 1 > i ? 1000 / i + 1 : i;j < 100;j++) {//关键代码1
        		product = i * j;
        		if(product % 100 == 0 || (product - i - j) % 9 != 0) //关键代码2
        			continue;
        		num++;
        		pArray = String.valueOf(product).toCharArray();
				nArray = (String.valueOf(i) + String.valueOf(j)).toCharArray();
				Arrays.sort(pArray);
				Arrays.sort(nArray);
				if(Arrays.equals(pArray,nArray)) {
					System.out.println(i + "*" + j + "=" + product);
					count++;
				}
        	}
        System.out.println("共找到" + count + "组吸血鬼数字");
        System.out.println("内层循环共执行" + num + "次");
	}
}

   代码解释：

   关键代码1：j的初始值的设定。注意到i和j都是两位数，为避免重复，可设定j不小于i，又因为i和j的乘积大于1000，因此j应取1000/i + 1 与 i中的较大者。如此一来，相比直接设定i = 11,j = i要减少很多内层循环次数。

    关键代码2：根据吸血鬼数字的定义，以两个0结尾的数字不是吸血鬼数字，因此如果乘积能被100整除，就被pass了，另外，假定任意一个4位数字A表示成1000*a + 100*b + 10*c + d的形式，那么如果这个数是吸血鬼数的话，那么它可以表示成两个两位数x,y的乘积的形式，即A = x * y。其中x、y可以表示成x = 10*a + b，y = 10*c + d或x = 10*a + c，y = 10*b + d……之类的形式。

    以x = 10*a + b，y = 10*c + d为例，A - x - y = 990*a + 99*b = 9*(110*a + 11*b)，能被9整除

    x、y的其他形式也同样能被9整除。

程序的执行结果如下：

15*93=1395

21*60=1260

21*87=1827

27*81=2187

30*51=1530

35*41=1435

80*86=6880

共找到7组吸血鬼数字

内层循环共执行243次

如果去掉关键代码2处的判断，则内层循环将会执行3337次，程序效率的提升非常显著。不过这一点非常不容易想到，特做此笔记，加深记忆。 

 

评论

1 楼 luolanchun 2012-07-11