code=Java]public Demo1() { int sum[] = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; for (int a = 0; a < 9; a++) { for (int b = 0; b < 9; b++) { for (int c = 0; c < 9; c++) { for (int d = 0; d < 9; d++) { for (int e = 0; e < 9; e++) { for (int f = 0; f < 9; f++) { for (int g = 0; g < 9; g++) { for (int h = 0; h < 9; h++) { for (int i = 0; i < 9; i++) { if ((((sum[a] * 1000) + (sum[b] * 100) + (sum[c] * 10) + sum[d]) * sum[e]) == ((sum[f] * 1000) + (sum[g] * 100) + (sum[h] * 10) + sum[i]) && bj(a, b, c, d, e, f, g, h, i)) { System.out.println(sum[a] + "" + sum[b] + sum[c] + sum[d] + "*" + sum[e] + "=" + sum[f] + sum[g] + sum[h] + sum[i]); } } } } } } } } } } } public boolean bj(int a, int b, int c, int d, int e, int f, int g, int h, int i) { boolean bean = true; String ss[] = (a + "," + b + "," + c + "," + d + "," + e + "," + f + "," + g + "," + h + "," + i).split(","); for (int j = 0; j < 9; j++) { for (int k = 0; k < 9; k++) { if (Integer.parseInt(ss[j]) == Integer.parseInt(ss[k]) && j != k) { bean = false; } } } return bean; }[[/code]
package fillNum;import java.util.ArrayList; import java.util.List;/** * 产生排列数的方法 * @author t00132569 * */ public class Permutation {
public static List<List<Object>> generateCombination(List baseArray) {
Object firstObj = baseArray.get(0); if (baseArray.size() == 1) { List<List<Object>> result = new ArrayList<List<Object>>(); List<Object> inner = new ArrayList<Object>(); inner.add(firstObj); result.add(inner); return result; } baseArray.remove(0); return combineWithArray(firstObj, baseArray); }
private static List<List<Object>> combineWithArray(Object single, List<Object> otherArray) { List<List<Object>> otherCombineArray = generateCombination(otherArray); List<List<Object>> finalResultList = new ArrayList<List<Object>>(); for (int i = 0; i < otherCombineArray.size(); i ++) { List<List<Object>> itemResult = new ArrayList<List<Object>>(); List<Object> combineItem = otherCombineArray.get(i); /*减少计算, 倒着增加*/ for (int j = combineItem.size(); j >= 0; j--) { List<Object> sigleResult = new ArrayList<Object>(); sigleResult.addAll(combineItem); sigleResult.add(j, single); itemResult.add(sigleResult); } finalResultList.addAll(itemResult); } return finalResultList; } }
主算法:package fillNum;import java.util.ArrayList; import java.util.List;public class Main {
private static boolean verify(List<Object> item) { StringBuffer first = new StringBuffer(); String second = null; StringBuffer result = new StringBuffer(); for (int i = 0; i < item.size(); i++) { if (i <= 3 ) { first.append(item.get(i)); } if ( i == 4) { second = item.get(i).toString(); }
if (i > 4) { result.append(item.get(i)); } }
int mul1 = Integer.valueOf(first.toString()); int mul2 = Integer.valueOf(second); int finalRes = Integer.valueOf(result.toString()); if (finalRes == mul1 * mul2) { System.out.println(mul1 + " * " + mul2 + " = " + finalRes); return true; } return false; }
public static void main(String[] args) { List<String> stringList = new ArrayList<String>(); stringList.add("1"); stringList.add("2"); stringList.add("3"); stringList.add("4"); stringList.add("5"); stringList.add("6"); stringList.add("7"); stringList.add("8"); stringList.add("9"); List<List<Object>> list = Permutation.generateCombination(stringList); for (int i = 0; i < list.size(); i++) { List<Object> item = list.get(i); verify(item); }
}}
private static void count() { // the first one should be 1-4 for (int a = 1; a < 5; a ++) { for (int b = 1; b <= 9; b ++) { if (a == b) continue; // the second one cann't equals to the first digit.
for (int c = 1; c <=9 ; c ++) { if (c == a || c == b) continue; // the third one cann't euqals to the first, neither the second.
for (int d = 2; d <=9 ; d++) // the fourth digit cann't be 1 { if (d == a|| d == b|| d == c) continue; // ignore those digits that appeared
// middle is between 2 - 8 for (int middle = 2; middle <= 8; middle ++) { if (middle == a || middle == b || middle == c || middle == d) continue; // ignore those digits that appeared int first = a * 1000 + b * 100 + c * 10 + d;
// the result should between 2000 - 9999 int result = first * middle; if (result > 10000) break;
// then count and find if that a good result. if (resultOK(first, middle, result)) { System.out.println(first + " * " + middle + " = " + result); } } } } } } }
private static boolean resultOK(int first, int middle, int result) { char [] firstC = String.valueOf(first).toCharArray(); char [] resultC = String.valueOf(result).toCharArray(); char [] finalC = new char[10]; for (int i = 0; i < firstC.length; i ++) { finalC [firstC[i] - '0'] ++; }
finalC[middle]++;
for (int i = 0; i < resultC.length; i ++) { finalC [resultC[i] - '0'] ++; }
if (finalC[0] > 0) return false;
for (int i = 1; i < 10; i++) { if (finalC[i] != 1) return false; }
return true; } 1738 * 4 = 6952 1963 * 4 = 7852
11楼的resultOK这个算法什么意思?
穷举法 import java.util.ArrayList; import java.util.Date; import java.util.List;public class Other { public static void main(String args[]) { long now = new Date().getTime(); String str = "123456789"; List list = new Other().getList(str);
// 遍历所有可能,将符合条件的数打印出来 for(int i = 0; i < list.size(); i++){ String num = list.get(i).toString(); int first = Integer.parseInt(num.substring(0, 4)); int second = Integer.parseInt(num.substring(4, 5)); int third = Integer.parseInt(num.substring(5, 9));
/** * 得到字符串全排列 * @param str * @return */ public List getList(String str){ List list = new ArrayList();
StringBuffer sb = new StringBuffer(); int leng = str.length(); int[] a = new int[leng]; boolean[] c = new boolean[leng]; for (int i = 0; i < leng; i++) { a[i] = i + 1; c[i] = false; } int ii = findActiveM(a, c); for (int i = 0; i < str.length(); i++){ sb.append("" + a[i]); } list.add(sb); if (ii >= 0) { do { int activeM = a[ii]; if (c[ii] == false) { swapInt(a, ii, ii - 1); swapBoolean(c, ii, ii - 1); } else { swapInt(a, ii, ii + 1); swapBoolean(c, ii, ii + 1); } sb = new StringBuffer(); for (int i = 0; i < str.length(); i++) { sb.append("" + a[i]); if (a[i] > activeM) c[i] = !c[i]; } list.add(sb); ii = findActiveM(a, c); } while (ii >= 0); }
return list; } private static void swapInt(int[] aa, int a, int b) { int temp = aa[a]; aa[a] = aa[b]; aa[b] = temp; } private static void swapBoolean(boolean[] aa, int a, int b) { boolean temp = aa[a]; aa[a] = aa[b]; aa[b] = temp; } private static int findActiveM(int[] a, boolean[] c) { int first1 = 0, first2 = 0; int m = -1, n = -1; for (int i = 1; i < a.length - 1; i++) { if (c[i] == false) { if ((a[i] > a[i - 1]) && a[i] > first1) { first1 = a[i]; m = i; } } else { if ((a[i] > a[i + 1]) && a[i] > first2) { first2 = a[i]; n = i; } } } if ((c[0] == true) && (a[0] > a[1]) && (a[0] > first2)) { first2 = a[0]; n = 0; } if ((c[a.length - 1] == false) && (a.length > 1) && (a[a.length - 1] > a[a.length - 2]) && (a[a.length - 1] > first1)) { first1 = a[a.length - 1]; m = a.length - 1; } if (first1 >= first2) return m; else return n; } }
思路:穷举第二个乘数(k=?,2~9,1不可能) 然后从第一个乘数的个位开始赋值(=a),x=a*k,就可以得到结果的个位 x%10。同时结果的十位加上 x/10。 同理,再赋值乘数的十位(=b),而这时的结果的十位应该 =b*k%10+(上面余留下来的 x/10) 赋值过程中,用 bArr[9] 对数字的使用情况进行判断。 public static void g() { new Runnable() { public void run() { for (k = 2; k <= 9; k++) { bArr[k - 1] = true; g(3); bArr[k - 1] = false; } } private void g(int c) { if (c < 0) { for (int i = 0; i < aTop.length; i++) { System.out.print(aTop[i] + " "); } System.out.println("\n" + k); for (int i = 0; i < aBottom.length; i++) { System.out.print(aBottom[i] + " "); } System.out.println("\n"); return; } for (int top = 1; top <= 9; top++) { if (!bArr[top - 1]) { bArr[top - 1] = true; int x = top * k + aBottom[c]; int bottom = x % 10; if (bottom > 0 && !bArr[bottom - 1] && (c > 0 || x < 10)) { int y = aBottom[c]; aTop[c] = top; aBottom[c] = bottom; if (c > 0) { aBottom[c - 1] = x / 10; } bArr[bottom - 1] = true; g(c - 1); bArr[bottom - 1] = false; aBottom[c] = y; } bArr[top - 1] = false; } } } private int[] aTop = new int[4]; private int[] aBottom = new int[4]; private boolean[] bArr = new boolean[9]; private int k; }.run(); }
int sum[] = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; for (int a = 0; a < 9; a++) {
for (int b = 0; b < 9; b++) {
for (int c = 0; c < 9; c++) {
for (int d = 0; d < 9; d++) {
for (int e = 0; e < 9; e++) {
for (int f = 0; f < 9; f++) {
for (int g = 0; g < 9; g++) {
for (int h = 0; h < 9; h++) {
for (int i = 0; i < 9; i++) {
if ((((sum[a] * 1000)
+ (sum[b] * 100)
+ (sum[c] * 10) + sum[d]) * sum[e]) == ((sum[f] * 1000)
+ (sum[g] * 100)
+ (sum[h] * 10) + sum[i])
&& bj(a, b, c, d, e, f, g,
h, i)) {
System.out.println(sum[a] + ""
+ sum[b] + sum[c]
+ sum[d] + "*" + sum[e]
+ "=" + sum[f] + sum[g]
+ sum[h] + sum[i]);
} }
}
}
}
} }
} } } } public boolean bj(int a, int b, int c, int d, int e, int f, int g, int h,
int i) {
boolean bean = true;
String ss[] = (a + "," + b + "," + c + "," + d + "," + e + "," + f
+ "," + g + "," + h + "," + i).split(",");
for (int j = 0; j < 9; j++) {
for (int k = 0; k < 9; k++) {
if (Integer.parseInt(ss[j]) == Integer.parseInt(ss[k])
&& j != k) {
bean = false;
}
}
}
return bean;
}[[/code]
import java.util.List;/**
* 产生排列数的方法
* @author t00132569
*
*/
public class Permutation {
public static List<List<Object>> generateCombination(List baseArray)
{
Object firstObj = baseArray.get(0);
if (baseArray.size() == 1)
{
List<List<Object>> result = new ArrayList<List<Object>>();
List<Object> inner = new ArrayList<Object>();
inner.add(firstObj);
result.add(inner);
return result;
}
baseArray.remove(0);
return combineWithArray(firstObj, baseArray);
}
private static List<List<Object>> combineWithArray(Object single, List<Object> otherArray)
{
List<List<Object>> otherCombineArray = generateCombination(otherArray);
List<List<Object>> finalResultList = new ArrayList<List<Object>>();
for (int i = 0; i < otherCombineArray.size(); i ++)
{
List<List<Object>> itemResult = new ArrayList<List<Object>>();
List<Object> combineItem = otherCombineArray.get(i);
/*减少计算, 倒着增加*/
for (int j = combineItem.size(); j >= 0; j--)
{
List<Object> sigleResult = new ArrayList<Object>();
sigleResult.addAll(combineItem);
sigleResult.add(j, single);
itemResult.add(sigleResult);
}
finalResultList.addAll(itemResult);
}
return finalResultList;
}
}
import java.util.List;public class Main {
private static boolean verify(List<Object> item)
{
StringBuffer first = new StringBuffer();
String second = null;
StringBuffer result = new StringBuffer();
for (int i = 0; i < item.size(); i++)
{
if (i <= 3 )
{
first.append(item.get(i));
}
if ( i == 4)
{
second = item.get(i).toString();
}
if (i > 4)
{
result.append(item.get(i));
}
}
int mul1 = Integer.valueOf(first.toString());
int mul2 = Integer.valueOf(second);
int finalRes = Integer.valueOf(result.toString());
if (finalRes == mul1 * mul2)
{
System.out.println(mul1 + " * " + mul2 + " = " + finalRes);
return true;
}
return false;
}
public static void main(String[] args)
{
List<String> stringList = new ArrayList<String>();
stringList.add("1");
stringList.add("2");
stringList.add("3");
stringList.add("4");
stringList.add("5");
stringList.add("6");
stringList.add("7");
stringList.add("8");
stringList.add("9");
List<List<Object>> list = Permutation.generateCombination(stringList);
for (int i = 0; i < list.size(); i++)
{
List<Object> item = list.get(i);
verify(item);
}
}}
{
// the first one should be 1-4
for (int a = 1; a < 5; a ++)
{
for (int b = 1; b <= 9; b ++)
{
if (a == b) continue; // the second one cann't equals to the first digit.
for (int c = 1; c <=9 ; c ++)
{
if (c == a || c == b) continue; // the third one cann't euqals to the first, neither the second.
for (int d = 2; d <=9 ; d++) // the fourth digit cann't be 1
{
if (d == a|| d == b|| d == c) continue; // ignore those digits that appeared
// middle is between 2 - 8
for (int middle = 2; middle <= 8; middle ++)
{
if (middle == a || middle == b || middle == c || middle == d) continue; // ignore those digits that appeared
int first = a * 1000 + b * 100 + c * 10 + d;
// the result should between 2000 - 9999
int result = first * middle;
if (result > 10000) break;
// then count and find if that a good result.
if (resultOK(first, middle, result))
{
System.out.println(first + " * " + middle + " = " + result);
}
}
}
}
}
}
}
private static boolean resultOK(int first, int middle, int result)
{
char [] firstC = String.valueOf(first).toCharArray();
char [] resultC = String.valueOf(result).toCharArray();
char [] finalC = new char[10];
for (int i = 0; i < firstC.length; i ++)
{
finalC [firstC[i] - '0'] ++;
}
finalC[middle]++;
for (int i = 0; i < resultC.length; i ++)
{
finalC [resultC[i] - '0'] ++;
}
if (finalC[0] > 0) return false;
for (int i = 1; i < 10; i++)
{
if (finalC[i] != 1) return false;
}
return true;
}
1738 * 4 = 6952
1963 * 4 = 7852
import java.util.ArrayList;
import java.util.Date;
import java.util.List;public class Other {
public static void main(String args[]) {
long now = new Date().getTime();
String str = "123456789";
List list = new Other().getList(str);
// 遍历所有可能,将符合条件的数打印出来
for(int i = 0; i < list.size(); i++){
String num = list.get(i).toString();
int first = Integer.parseInt(num.substring(0, 4));
int second = Integer.parseInt(num.substring(4, 5));
int third = Integer.parseInt(num.substring(5, 9));
if(first * second == third){
System.out.println(first + " * " + second + " = " + third);
}
}
System.out.println("耗时:" + (new Date().getTime() - now) / 1000.0 + " 秒");
}
/**
* 得到字符串全排列
* @param str
* @return
*/
public List getList(String str){
List list = new ArrayList();
StringBuffer sb = new StringBuffer();
int leng = str.length();
int[] a = new int[leng];
boolean[] c = new boolean[leng];
for (int i = 0; i < leng; i++) {
a[i] = i + 1;
c[i] = false;
}
int ii = findActiveM(a, c); for (int i = 0; i < str.length(); i++){
sb.append("" + a[i]);
}
list.add(sb); if (ii >= 0) {
do {
int activeM = a[ii];
if (c[ii] == false) {
swapInt(a, ii, ii - 1);
swapBoolean(c, ii, ii - 1);
} else {
swapInt(a, ii, ii + 1);
swapBoolean(c, ii, ii + 1);
}
sb = new StringBuffer();
for (int i = 0; i < str.length(); i++) {
sb.append("" + a[i]);
if (a[i] > activeM)
c[i] = !c[i];
}
list.add(sb);
ii = findActiveM(a, c); } while (ii >= 0);
}
return list;
} private static void swapInt(int[] aa, int a, int b) {
int temp = aa[a];
aa[a] = aa[b];
aa[b] = temp;
} private static void swapBoolean(boolean[] aa, int a, int b) {
boolean temp = aa[a];
aa[a] = aa[b];
aa[b] = temp;
} private static int findActiveM(int[] a, boolean[] c) { int first1 = 0, first2 = 0;
int m = -1, n = -1;
for (int i = 1; i < a.length - 1; i++) {
if (c[i] == false) {
if ((a[i] > a[i - 1]) && a[i] > first1) {
first1 = a[i];
m = i;
}
} else {
if ((a[i] > a[i + 1]) && a[i] > first2) {
first2 = a[i];
n = i;
}
}
}
if ((c[0] == true) && (a[0] > a[1]) && (a[0] > first2)) {
first2 = a[0];
n = 0;
}
if ((c[a.length - 1] == false) && (a.length > 1)
&& (a[a.length - 1] > a[a.length - 2])
&& (a[a.length - 1] > first1)) {
first1 = a[a.length - 1];
m = a.length - 1;
}
if (first1 >= first2)
return m;
else
return n;
}
}
然后从第一个乘数的个位开始赋值(=a),x=a*k,就可以得到结果的个位 x%10。同时结果的十位加上 x/10。
同理,再赋值乘数的十位(=b),而这时的结果的十位应该 =b*k%10+(上面余留下来的 x/10)
赋值过程中,用 bArr[9] 对数字的使用情况进行判断。
public static void g() {
new Runnable() { public void run() {
for (k = 2; k <= 9; k++) {
bArr[k - 1] = true;
g(3);
bArr[k - 1] = false;
}
} private void g(int c) {
if (c < 0) {
for (int i = 0; i < aTop.length; i++) {
System.out.print(aTop[i] + " ");
}
System.out.println("\n" + k);
for (int i = 0; i < aBottom.length; i++) {
System.out.print(aBottom[i] + " ");
}
System.out.println("\n");
return;
}
for (int top = 1; top <= 9; top++) {
if (!bArr[top - 1]) {
bArr[top - 1] = true;
int x = top * k + aBottom[c];
int bottom = x % 10;
if (bottom > 0 && !bArr[bottom - 1] && (c > 0 || x < 10)) {
int y = aBottom[c];
aTop[c] = top;
aBottom[c] = bottom;
if (c > 0) {
aBottom[c - 1] = x / 10;
}
bArr[bottom - 1] = true;
g(c - 1);
bArr[bottom - 1] = false;
aBottom[c] = y;
}
bArr[top - 1] = false;
}
}
}
private int[] aTop = new int[4];
private int[] aBottom = new int[4];
private boolean[] bArr = new boolean[9];
private int k;
}.run();
}
for(int i=123456789; i<=987654321; i++) {
check(i);
}
} public static void check(int num) {
String str = String.valueOf(num);
if(str.contains("0"))
return;
for(int i=0; i<str.length(); i++) {
char c = str.charAt(i);
if(i != str.lastIndexOf(c))
return;
}
int num1 = Integer.parseInt(str.substring(0,4));
int num2 = str.charAt(4)-48;
int num3 = Integer.parseInt(str.substring(5));
if(num1 * num2 == num3) {
System.out.println(num1 + "×" + num2 + "=" + num3);
}
}