JAVA实现的吸血鬼数字算法,高效率版本(同时求助算法高人解惑)

Question

关于吸血鬼数字的解释我就不写了，原文在我的博客里：
http://blog.csdn.net/java2000_net/archive/2009/01/23/3851203.aspx希望能解决里面的关键代码
        // 下面的这个代码，我个人并不知道为什么，汗颜
        if (i_val % 100 == 0 || (i_val - i - j) % 9 != 0) {
          continue;
        }

Answer 1

吸血鬼算法得出的数字不能是两个00结尾的
所以i_val % 100 == 0就直接continue了
至于(i_val - i - j) % 9 != 0的话会导致什么样的数字就不清楚了(数学不好-_-!)，一时间还找不到数学系的同学问问(都回家了)
期待楼下解答

Answer 2

假设val = 1000a + 100b + 10c + d, 因为满足val = x * y, 则有x = 10a + b, y = 10c + d
则val - x - y = 990a + 99b + 9c = 9 * (110a + 11b + c), 所以val - x - y能被9整除。
所以满足该条件的数字必定能被9整除，所以可以直接过滤其他数字。

Answer 3

假设val = 1000a + 100b + 10c + d, 因为满足val = x * y, 则有x = 10a + b, y = 10c + d
则val - x - y = 990a + 99b + 9c = 9 * (110a + 11b + c), 所以val - x - y能被9整除。
所以满足该条件的数字必定能被9整除，所以可以直接过滤其他数字。

Answer 4

晕，怎么回了两次，至于i_val % 100，那就是3楼说的

Answer 5

改正一个小错误，val - x - y应该是990a + 90b = 9 * (110a + 10b)哈 

Answer 6

abcd = 1000a+100b+10c-d
任意的2位组合，如ac,db, 表示为10a+c,10d+b
则abcd - ac-db = 990a+99b+9c-9d 
这个数肯定是9的倍数，
对于其他的2位组合，也成立
所以，对于满足条件的吸血鬼数字，(i_val - i - j) % 9 != 0 肯定成立
不满足这个条件的，则不是吸血贵数字

Answer 7

一、吸血鬼数字的两个因子不能同时以0结尾，故用条件i_val % 100 == 0 先过滤一次。
二、任何4位数i_val都可以表示为1000a+100b+10c+d
如果其是吸血鬼数字，其两个因子是i和j,那么i+j只能有以下六种情况：
1.(i+j)=10a+b+10c+d
2.(i+j)=10a+10b+c+d
3.(i+j)=10a+b+c+10d
4.(i+j)=a+10b+c+10d
5.(i+j)=a+10b+10c+d
6.(i+j)=a+b+10c+10d
所以无论上述的哪种情况下i_val-(i+j)都一定能被9整除，故不满足这个条件的一定不是吸血鬼数字，所以通过条件(i_val - i - j) % 9 != 0再过滤一次。以上是个人的理解，不知道对错，仅供参考，班门弄斧了：）

Answer 8

所谓“吸血鬼数字”就是指位数为偶数的数字(我们算得是4位的)，可以由一对数字相乘而得到，而这对数字各包含乘积的一半位数字，其中从偶数位数字中选取的数字可以任意排列。以两个0截尾的数字是不允许的。例如：1260=21*60 1827=21*87 2187=27*81 
public class bloodSucker {
 6
 7    public static void main(String[] args) {
 8        for(int i = 10; i <= 99; i++){
 9            for(int j = 10; j<= 99; j++){
10                int sun = i*j;
11                if(sun >=1000 && sun <= 9999){
12                    String [] str = String.valueOf(sun).split("");
13                    Arrays.sort(str);    //按照字符的升序排列
14                    String [] str1 =(String.valueOf(i)+String.valueOf(j)).split("");
15                    Arrays.sort(str1);    //对两个Arrays进行比较
16                    if(Arrays.equals(str, str1)){
17                        System.out.println(i+"*"+j+"="+i*j);
18                    }
19                }
20            }
21        }
22
23    }
24
25}

Answer 9

如果x = 10a + b, y = 10c + d ，那么val = x * y 不是应该= 100ac + 10ad + 10bc + bd吗？？

Answer 10

应该是“因为val满足吸血鬼数字，则有x = 10a + b, y = 10c + d”，呵呵

Answer 11

假设val = 1000a + 100b + 10c + d, 拆分成val = x * y而x是a、b、c、d中两个的线性组合，y是另两个的线性组合，系数分别是10和1
则val-x-y
  =val-m1*a-m2*b-m3*c-m4*d  //m1\m2\m3\m4 是10或者是1
  =1000a + 100b + 10c + d-m1*a-m2*b-m3*c-m4*d
  =(1000-m1)a+(100-m2)b+(10-m3)c+(1-m4)d1000-m1等900或者999，能被9整除
100-m2等90或者99，能被9整除
10-m3等0或者9，能被9整除
1-m4等-9或者0，能被9整除所以(1000-m1)a+(100-m2)b+(10-m3)c+(1-m4)d能被9整除
得到val-x-y能被9整除

Answer 12

for (int i = 10; i < 100; i++)
      {   
          from = Math.max(1000 / i, i + 1);   
          to = Math.min(10000 / i, 100);   
          for (int j = from; j < to; j++) {   
          i_val = i * j;   
           if (i_val % 100 == 0 || (i_val - i - j) % 9 != 0) {   
          continue;   
        }   
复制到这里就够了 ，求教j = from中from = Math.max(1000 / i, i + 1)为什么要这么写，另外to = Math.min(10000 / i, 100);   不是始终是100么 ，为什么要多次一举

Answer 13

from取max是为了不重复，至于to取min确实没什么用