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

2023-08-25 13:25:05 61

这个问题来源于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。

实现代码如下：

/**
*VampireNumbers

*求所有的4位吸血鬼数
*@authorSouthPark
*/
publicfinalclassVampireNumbers{
privatestaticfinalStringBuilderoutputStr=newStringBuilder(14);
privatestaticfinalStringequalSign="=";
privatestaticfinalStringmultiSign="*";
/**
*如果这两个2位数的乘积等于原来的数则成功，打印该数字
*@parami4位数的值
*@paramm其中一个2位数
*@paramn另外一个2位数
*/
privatestaticfinalvoidproductTest(finalinti,finalintm,finalintn){
//如果满足条件，就输出
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位数的各种分拆组合
*@paramargs
*/
publicstaticvoidmain(String[]args){
intcount=0;//计数循环次数
longstartTime=System.nanoTime();
//分别表示千百十各位
inta,b,c,d;
//4位数中含零的个数
intzeroCount=0;
for(shorti=1011;i<9999;i++){
zeroCount=0;
Stringvalue=""+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("loopcount:"+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
loopcount: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)

代码实现：

importjava.util.Arrays;
/**
*VampireNumbers2

*求所有的4位吸血鬼数
*@authorSouthPark
*/
publicfinalclassVampireNumbers2{
privatestaticfinalStringBuilderoutputStr=newStringBuilder(14);
privatestaticfinalStringequalSign="=";
privatestaticfinalStringmultiSign="*";
/**
*如果这两个2位数的乘积等于原来的数则成功，打印该数字
*@parami4位数的值
*@paramm其中一个2位数
*@paramn另外一个2位数
*/
privatestaticfinalvoidprintVN(finalinti,finalintm,finalintn){
outputStr.append(i).append(equalSign).append(m).append(multiSign).append(n);
System.out.println(outputStr.toString());
outputStr.delete(0,14);
}
/**
*从11开始到99，双重循环尝试每种组合的4位数乘积结果是否刚好包含原来两个2位数的数字
*@paramargs
*/
publicstaticvoidmain(String[]arg){
intcount=0;//计数循环次数
longstartTime=System.nanoTime();
StringvnValueStr="";
StringmultiValueStr="";
char[]vnValueArr=newchar[4];
char[]multiValueArr=newchar[4];
intfrom;
intto;
intvampireNumbers;
//双重循环穷举
for(inti=11;i<100;i++){
//通过对from和to的计算，缩小第二重循环的次数；j=i+1避免重复
from=Math.max(1000/i+1,i+1);
to=Math.min(10000/i,100);
for(intj=from;j
输出结果：

1395=15*93

1260=21*60

1827=21*87

2187=27*81

1530=30*51

1435=35*41

6880=80*86

3024115

3269

由于没有找到吸血鬼数的产生机理，所以只好用穷举法。在这里提高性能的方法主要是减少循环次数，减少不必要的计算。
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对毛票票的支持。如果你想了解更多相关内容请查看下面相关链接

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

热门推荐

随机推荐