吸血鬼数字算法研究

所谓“吸血鬼数字”就是指位数为偶数的数字(我们算得是4位的)，可以由一对数字相乘而得到，而这对数字各包含乘积的一半位数字，其中从偶数位数字中选取的数字可以任意排列。以两个0截尾的数字是不允许的。例如：1260=21*60          1827=21*87          2187=27*81
今天在Thinking in JAVA 中做到的练习题。我先自己写了一个算法，但是总感觉太复杂。后来在网上找到一个比较好的算法。如下：

package org.idcn.jse; 

public class XiXieGui { 
    /** 
     * 吸血鬼数字算法 
     * 如：12*60=1260 
     * YangL. 
     */ 
    public static void main(String[] args) { 
        String[] ar_str1, ar_str2; 
        int sum = 0; 
        for (int i = 10; i < 100; i++) { 
            for (int j = i + 1; j < 100; j++) { 
                int i_val = i * j; 
                if (i_val < 1000 || i_val > 9999) 
                    continue; // 积小于1000或大于9999排除,继续下一轮环 
                ar_str1 = String.valueOf(i_val).split(""); 
                ar_str2 = (String.valueOf(i) + String.valueOf(j)).split(""); 
                java.util.Arrays.sort(ar_str1); 
                java.util.Arrays.sort(ar_str2); 
                if (java.util.Arrays.equals(ar_str1, ar_str2)) { 
                    // 排序后比较,为真则找到一组 
                    sum++; 
                    System.out.println("第" + sum + "组: " + i + "*" + j + "=" 
                            + i_val); 
                } 
            } 
        } 
        System.out.println("共找到" + sum + "组吸血鬼数"); 
    } 
}

这个算法应该是比较简单的了。算法中用到String.valueOf(j)).split("");的方法来把数字转换为字符串，以拆分数字的方法用的很巧妙了。把数字的比较，转换为对字符串的比较，实在高明。

下面是我在《Thinking in Java, 2nd edition, Annotated Solution Guide Revision 1.0》中找到的答案，也就是Thinking in JAVA的官方答案书上的答案。不过个人感觉没有上面的算法好。

//: c03:E11_Vampire.java
// Solution by Dan Forhan
import java.applet.*;
import java.awt.*;

public class Vampire extends Applet {
    private int num1, num2, product;
    private int[] startDigit = new int[4];
    private int[] productDigit = new int[4];
    private int count = 0;
    private int vampCount = 0;
    private int x, y;
    public void paint(Graphics g) {
      g.drawString("Vampire Numbers", 10, 20);
      g.drawLine(10, 22, 150, 22);
      // Positioning for output to applet:
      int column = 10, row = 35;
      for(num1 = 10; num1 <= 99; num1++)
        for(num2 = 10; num2 <= 99; num2++) {
          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;
          count = 0;
          for(x = 0; x < 4; x++)
            for(y = 0; y < 4; y++) {
              if (productDigit[x] == startDigit[y]){
                count++;
                productDigit[x] = -1;
                startDigit[y] = -2;
                if (count == 4) {
                  vampCount++;
                  int a = (int)Math.random() * 100;
                  int b = (int)Math.random() * 100;
                  int c = (int)Math.random() * 100;
                  if (vampCount < 10) {
                    g.drawString("Vampire number     "
                      + vampCount + " is " + num1 +
                      " * " + num2 + " = "+ product,
                      column, row);
                    row += 20;
                  } else {
                    g.drawString("Vampire number    "
                      + vampCount + " is " + num1 +
                      " * " + num2 + " = "+ product,
                      column, row);
                    row += 20;
                  }
                }
              }
            }
        }
    }
} ///:~

来自我的搜狐博客：http://ielin.blog.sohu.com/63617803.html
刚从搜狐把博客搬过来，以后就在这安家了。

评论

6 楼 patrickyao1988 2009-11-03  

第一个命名比较山寨。。。。

5 楼 hand515 2009-11-03  

import java.util.*;

public class Test{
    public static void main(String[] args){
	int[] st=new int[4];
	int[] ed=new int[4];
        for(int i=11;i<100;i++){
		for(int j=(1000/i+1<i?i:1000/i+1);j<100;j++){
			int s=i*j;
			boolean b=true;
			st[0]=i%10;
			st[1]=i/10;
			st[2]=j%10;
			st[3]=j/10;
			ed[0]=s%10;
			ed[1]=(s/10)%10;
			ed[2]=(s/100)%10;
			ed[3]=s/1000;
			Arrays.sort(st);
			Arrays.sort(ed);
			for(int k=0;k<4;k++){
				if(st[k]!=ed[k]){
					b=false;
					break;
				}
			}			
			if(b) System.out.println(i*j+"="+i+"*"+j);
		}
	}
    }
}

我觉得这样比较好，乘法交换律和两个数相乘必须大于1000这两个条件可以少判断一些东西。

4 楼 ningmenglovesoft 2009-09-20  

哎？看了半天眼都看花了。找了半天都不知道你的变量是怎么弄的。。

3 楼 colinzhy 2009-09-20  

我自己也写了个，不过更麻烦，谢谢指教了！

2 楼 jitabc 2008-11-09  

axxxx2000 写道

XiXieGui 怎么不学学下面的命名方法

正在苦学英语中，谢谢您的提醒.

1 楼 axxxx2000 2008-11-09  

XiXieGui
怎么不学学下面的命名方法