枚举与剪枝_观察算式

观察算式

观察下面的算式：

△△△ * △△ = △△△△

某3位数乘以2位数，结果为4位数

要求：在9个△所代表的数字中，1~9的数字恰好每个出现1次。

暴力破解代码：

package lianxijihe;

import java.util.ArrayList;
import java.util.Date;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class lianxi028 {

	public static void main(String[] args) {
		Set<Integer> set = new HashSet<Integer>();
		long pre = System.currentTimeMillis();
		int a1 ;
		int a2 ;
		int a3 ;
		int a4 ;
		int a5 ;
		int a6 ;
		int a7 ;
		int a8;
		int a9 ;
		 for (int i = 102; i <= 999; i++) {
				a1 =i / 100;
				a2 =i / 10 % 10;
				a3 =i % 10;
				
//			if (a1 * a2* a3 == 0)
//				continue ;// 如果包含0就退出
//			if (a1== a2|| a2== a3
//					|| a1 == a3)
//				continue ;// 如果他们中有一对是相等就退出
			L2: for (int j = 10; j <= 99; j++) {
				set.add(a1);
				set.add(a2);
				set.add(a3);
				a4 =j / 10;
				a5 =j % 10;
//				if (a4*a5 == 0){
//					set.clear();
//					continue L2;// 如果包含0就进行下一轮循环
//				}
//				if (a4 == a5)
//				{
//					set.clear();
//					continue L2;// 如果他们中有一对是相等就进行下一轮循环
//				}

				int k = i * j;
				if (k >= 1023 && k <= 9999) {// 如果他们的结果是4位不重复数字
					a6=k / 1000;
					a7=k / 100 % 10;
					a8=k / 10 % 10;
					a9=k % 10;
					set.add(a4);
					set.add(a5);
					set.add(a6);
					set.add(a7);
					set.add(a8);
					set.add(a9);
					if (set.contains(0))
						set.clear();
					if (set.size() == 9) {// SET集合里一共有9个元素说明找到了9个不重复的数字
						System.out.println(i + "*" + j + "=" + k);
					}

				}
				set.clear();// 清除
			}
		}
		System.out.println(System.currentTimeMillis() - pre);

	}
}

做了减枝判断后代码

package lianxijihe;

import java.util.ArrayList;
import java.util.Date;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class lianxi028 {

	public static void main(String[] args) {
		Set<Integer> set = new HashSet<Integer>();
		long pre = System.currentTimeMillis();
		int a1 ;
		int a2 ;
		int a3 ;
		int a4 ;
		int a5 ;
		int a6 ;
		int a7 ;
		int a8;
		int a9 ;
		 for (int i = 102; i <= 999; i++) {
				a1 =i / 100;
				a2 =i / 10 % 10;
				a3 =i % 10;
				
			if (a1 * a2* a3 == 0)
				continue ;// 如果包含0就退出
			if (a1== a2|| a2== a3
					|| a1 == a3)
				continue ;// 如果他们中有一对是相等就退出
			L2: for (int j = 10; j <= 99; j++) {
				set.add(a1);
				set.add(a2);
				set.add(a3);
				a4 =j / 10;
				a5 =j % 10;
				if (a4*a5 == 0){
					set.clear();
					continue L2;// 如果包含0就进行下一轮循环
				}
				if (a4 == a5)
				{
					set.clear();
					continue L2;// 如果他们中有一对是相等就进行下一轮循环
				}

				int k = i * j;
				if (k >= 1023 && k <= 9999) {// 如果他们的结果是4位不重复数字
					a6=k / 1000;
					a7=k / 100 % 10;
					a8=k / 10 % 10;
					a9=k % 10;
					set.add(a4);
					set.add(a5);
					set.add(a6);
					set.add(a7);
					set.add(a8);
					set.add(a9);
					if (set.contains(0))
						set.clear();
					if (set.size() == 9) {// SET集合里一共有9个元素说明找到了9个不重复的数字
						System.out.println(i + "*" + j + "=" + k);
					}

				}
				set.clear();// 清除
			}
		}
		System.out.println(System.currentTimeMillis() - pre);

	}
}

最优的标准答案是：

package lianxijihe;
public class lianxi012
{
	public static void main(String[] args)
	{
		long pre = System.currentTimeMillis();
		for(int x=10; x<100; x++){
			int a = x/10;
			int b = x%10;
			if(a==0 || b==0 || a==b) continue;
L1:			for(int y=100; y<1000; y++){
				int c = y / 100;
				int d = y % 100 / 10;
				int e = y % 10;
				if(c*d*e==0) continue;
				if(c==a || c==b) continue;
				if(d==a || d==b || d==c) continue;
				if(e==a || e==b || e==c || e==d) continue;
				
				int z = x * y;
				if(z<1000 || z>=10000) continue; // 结果不是4位数
				
				// 分解为位
				int[] r = new int[4];
				for(int i=0; i<r.length; i++){
					r[i] = z % 10;
					z /= 10;
					
					// 与乘数或被乘数有重复
					if(r[i]==0) continue L1;
					if(r[i]==a || r[i]==b || r[i]==c || r[i]==d || r[i]==e) continue L1;
				}
				
				// 本身重复
				if(r[0]==r[1] || r[0]==r[2] || r[0]==r[3]) continue;
				if(r[1]==r[2] || r[1]==r[3]) continue;
				if(r[2]==r[3]) continue; 
				
				System.out.println(x + " * " + y + " = " + x*y);
			}
		}
		System.out.println(System.currentTimeMillis() - pre);
	}
}

枚举与剪枝_观察算式,布布扣,bubuko.com

枚举与剪枝_观察算式

原文：http://blog.csdn.net/u012897654/article/details/24040167