服务器之家

服务器之家 > 正文

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

时间:2021-07-25 16:03     来源/作者:Scub

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

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021德云社封箱演出完整版 2021年德云社封箱演出在线看
2021德云社封箱演出完整版 2021年德云社封箱演出在线看 2021-03-15
返回顶部