观察算式
观察以下的算式：
△△△ * △△ = △△△△
某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);
}
}
执行时间是46毫秒。
做了减枝推断后代码
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);
}
}
执行时间是32毫秒
最优的标准答案是：
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);
}
}
执行仅仅有6毫秒 ！
！ 简直牛B。。
。
最新改进仅仅要3毫秒比标准答案还要牛B
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) {
int a1;
int a2;
int a3;
int a4;
int a5;
int a6;
int a7;
int a8;
int a9;
long pre = System.nanoTime();
for (int i = 102; i <= 987; 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 <= 98; j++) {
int k = i * j;
if (k >= 1023 && k <= 9876) {
a4 = j / 10;
a5 = j % 10;
if (a4 * a5 == 0) {
continue L2;// 假设包括0就进行下一轮循环
}
if (a4 == a5 || a4 == a1 || a4 == a2 || a4 == a3
|| a5 == a1 || a5 == a2 || a5 == a3) {
continue L2;// 假设他们中有一对是相等就进行下一轮循环
}
a6 = k / 1000;
a7 = k / 100 % 10;
a8 = k / 10 % 10;
a9 = k % 10;
if(a9%2!=0)continue L2;
if (a6 * a7 * a8 * a9 == 0) {
continue L2;
}
if (a6 == a1 || a6 == a2 || a6 == a3 || a6 == a4
|| a6 == a5 || a7 == a1 || a7 == a2 || a7 == a3
|| a7 == a4 || a7 == a5 || a7 == a6) {
continue L2;
}
if (a8 == a1 || a8 == a2 || a8 == a3 || a8 == a4
|| a8 == a5 || a8 == a6 || a8 == a7) {
continue L2;
}
if (a9 == a1 || a9 == a2 || a9 == a3 || a9 == a4
|| a9 == a5 || a9 == a6 || a9 == a7 || a9 == a8) {
continue L2;
}
System.out.println(i + "*" + j + "=" + k);
}
}
}
System.out.println(System.nanoTime() - pre);
}
}