java编程思想的一道题（吸血鬼数字）

    吸血鬼数字是指位数为偶数的数字，可以由一对数字相乘而得到，而这对数字各自包含乘积的一半位数的数字，其中从最初的数字中选取的数字任意排序，以2个0结尾的数字是不允许的
    比如说下面的数字是吸血鬼数字
1260 =  21 × 60
1827 = 21 × 87
2187 = 27 × 81；
    写一个程序，找出4位数字所有吸血鬼数据.(我写了个- -，算法我的比较复杂，我想求比较简单的。。。。。)

不知道你要的简单是指代码少还是效率高。
我写了个穷举的算法。

public class Test {

	public static void main(String[] args) {
		Test t = new Test();
		t.vampireNumber();
	}

	public void vampireNumber() {
		for (int i = 10; i < 100; i++) {
			for (int j = 10; j < 100; j++) {
				int product = i * j;
				if (product > 1000 && product < 10000 && product % 100 != 0 && isEqual(product, i, j)) {
					System.out.println(product + "=" + i + "*" + j);
				}
			}
		}
	}

	public boolean isEqual(int product, int i, int j) {
		char[] num1 = ("" + product).toCharArray();
		char[] num2 = ("" + i + j).toCharArray();
		Arrays.sort(num1);
		Arrays.sort(num2);
		return Arrays.equals(num1, num2);
	}
}

楼上的兄弟这个算法很容易搞定，但是穷举的话，可能效率是要低点

自己想的，很丑陋很局限的一种解法，应该是最高效的了，ON

	public static void solution1 () {
		for (int i=1000;i<9999;i++) {
			int a = i/1000;
			int b = i%1000/100;
			int c = i%100/10;
			int d = i%10;

			if (i == (a*10 + b)*(c*10 + d)) {
				System.out.println(i + " = " + a + b + " * " + c + d);
			} else if (i == (a*10 + b)*(d*10 + c)) {
				System.out.println(i + " = " + a + b + " * " + d + c);				
			} else if (i == (b*10 + a)*(c*10 + d)) {
				System.out.println(i + " = " + b + a + " * " + c + d);				
			} else if (i == (b*10 + a)*(d*10 + c)) {
				System.out.println(i + " = " + b + a + " * " + d + c);			
			} else if (i == (a*10 + c)*(b*10 + d)) {
				System.out.println(i + " = " + a + c + " * " + b + d);			
			} else if (i == (a*10 + c)*(d*10 + b)) {
				System.out.println(i + " = " + a + c + " * " + d + d);		
			} else if (i == (c*10 + a)*(b*10 + d)) {
				System.out.println(i + " = " + c + a + " * " + b + d);		
			} else if (i == (c*10 + a)*(d*10 + b)) {
				System.out.println(i + " = " + c + a + " * " + d + b);		
			} else if (i == (a*10 + d)*(c*10 + b)) {
				System.out.println(i + " = " + a + d + " * " + c + b);
			} else if (i == (a*10 + d)*(b*10 + c)) {
				System.out.println(i + " = " + a + d + " * " + b + c);
			} else if (i == (d*10 + a)*(c*10 + b)) {
				System.out.println(i + " = " + d + a + " * " + c + b);
			} else if (i == (d*10 + a)*(b*10 + c)) {
				System.out.println(i + " = " + d + a + " * " + b + c);
			}
		}
	}

楼上的,等于自己算出来然后打印出去的,我晕,我也只能想到穷举,除非有数学性质的解答,按照程序员的思路,应该就是穷举

//: control/E10_Vampire.java
/****************** Exercise 10 *********************
* A vampire number has an even number of digits and
* is formed by multiplying a pair of numbers containing
* half the number of digits of the result. The digits
* are taken from the original number in any order.
* Pairs of trailing zeroes are not allowed. Examples
* include:
* 1260 = 21 * 60
* 1827 = 21 * 87
* 2187 = 27 * 81
* Write a program that finds all the 4-digit vampire
* numbers. (Suggested by Dan Forhan.)
****************************************************/

package control;

public class E10_Vampire {
	public static void main(String[] args) {
		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);
						}
					}
			}
	}
}

/* Output:
15 * 93 : 1395
21 * 60 : 1260
21 * 87 : 1827
27 * 81 : 2187
30 * 51 : 1530
35 * 41 : 1435
80 * 86 : 6880
*///:~
The program does not produce duplicates, and is optimized by using Pete
Hartley’s theoretical result (see the comment inside main( )).
=================================================================
这些练习还是很有挑战性的

public class VampireDigital {

	/**
	 * @param args
	 * 吸血鬼数字是指位数为偶数的数字，可以由一对数字相乘而得到，而这对数字各自包含乘积的一半位数的数字，
	 * 其中从最初的数字中选取的数字任意排序，以2个0结尾的数字是不允许的 
	 * 比如说下面的数字是吸血鬼数字 
	 * 1260 = 21 × 60
	 * 1827 = 21 × 87 
	 * 2187 = 27 × 81
	 * 写一个程序，找出4位数字所有吸血鬼数据
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		for (int i = 1001; i <= 9999; i++) {
			if (i%100 != 0) {
				for (int j = 10; j <= 99; j++) {
					if (i%j == 0 && i%(i/j) == 0 && i/j <= i/(i/j)) {
						String str1 = String.valueOf(i);
						String str2 = String.valueOf(i/j);
						String str3 = String.valueOf(i/(i/j));
						String str11 = Bubble(str1);
						String str22 = Bubble(str2+str3);
						if (str11.equals(str22)) {
							System.out.println(i);
						}
					}
				}
			}
		}
		

	}
	
	public static String Bubble(String str){
	    String result="";
		char [] array=str.toCharArray();		
		java.util.Arrays.sort(array);//java中已有的排序		
	    for(int j=0;j<array.length;j++){
	    	result=result+array[j];
	    }
	    return result;		
	}
	

}

运行结果是：

1260
1395
1435
1530
1827
2187
6880

在穷举时，也有不同的思路，我觉得，这个题是不是考查复杂度的估量？

穷举一：以这个四位数为迭代

 

for ( value in 1000...9999 )
{
    把value 分解为两个2位数a,b，共4!=16种分法
    for (i in 16 种排列法 )
   {
        计算a*b=c
        比较c 与 value
   } 
}

 复杂度约为 9000 * 16 （或者说计算9000*16次乘法）

 

穷举二：以两个两位数分别迭代

 

 

for( 两位数a in 10...99 )
{
    for ( 两位数b in 10...99 )
    {
         计算c=a*b
         判断c中的四位数，是否是a,b的每一位的全排列
    }
}

 复杂度约为： 90 * 90 = 8100 （或说计算8100次乘法）

 

注：判断c中的四位数，是否是a,b的每一位的全排列，这一步可能耗费一些时间，但也取决于用什么方法了。

最差方法就分别遍历2个两位数及这个4位数，分别比较，

复杂度为4*4，这样总的复杂度还是比第一种小。况且乘法计算次数大大减小。

 

总体上来看，从算法复杂度来讲，穷举应该选择第二种。

我来回复一个吧:

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.apache.commons.collections.CollectionUtils;

public class test {
	public static void main(String args[]) {
		for(int x=10;x<100;x++){
			for(int y=10;y<100;y++){
				if(chen(x,y)){//如果是魔鬼数的话则打印出来,同时把这对相乘的数也打印出来
					System.out.println(x*y+"="+x+"*"+y);
				}
			}
		}
	}

	/**
	 * 判断x,y的乘积是否是魔鬼数
	 * @param x
	 * @param y
	 * @return
	 */
	public static boolean chen(int x, int y) {
		int z = x * y;
		String s = String.valueOf(z);
		if (s.length() == 4) {
			String a = String.valueOf(s.charAt(0));
			String b = String.valueOf(s.charAt(1));
			String c = String.valueOf(s.charAt(2));
			String d = String.valueOf(s.charAt(3));
			Map<String,String> list = zuhe(a,b,c,d);
			return isHeshi(x,y,list);
		}
		return false;
	}

	/**
	 * 这个4位数的乘积可以组合成多少种2位数配对的组合
	 * 
	 * @param a
	 * @param b
	 * @param c
	 * @param d
	 * @return
	 */
	public static Map<String,String> zuhe(String a, String b, String c, String d) {
		List<String> l = new ArrayList<String>();
		l.add(a);
		l.add(b);
		l.add(c);
		l.add(d);
		
		Map<String,String> list = new HashMap<String,String>();
		for (String dd : l) {
			List<String> ll = new ArrayList<String>();
			ll.add(dd);
			Collection<String> cc = CollectionUtils.subtract(l, ll);
			for (String e : cc) {
				List<String> lll = new ArrayList<String>();
				lll.add(dd);lll.add(e);
				Collection<String> ccc = CollectionUtils.subtract(l, lll);
				String o ="";
				for(String g:ccc){
					o=o+g;
				}
				list.put(dd+e, o);
			}
		}	
		
		return list;
	}

	/**
	 * 判断原始相乘的一对数是否在排列组合后的2位数的组合中,如果是的话,那么这 对数相乘后的数字就是魔鬼数字
	 * 
	 * @param x
	 *            原始相乘的数x
	 * @param y
	 *            原始相乘的数y
	 * @param l
	 *           这个4位数的乘积可以组合成多少种2位数配对的组合
	 * @return
	 */
	public static boolean isHeshi(int x, int y, Map l) {
		String s = String.valueOf(x);
		String s2 = String.valueOf(y);
		if (l.get(s)!=null && l.get(s).equals(s2)){
			return true;
		}
		return false;
	}
}

最简洁明了的算法，但考虑到乘法是对称算法，所以前后各取一半就行，可以提高一倍的效率