这个问题来源于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 + 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。
实现代码如下：
|
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
/** * vampirenumbers<br /> * 求所有的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)代码实现：
|
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
import java.util.arrays; /** * vampirenumbers2<br /> * 求所有的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 ] = vnvaluestr.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
由于没有找到吸血鬼数的产生机理，所以只好用穷举法。在这里提高性能的方法主要是减少循环次数，减少不必要的计算。
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对的支持。如果你想了解更多相关内容请查看下面相关链接
原文链接：https://blog.csdn.net/u013673976/article/details/43890499
查看更多关于4位吸血鬼数字的java实现思路与实例讲解的详细内容...