现在小学也不好混哪! 某日我在一本去年的小学四年级寒假作业上看到了这样的一道数学题:”用0,1,2,3,4,5,6,7,8,9这十个数字组成一个加法式子,如X+Y=Z,使得十个数字刚好被用完,并且不被重复使用”. 不过300+700=1000是不符合要求的,因为它把0用了共6次,并且没有用到2,4,5,6,8,9这几个数字. 当时想了半天都做不出来……..
今天想到用java实现一下.我假设符合条件的X和Y都是三位数,Z是四位数. 因为我从来没见过一个两位数加上一个两位数能等于一个六位数,我同样没见过一个三位数加一个四位数能等于一个三位数!
用高中的概率知识里的排列组合来说,只需要A(3,10)一下,再A(3,7)一下,再A(4,4)一下.意思是说,先从十个数字里挑出三个站成一排,有10*9*8种排法, 再从剩下的7个数字里挑出三个排成一排,有7*6*5种排法,最后剩下4个数字,站成一排,有4*3*2*1中排法.
ArrayList one= 从"0123456789"里选三个; //one的元素是这样子的:012,013,014
for(one里的每一个元素i){
ArrayList two=从("0123456789"去掉i)里选三个; //"0123456789"去掉"012"就剩下"3456789"
for(two里的每一个j){
String 剩下的= 从"0123456789"去掉i和j ;//"0123456789"去掉"012",再去掉"345"就剩下"6789"了
如果 (i+j==剩下的 && 剩下的>999){
输出这个算式!
}
}
}
代码如下:
import java.io.*;
import java.util.ArrayList;
public class Test {
ArrayList arrayOne = new ArrayList();
ArrayList arrayTwo = new ArrayList();
ArrayList arrayADD = new ArrayList();
public static void main(String[] args) {
Test test = new Test();
String before = "0123456789";
char[] a = before.toCharArray();
test.select(3, a); //得到了arrayOne
int m = 0;
for (int i = 0; i < test.arrayOne.size(); i++) {
String left = getLeft(test.arrayOne.get(i).toString(), before);
Test testTwo = new Test();
testTwo.select(3, left.toCharArray()); //得到了arrayOne
for (int j = 0; j < testTwo.arrayOne.size(); j++) {
String newLeft = getLeft(test.arrayOne.get(i).toString(),
testTwo.arrayOne.get(j).toString(), before);
doADD(test.arrayOne.get(i).toString(), testTwo.arrayOne.get(j)
.toString(), newLeft);
m++;
}
}
System.out.println(m);
}
/**
* 调用那个递归算法,传入选择的个数和原数组,将排列的可能的种类存在this.arrayOne这个ArrayList中.....
* 相当于概率论里的C(m,n),不关心顺序的那种,与全排列A(m,n)相反....................................
*
* 例如C(2,3)=3, C(2,5)=10........
* A(2,3)=6, A(2,5)=20
* @param k
* @param a
*/
private void select(int k, char[] a) {
char[] result = new char[k];
subselect(0, 1, result, k, a);
}
/**
* 递归调用计算的主体
*
* @param head
* @param index
* @param r
* @param k
* @param a
*/
private void subselect(int head, int index, char[] r, int k, char[] a) {
for (int i = head; i < a.length + index - k; i++) {
if (index < k) {
r[index - 1] = a[i];
subselect(i + 1, index + 1, r, k, a);
} else if (index == k) {
r[index - 1] = a[i];
this.arrayOne.add(new String(r));
subselect(i + 1, index + 1, r, k, a); //递归调用
} else {
return;
}
}
}
/**
* 输入(1,12345), 返回2345
*
* @param now
* @param before
* @return
*/
public static String getLeft(String now, String before) {
String result = "";
for (int i = 0; i < before.length(); i++) {
//System.out.println(before.charAt(i));
int flag = now.indexOf(before.charAt(i));
if (flag == -1) {
result += before.charAt(i);
}
}
return result;
}
/**
* 输入(12, 34, 12345),返回5
* @param now1
* @param now2
* @param before
* @return
*/
public static String getLeft(String now1, String now2, String before) {
String result = "";
for (int i = 0; i < before.length(); i++) {
//System.out.println(before.charAt(i));
int flag1 = now1.indexOf(before.charAt(i));
int flag2 = now2.indexOf(before.charAt(i));
if (flag1 == -1 && flag2 == -1) {
result += before.charAt(i);
}
}
return result;
}
public static void doADD(String one, String two, String three) {
//System.out.println(one + "+" + two + "==" + three + "吗?");
char oneChar[] = one.toCharArray();
char twoChar[] = two.toCharArray();
char threeChar[] = three.toCharArray();
Test allOne = new Test();
allOne.perm(oneChar, 0, oneChar.length - 1); //更新自己的result
Test allTwo = new Test();
allTwo.perm(twoChar, 0, twoChar.length - 1); //更新自己的result
Test allThree = new Test();
allThree.perm(threeChar, 0, threeChar.length - 1); //更新自己的result
int m = 0;
for (int i = 0; i < allOne.arrayADD.size(); i++) {
for (int j = 0; j < allTwo.arrayADD.size(); j++) {
for (int k = 0; k < allThree.arrayADD.size(); k++) {
// System.out.println(allOne.arrayADD.get(i) + "+"
// + allTwo.arrayADD.get(j) + "=="
// + allThree.arrayADD.get(k));
int a=Integer.parseInt(allOne.arrayADD.get(i).toString());
int b=Integer.parseInt(allTwo.arrayADD.get(j).toString());
int c=Integer.parseInt(allThree.arrayADD.get(k).toString());
if((a+b)==c && c>999){
System.out.println(a+"+"+b+"=="(a+b));
}
m++;
}
}
}
//System.out.println(m);
}
public void perm(char[] buf, int start, int end) {
if (start == end) {//当只要求对数组中一个字母进行全排列时，只要就按该数组输出即可（特殊情况）
String result = "";
for (int i = 0; i <= end; i++) {
result += buf[i];
}
this.arrayADD.add(result);
} else {//多个字母全排列（普遍情况）
for (int i = start; i <= end; i++) {//（让指针start分别指向每一个数）
char temp = buf[start];//交换数组第一个元素与后续的元素
buf[start] = buf[i];
buf[i] = temp;
perm(buf, start + 1, end);//后续元素递归全排列
temp = buf[start];//将交换后的数组还原
buf[start] = buf[i];
buf[i] = temp;
}
}
}
}输出结果如下:
324+765==1089
342+756==1098
432+657==1089
423+675==1098
325+764==1089
352+746==1098
632+457==1089
623+475==1098
425+673==1098
452+637==1089
246+789==1035
264+789==1053
426+879==1305
624+879==1503
742+356==1098
724+365==1089
284+769==1053
824+679==1503
249+786==1035
429+876==1305
652+437==1089
625+473==1098
752+346==1098
725+364==1089
286+749==1035
826+479==1305
269+784==1053
629+874==1503
289+764==1053
289+746==1035
829+476==1305
829+674==1503
346+752==1098
364+725==1089
437+652==1089
473+625==1098
347+859==1206
437+589==1026
473+589==1062
743+859==1602
483+579==1062
843+759==1602
349+857==1206
439+587==1026
356+742==1098
365+724==1089
357+849==1206
537+489==1026
573+489==1062
753+849==1602
583+479==1062
853+749==1602
359+847==1206
539+487==1026
637+452==1089
673+425==1098
457+632==1089
475+623==1098
764+325==1089
746+352==1098
476+829==1305
674+829==1503
764+289==1053
746+289==1035
784+269==1053
874+629==1503
487+539==1026
847+359==1206
479+826==1305
749+286==1035
479+583==1062
749+853==1602
489+537==1026
489+573==1062
849+357==1206
849+753==1602
657+432==1089
675+423==1098
765+324==1089
756+342==1098
587+439==1026
857+349==1206
579+483==1062
759+843==1602
589+437==1026
589+473==1062
859+347==1206
859+743==1602
786+249==1035
876+429==1305
679+824==1503
769+284==1053
789+246==1035
789+264==1053
879+426==1305
879+624==1503