Java 吸血鬼数字

      吸血鬼数字是指位数为偶数的数字,可以由一对数字相乘而得到,而这对数字各包含乘积的一半位数的数字,其中从最初的数字中选取的数字可以任意排序.

以两个0结尾的数字是不允许的。

 例如下列数字都是吸血鬼数字

1260=21*60

1827=21*87

2187=27*81

比较笨的低效率的做法: 遍历所有四位数, 每生成一个四位数的时候,在双重循环遍历两位数,在两位数的内层循环中判断是否与最外层循环的四位数相等。 如果相等把这些数字都存放到数组,进行排序后比较两组数字,如果相等那么输出这个数就是要找的数字。下面是官方给出的四位吸血鬼数字的参考答案,不得不说,大神就是大神,膜拜!!

private static void vampireNum() { // 官方参考答案  
      
        int[] startDigit = new int[4];  
        int[] productDigit = new int[4];  
        for (int num1 = 10; num1 <= 99; num1++)  
            for (int num2 = num1; num2 <= 99; num2++) {  
                // Pete Hartley's theoretical result: // If x·y is a vampire number then // x·y == x+y (mod 9) if ((num1 * num2) % 9 != (num1 + num2) % 9) continue; int product = num1 * num2; startDigit[0] = num1 / 10; startDigit[1] = num1 % 10; startDigit[2] = num2 / 10; startDigit[3] = num2 % 10; productDigit[0] = product / 1000; productDigit[1] = (product % 1000) / 100; productDigit[2] = product % 1000 % 100 / 10; productDigit[3] = product % 1000 % 100 % 10; int count = 0; for (int x = 0; x < 4; x++) for (int y = 0; y < 4; y++) { if (productDigit[x] == startDigit[y]) { count++; productDigit[x] = -1; startDigit[y] = -2; if (count == 4) System.out.println(num1 + " * " + num2 + " : " + product); } } } } 复制代码

很多人可能对if ((num1 * num2) % 9 != (num1 + num2) % 9) 这个判断条件不是很理解,别急下面我们慢慢来研究一下。

其实官方答案是有说明的,如下:

Let mod be the binary modulo operator and d(x) the sum of the decimal digits of x.

It is well-known that d(x) mod 9 = x mod 9, for all x.

Assume x·y is a vampire. Then it contains the same digits as x and y, and in particular d(x·y) = d(x)+d(y). This leads to:

(x·y) mod 9 = d(x·y) mod 9 = (d(x)+d(y)) mod 9 = (d(x) mod 9 + d(y) mod 9) mod 9

= (x mod 9 + y mod 9) mod 9 = (x+y) mod 9

The solutions to the congruence are (x mod 9, y mod 9) in {(0,0), (2,2), (3,6), (5,8), (6,3), (8,5)}

Only these cases (6 out of 81) have to be tested in a vampire search based on testing x·y for different values of x and y.








意思如下:mod是取余数的意思,java中用%好表示。首先假设一个函数d(x)为x这个数所有数位上数字的总和,如d(1234)= 10,d(2345) = 14,那么有d(x)mod 9 = xmod 9,why?

证明1如下:假设x为一个四位数,个十百千位上的数字分别为a、b、c、d;那么d(x)= a+b+c+d,

x = a+10b +100c+1000d = a+b+c+d+9b+99c+999d所以xmod 9 = (a+b+c+d)mod 9 = d(x)mod 9,证明完毕。

继续往下看:假设x*y的结果是一个吸血鬼数字,那么有d(x·y) = d(x)+d(y),这个不用解释吧,那么有 (x·y) mod 9 = d(x·y) mod 9证明1已经证明了了,从而(x·y) mod 9 =  (d(x)+d(y)) mod 9 = (d(x) mod 9 + d(y) mod 9) mod 9。

说明1:两个数的和对m取余数等于这两个数分别对m取余的和再对m取余,这个应该算是常识,想想就明白了。

既然有(x·y) mod 9  = (d(x) mod 9 + d(y) mod 9) mod 9 由证明1可知(x·y) mod 9 = (d(x) mod 9 + d(y) mod 9) mod 9 = (x mod 9 + y mod 9) mod 9由说明1可知(x·y) mod 9 = (d(x) mod 9 + d(y) mod 9) mod 9 = (x mod 9 + y mod 9) mod 9 =  (x+y) mod 9,所以如果一个数是吸血鬼数字,那么(x·y) mod 9 =  (x+y) mod 9 。所以这个条件if ((num1 * num2) % 9 != (num1 + num2) % 9)成立的,搞清楚了这个,接下来的问题就是怎么去组合了,假如x*y = n,如果n是一个吸血鬼数字,那么组成x和y的数字也是组成n的数字,这个比较简单,就不在多说了。

    原文作者:weixin_33980459
    原文地址: https://blog.csdn.net/weixin_33980459/article/details/88001645
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞