吸血鬼数字 高效算法

提前声明. 此算法来自 【老紫竹】.
老紫竹CSDN ID:java2000_net
主页http://www.laozizhu.com
废话不多说.直接上代码

package com.javaeye.arrick.util;
import java.util.Arrays;   
/**  
 * 吸血鬼数字,高效率版本.<br>  
 * 一个4位数字，可以拆分2个2位数数字的乘积,顺序不限。<br>  
 * 比如 1395 =15 * 93  
 *   
 * @author 老紫竹(laozizhu.com)  
 */  
public class VampireNumber {   
  public static void main(String[] arg) {   
    String[] ar_str1, ar_str2;   
    int sum = 0;   
    int from;   
    int to;   
    int i_val;   
    int count = 0;   
    // 双重循环穷举   
    for (int i = 10; i < 100; i++) {   
      // j=i+1避免重复   
      from = Math.max(1000 / i, i + 1); //返回两个int值中较大的一个
      to = Math.min(10000 / i, 100);   //返回两个int值中较小的一个
      for (int j = from; j < to; j++) {   
        i_val = i * j;   
        if (i_val % 100 == 0 ||(i_val - i - j) % 9 != 0) {   
          continue;   
        }   
        count++;
        ar_str1 = String.valueOf(i_val).split("");   
        ar_str2 = (String.valueOf(i) + String.valueOf(j)).split("");   
        Arrays.sort(ar_str1);   
        Arrays.sort(ar_str2);
        if (Arrays.equals(ar_str1, ar_str2)) {
           // 排序后比较,为真则找到一组
           // 返回两个Objects数组彼此相等,返回true
          sum++;   
          System.out.println("第" + sum + "组: " + i + "*" + j + "=" + i_val);   
        }   
      }   
    }   
    System.out.println("共找到" + sum + "组吸血鬼数");   
    System.out.println(count);   
  }   
}  

运行结果

第1组: 15*93=1395
第2组: 21*60=1260
第3组: 21*87=1827
第4组: 27*81=2187
第5组: 30*51=1530
第6组: 35*41=1435
第7组: 80*86=6880
共找到7组吸血鬼数
232

count 次数只有232.. 已经算是最高效的了.
而主要的高效代码 只有3行代码

if (i_val % 100 == 0 ||(i_val - i - j) % 9 != 0) {   
  continue;   
}   

而已
i_val % 100 -->都明白什么意思.
(i_val - i -j) % 9 !=0 --> 也许一时想不明白.
请看如下逻辑. 你会一目了然
算法解释：
假设
i_val = 1000a + 100b + 10c + d,
因为满足i_val = x * y,
则有x = 10a + b, y = 10c + d
则i_val - x - y = 990a + 99b + 9c = 9 * (110a + 11b + c)
所以i_val - x - y能被9整除。
所以满足该条件的数字必定能被9整除，所以可以直接过滤其他数字。
完毕.
《Thinking in Java》 (Dan Forhan推荐练习代码)

评论

13 楼 yingwuhahahaha 2010-03-15  

zhanghaocool 写道

345678910 写道

假设
i_val = 1000a + 100b + 10c + d,
因为满足i_val = x * y,
则有x = 10a + b, y = 10c + d

i_val = 1000a + 100b + 10c + d,
i_val = x * y,
x = 10a + b,
y = 10c + d
这些都是条件，并不是推导出来的 "则有x = 10a + b, y = 10c + d " (wrong)

i_val = 1000a + 100b + 10c + d,
如果有吸血鬼数字 i_val ，则有x,y使得下面成立
i_val = x * y,
x = 10a + b
y = 10c + d
或者其它情况如
x = 10a + b
y = 10d + c

无论何种情况，相同项（如a）的系数都是10的m次方-10n次方，都是9的倍数。
楼主有点没说明白

正解。我看楼主的“假设。。则有。。”还在觉得奇怪，这个在数学上是用什么导出来的。

12 楼 zhanghaocool 2010-03-14  

345678910 写道

假设
i_val = 1000a + 100b + 10c + d,
因为满足i_val = x * y,
则有x = 10a + b, y = 10c + d

i_val = 1000a + 100b + 10c + d,
i_val = x * y,
x = 10a + b,
y = 10c + d
这些都是条件，并不是推导出来的 "则有x = 10a + b, y = 10c + d " (wrong)

i_val = 1000a + 100b + 10c + d,
如果有吸血鬼数字 i_val ，则有x,y使得下面成立
i_val = x * y,
x = 10a + b
y = 10c + d
或者其它情况如
x = 10a + b
y = 10d + c

无论何种情况，相同项（如a）的系数都是10的m次方-10n次方，都是9的倍数。
楼主有点没说明白

11 楼 laoshifu 2010-03-14  

345678910 写道

楼主的解法没有体现出数学思路，再好好想想。

同意LS，这式子推理简直荒谬。

10 楼 zhanghaocool 2010-03-13  

banfry 写道

ar_str1 = String.valueOf(i_val).split("");     
不理解，split不指定参考字符串，出来的结果是什么呢？

一个一个单“字符”串（这里字符不同于char）

9 楼 banfry 2010-03-13  

ar_str1 = String.valueOf(i_val).split("");     
不理解，split不指定参考字符串，出来的结果是什么呢？

8 楼 zhanghaocool 2010-03-13  

用string数组不可能高效，改成int数组，时间消耗大概只有原来的1/9

package com.kwzh;

import java.util.Arrays;

public class VampireNumber {

	public static void main(String[] args) {
		float f = System.nanoTime();
		new VampireNumber().vampireArray();
		System.out.println("string array: " + (System.nanoTime() - f)
				+ " nano seconds");
		f = System.nanoTime();
		new VampireNumber().vampireArray2();
		System.out.println("int array: " + (System.nanoTime() - f)
				+ " nano seconds");
	}

	public void vampireArray() {
		int small, big, product, floor = 10, ceil = 100;
		int from, count = 0, sum = 0;
		String[] ar_str1, ar_str2;
		for (small = floor; small < ceil; small++) {
			from = Math.max(1000 / small, small + 1);
			for (big = from; big < ceil; big++) {
				product = small * big;
				if (product % 100 == 0 || (product - small - big) % 9 != 0) {
					continue;
				}
				ar_str1 = String.valueOf(product).split("");
				ar_str2 = (String.valueOf(small) + String.valueOf(big))
						.split("");
				Arrays.sort(ar_str1);
				Arrays.sort(ar_str2);

				if (Arrays.equals(ar_str1, ar_str2)) {
					// 排序后比较,为真则找到一组
					// 返回两个Objects数组彼此相等,返回true
					sum++;
					System.out.println("第" + sum + "组: " + small + "*" + big
							+ "=" + product);
				}
				count++;
			}
		}
		System.out.println(count);
	}

	public void vampireArray2() {
		int small, big, product, floor = 10, ceil = 100;
		int from, count = 0, sum = 0;
		int[] ar_int1 = new int[4], ar_int2 = new int[4];
		for (small = floor; small < ceil; small++) {
			from = Math.max(1000 / small, small + 1);
			for (big = from; big < ceil; big++) {
				product = small * big;
				if (product % 100 == 0 || (product - small - big) % 9 != 0) {
					continue;
				}
				ar_int1[0] = small / 10;
				ar_int1[1] = small % 10;
				ar_int1[2] = big / 10;
				ar_int1[3] = big % 10;
				ar_int2[0] = product / 1000;
				product = product % 1000;
				ar_int2[1] = product / 100;
				product = product % 100;
				ar_int2[2] = product / 10;
				ar_int2[3] = product % 10;
				Arrays.sort(ar_int1);
				Arrays.sort(ar_int2);
				if (Arrays.equals(ar_int1, ar_int2)) {
					sum++;
					System.out.println("第" + sum + "组: " + small + "*" + big
							+ "=" + product);
				}
				count++;
			}
		}
		System.out.println(count);
	}

}

7 楼 zhanghaocool 2010-03-12  

东四环屠夫 写道

吸血鬼数字更高效版本 …… 屠夫版：
http://butcher.iteye.com/blog/613750

呃，我的是检验而非穷举 ……

感觉两个二位数字穷举，比检验四位数更高效

AsWater 写道

to = Math.min(10000 / i, 100);   //返回两个int值中较小的一个 
for (int j = from; j < to; j++) {  
  ......
}

直接写 for (int j=from; j<100; j++) 就可以了。因为i的取值是从10到100，所以10000/i肯定是大于等于100的。

恩，to不需要

6 楼 AsWater 2010-03-12  

to = Math.min(10000 / i, 100);   //返回两个int值中较小的一个 
for (int j = from; j < to; j++) {  
  ......
}

直接写 for (int j=from; j<100; j++) 就可以了。因为i的取值是从10到100，所以10000/i肯定是大于等于100的。

5 楼 jackdong 2010-03-12  

东四环屠夫 写道

吸血鬼数字更高效版本 …… 屠夫版：
http://butcher.iteye.com/blog/613750

呃，我的是检验而非穷举 ……

写的不错 ，但是仔细看了一下 检验的算法也这差不多的思路 应该不会更高效率 只是ruby api的强大 看起来更简洁

4 楼 Darrick 2010-03-12  

vieri122 写道

最好能说一下解题的思路

  回头补上吧.

3 楼 Darrick 2010-03-12  

东四环屠夫 写道

吸血鬼数字更高效版本 …… 屠夫版：
http://butcher.iteye.com/blog/613750

呃，我的是检验而非穷举 ……

Ruby. 不会.　嘿嘿.

2 楼 vieri122 2010-03-12  

最好能说一下解题的思路

1 楼 东四环屠夫 2010-03-12  

吸血鬼数字更高效版本 …… 屠夫版：
http://butcher.iteye.com/blog/613750

呃，我的是检验而非穷举 ……