4位吸血鬼数字的java实现思路与实例讲解

4位吸血鬼数字的java实现思路与实例讲解

这个问题来源于java编程思想一书，所谓“吸血鬼数字”就是指位数为偶数的数字，可以由一对数字相乘而得到，而这对数字各包含乘积的一半位数字，其中从偶数位数字中选取的数字可以任意排列。例如：

1260=21*60，1827=21*87，2187=27*81……

先列出结果：

一共7个：

1260=21*60，1395=15*93，1435=41*35，1530=51*30，1827=87*21，2187=27*81，6880=86*80

第一种思路对所有的4位数进行穷举，假设这个4位数是abcd，可以表示为1000a+100b+10c+d。那么由这个4位数中抽出的2位数的组合有如下12种（abcd分别为0-9的数字，能作为X、Y的十位上的数字必为1-9）：

①X=10*a + b, Y=10*c + d ---不可能

②X=10*a + b, Y=10*d + c ---不可能

③X=10*a + c, Y=10*b + d ---不可能

④X=10*a + c, Y=10*d + b ---不可能

⑤X=10*a + d, Y=10*b + http://c ---不可能

⑥X=10*a + d, Y=10*c + b

⑦X=10*b + a, Y=10*c + d

⑧X=10*b + a, Y=10*d + c

⑨X=10*b + c, Y=10*d + a ---不可能

⑩X=10*b + d, Y=10*c + a

⑾X=10*c + a, Y=10*d + b

⑿X=10*c + b, Y=10*d + a

这12种组合中，有没有可能其中某些情况是不可能满足1000a+100b+10c+d=X*Y的？如果能直接去掉就能减少不必要的计算。

假设①可能找出匹配的吸血鬼数字，那么存在等式：(10*a + b)*(10*c + d) = 1000a+100b+10c+d = 100*(10*a + b) + 10*c + d

<=>(10*a + b)*(10*c + d - 100) = 10*c + d

因为左边(10*c + d - 100)是负数，而右边为正数，不可能相等；又因为在上式中c/d具有互换性，故不可能通过①②找到吸血鬼数。

假设③可能找出匹配的吸血鬼数字，那么存在等式：(10*a + c)*(10*b + d) = 1000a+100b+10c+d

<=>100*a*b + 10*(a*d+b*c) + cd = 100*a*b - 100*a*b + 1000*a + 100*b + 10*c +d = 100*a*b + 10*[10*a*(10-b) + 10*b] + 10*c +d

<=>10*(a*d+b*c) + cd = 10*[10*a*(10-b) + 10*b] + 10*c +d

因为两边的子项都有a*d<10*a*(10-b)，b*c<10*b，cd<10*c +d，所以右边恒大于左边；又因为在上式中b/d具有互换性，故不可能通过③④找到吸血鬼数。

假设10*b + c的组合⑤能找到吸血鬼数字，那么存在等式：(10*a + d)*(10*b + c) = 1000*a + 10*(10*b + c) + d

<=>(10*b + c)*(10*a + d - 10) = 1000*a + d = 100*(10a + d/100)

因为左边(10*b + c)<100，(10*a + d - 10)<(10a + d/100)，所以右边恒大于左边；又因为在上式中a/d具有互换性，故不可能通过⑤⑨找到吸血鬼数。

另外4位数中包含两个及以上0的是不可能为吸血鬼数字，原因：假如包含2个零，则只能拆出10*a和10*b形式，乘积的结果后两位必为ZZ00的形式；于是等式就退化为a*b =10*a + b，变换为b=10*a/(a-1) >10,而b不可能大于10。

实现代码如下：

/**

* VampireNumbers

* 求所有的4位吸血鬼数

* @author South Park

*/

public final class VampireNumbers {

private static final StringBuilder outputStr = new StringBuilder(14);

private static final String equalSign = " = ";

private static final String multiSign = " * ";

/**

* 如果这两个2位数的乘积等于原来的数则成功，打印该数字

* @param i 4位数的值

* @param m 其中一个2位数

* @param n 另外一个2位数

*/

private static final void productTest (final int i, final int m, final int n) {

// 如果满足条件，就输出

if(m * n == i) {

outputStr.append(i).append(equalSign).append(m).append(multiSign).append(n);

System.out.println(outputStr.toString());

outputStr.delete(0, 14);

}

}

/**

* 从1011开始到9998，循环尝试每个4位数的各种分拆组合

* @param args

*/

public static void main(String[] args) {

int count = 0;// 计数循环次数

long startTime = System.nanoTime();

// 分别表示千百十各位

int a,b,c,d;

// 4位数中含零的个数

int zeroCount = 0;

for(short i = 1011; i < 9999; i++) {

zeroCount = 0;

String value = ""+i;

// 获取各位中的值(0-9)

a = value.charAt(0) - 48;//千位

b = value.charAt(1) - 48;//百位

c = value.charAt(2) - 48;//十位

d = value.charAt(3) - 48;//个位

if (b == 0)

zeroCount++;

if (c == 0)

zeroCount++;

if (d == 0)

zeroCount++;

// 数字中含有2个以上的零排除

if (zeroCount >= 2) {

continue;

}

count++;

//productTest(i, 10*a + b, 10*c + d);

//productTest(i, 10*a + b, 10*d + c);

//productTest(i, 10*a + c, 10*b + d);

//productTest(i, 10*a + c, 10*d + b);

//productTest(i, 10*a + d, 10*b + c);

productTest(i, 10*a + d, 10*c + b);

productTest(i, 10*b + a, 10*c + d);

productTest(i, 10*b + a, 10*d + c);

//productTest(i, 10*b + c, 10*d + a);

productTest(i, 10*b + d, 10*c + a);

productTest(i, 10*c + a, 10*d + b);

productTest(i, 10*c + b, 10*d + a);

}

System.out.println(System.nanoTime() - startTime);

// 输出循环次数

System.out.println("loop count:" + count);

}

}

输出结果：

1260 = 21 * 60

1395 = 15 * 93

1435 = 41 * 35

1530 = 51 * 30

1827 = 87 * 21

2187 = 27 * 81

6880 = 86 * 80

6880 = 80 * 86

12360961

loop count:8747

第二种方式是对分解后的一对XY入手，从10到99进行双重循环穷举，由于乘积结果必须是4位数，也就是范围为1000到9999，故可对第二层循环进行范围限定，减少循环次数。从结果来看，第二种方式的循环次数较少，时间也更少。

对于4位吸血鬼数，必有X*Y-X-Y为9的倍数，因为X*Y-X-Y只有下列6种结果：

9*(110*a + 11*b)

9*(110*a + 10*b + c)

9*(110*a + 11*b + c - d)

9*(111*a + 10*b)

9*(111*a + 11*b - d)

9*(111*a + 10*b + c - d)

代码实现：

import java.util.Arrays;

/**

* VampireNumbers2

* 求所有的4位吸血鬼数

* @author South Park

*/

public final class VampireNumbers2 {

private static final StringBuilder outputStr = new StringBuilder(14);

private static final String equalSign = " = ";

private static final String multiSign = " * ";

/**

* 如果这两个2位数的乘积等于原来的数则成功，打印该数字

* @param i 4位数的值

* @param m 其中一个2位数

* @param n 另外一个2位数

*/

private static final void printVN (final int i, final int m, final int n) {

outputStr.append(i).append(equalSign).append(m).append(multiSign).append(n);

System.out.println(outputStr.toString());

outputStr.delete(0, 14);

}

/**

* 从11开始到99，双重循环尝试每种组合的4位数乘积结果是否刚好包含原来两个2位数的数字

* @param args

*/

public static void main(String[] arg) {

int count = 0;// 计数循环次数

long startTime = System.nanoTime();

String vnValueStr = "";

String multiValueStr = "";

char[] vnValueArr = new char[4];

char[] multiValueArr = new char[4];

int from;

int to;

int vampireNumbers;

// 双重循环穷举

for (int i = 11; i < 100; i++) {

// 通过对from和to的计算，缩小第二重循环的次数；j=i+1避免重复

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

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

for (int j = from; j < to; j++) {

count++;

vampireNumbers = i * j;

// 过滤掉非吸血鬼数

if ((vampireNumbers - i - j) % 9 != 0) {

continue;

}

vnValueStr = "" + vampireNumbers;

vnValueArr[0] = vnValueStr.charAt(0);

vnValueArr[1] = vnValueStr.charAt(1);

vnValueArr[2] = vnVaQivsvcDlueStr.charAt(2);

vnValueArr[3] = vnValueStr.charAt(3);

multiValueStr = "" + i + j;

multiValueArr[0] = multiValueStr.charAt(0);

multiValueArr[1] = multiValueStr.charAt(1);

multiValueArr[2] = multiValueStr.charAt(2);

multiValueArr[3] = multiValueStr.charAt(3);

Arrays.sort(vnValueArr);

Arrays.sort(multiValueArr);

if (Arrays.equals(vnValueArr, multiValueArr)) {// 排序后比较,为真则找到一个吸血鬼数

printVN(vampireNumbers, i, j);

}

}

}

System.out.println(System.nanoTime() - startTime);

// 输出循环次数

System.out.println(count);

}

}

输出结果：

1395 = 15 * 93

1260 = 21 * 60

1827 = 21 * 87

2187 = 27 * 81

1530 = 30 * 51

1435 = 35 * 41

6880 = 80 * 86

3024115

3269

由于没有找到吸血鬼数的产生机理，所以只好用穷举法。在这里提高性能的方法主要是减少循环次数，减少不必要的计算。

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对我们的支持。如果你想了解更多相关内容请查看下面相关链接

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。