有一个算法问题搞得我很郁闷！（我真是猪脑子，这么简单的居然想不出来！！！）

Question

public class Test{
int[] re;
boolean[] fn;
int len;
int tp;
Test(int n){
len=n;
fn=new boolean[n];
re=new int[len];
}
public static void main(String[] args){
Test a=new Test(5);
a.all();
}
void print(){
for(int i=0;i<len;i++){
System.out.print(Integer.toString(re[i])+"  ");
}
System.out.println();
}
boolean testing(){
return true;
}
public void all(){
if(tp==len){
if(testing()){
print();
return;
}
}
for(int i=1;i<=len;i++){
if(!fn[i-1]){
fn[i-1]=true;
re[tp]=i;
tp++;
all();
tp--;
fn[i-1]=false;
}
}
}
}

Answer 1

转变一个思路，换一个想法（俺做了简单试验，这个做法性能很低，但是你没有性能需求）
1,2,3,4,5,6,7,8,9 九个数字排列最小是多少？ 123456789，最大呢？ 987654321。
所以你可以从MIN到MAX遍历：
for(int i=123456789; i<=987654321; i++  )
对于每个i是否都可以呢？不行，必须剔除有重复数字的i。这个可以这么实现：
<<
    String str = Integer.toString(i);
    byte[] bs = str.getBytes();
    Set temp = new HashSet();
    for(int index=0;index<bs.length;index++) {
        temp.add(new Byte(bs[index]));
    }
    return temp.size()==bs.length;
>>
然后呢，把满足条件的一个数字转换为int[]数组，大致这样：
<<
    String str = Integer.toString(i);
    int[] result = new int[str.length()];
    for(int index=0;index<str.length();index++) {
        result[index] = Character.digit(str.charAt(index), 10);
    }
    return result;
>>
然后再得到是否需要：
<<
    return arr[0]+arr[4]+arr[8]==15;
>>
大致就可以了。这样性能很低。从1亿遍历到9亿(可以使用多线程分段同时遍历)。幸好思路还算比较直接。

Answer 2

public class Test{
int[] re;
boolean[] fn;
int len;
int tp;
int w;
Test(int n){
w=n;
len=n*n;
fn=new boolean[len];
re=new int[len];
}
public static void main(String[] args){
Test a=new Test(3);
a.all();
}
void print(){
for(int i=0;i<w;i++){
for(int j=0;j<w;j++){
System.out.print(Integer.toString(re[i*3+j])+"  ");
}
System.out.println();
}
System.out.println();

}
boolean testing(){
int sum=(int)((1+w*w)*w/2);
int xie1=0,xie2=0;
for(int i=0;i<w;i++){
int hen=0,shu=0;
for(int j=0;j<w;j++){
hen+=re[i*w+j];
shu+=re[i+j*w];
}
if(hen!=sum || shu!=sum){
return false;
}
xie1+=re[(w-1)*(i+1)];
xie2+=re[i+i*w];
}
if( xie1!=sum || xie2!=sum){
return false;
}
return true;
}
public void all(){
if(tp==len){
if(testing()){
print();
return;
}
}
for(int i=1;i<=len;i++){
if(!fn[i-1]){
fn[i-1]=true;
re[tp]=i;
tp++;
all();
tp--;
fn[i-1]=false;
}
}
}
}

Answer 3

to recover(recover)，能不能给个注释！

Answer 4

递归做的，算法没写注释，看起来麻烦，但是结果是对的。import java.util.*;
public class Test{public static void main(String[] args){
    final int EQUAL=15;
 Vector endmy=new Vector();
 Vector result = new Vector();
Integer[] loca=new Integer[]{new Integer(1),new Integer(2),new Integer(3),new Integer(4),new Integer(5),
new Integer(6),new Integer(7),new Integer(8),new Integer(9)};
//Integer[] loca=new Integer[]{new Integer(1),new Integer(2),new Integer(3),new Integer(4),new Integer(5)}; for(int size=1;size<=9;size++)
{
Vector loc=new Vector();
for(int i=0;i<loca.length;i++)
{
loc.add(loca[i]);
}

endmy=leek(loc,size);
//System.out.println(endmy);
//System.out.println(endmy.size());
for(int j=0;j<endmy.size();j++)
{
Vector vec = (Vector)endmy.get(j);
int count=0;
for(int k=0;k<vec.size();k++)
{
count+=((Integer)vec.get(k)).intValue();
}
if(count==EQUAL)
{
result.add(vec);
}
}
}
System.out.println(result);  
}
static Vector leek(Vector loc,int size)
{
Vector endx=new Vector();
if(size==1)
{Vector vvv=new Vector();
for(int i=0;i<loc.size();i++)
{ Vector vv=new Vector();
vv.add(loc.get(i));
vvv.add(vv);
}
return vvv;
}
if(loc.size()==size)
{
Vector tmp=new Vector(); 
for(int i=0;i<loc.size();i++)
tmp.add(loc.get(i));
Vector vx=new Vector();
 vx.add(tmp);
 return vx;
}
else
{
if(loc==null)
{
return null;
}
if(loc.size()==0)
{
return new Vector();
}

Object x=loc.get(0);
//System.out.println("x"+x);
Vector newvec=new Vector();
for(int i=1;i<loc.size();i++)
{
newvec.add(loc.get(i));
}
//System.out.println("new"+newvec);
Vector v=new Vector();
  v=leek(newvec,size);
  //System.out.println("v"+v);
  endx=v;
  Vector v1=new Vector();
  v1=leek(newvec,size-1);
  //System.out.println("v1"+v1);
 
  if(v1.get(0) instanceof Vector)
  {
  for(int j=0;j<v1.size();j++)
{
Vector end=new Vector();
end.add(x);
//end.addAll((Vector)v1.get(j));
for(int k=0;k<((Vector)v1.get(j)).size();k++)
{
end.add(((Vector)v1.get(j)).get(k));
}
endx.add(end);
//System.out.println("count"+endx.size()+endx+"\n");
}
  }
  else
  {
  Vector end1=new Vector();
  end1.add(x);
  for(int i=0;i<v1.size();i++)
 
  end1.add(v1.get(i));
  endx.add(end1);
  //System.out.println("count"+endx.size()+endx+"\n");
}
return endx;
}

}
}

Answer 5

TO cyouryuu(Figo):唉，代码真是没有可读性啊。代码是需要和人来交流的，写成这样，别人怎么看啊？特别是leak方法竟然这么长，嵌套这么多，犯了大忌。

Answer 6

TO:xiaohaiz(老土进城,两眼通红) 
我知道，很久以前java入门时写的,确实写的很烂。等有时间我重写一下（自己也要半天才能看懂），再加个注释。今天没时间了，你可以不管leak方法，leak的功能就是从n个数中取m个数的组合（m<n）。但是确实能用，这末烂的程序你要是看懂了才说明你NB, :)。

Answer 7

public class Test{
int[] re;  //与 tp 构成椎栈. 你说的,有1,2,3,4,5,6,7,8,9九个数字，放在一个一维数组中,,偶就放在这个数组中.,其实是个椎栈.
         int tp;    //椎栈指针.
boolean[] fn;  //fn[n]=true ,说明数字N+1已经放在椎栈里.,以后不能再用了.
int len;   
Test(int n){
len=n;
fn=new boolean[n];
re=new int[len];
}
public static void main(String[] args){
Test a=new Test(5);
a.all();
}
void print(){
for(int i=0;i<len;i++){
System.out.print(Integer.toString(re[i])+"  ");
}
System.out.println();
}
boolean testing(){
return true;
}
public void all(){
if(tp==len){     //是否到了栈顶,就N个数字都放在数组中了
if(testing()){
print();
return;
}
}
for(int i=1;i<=len;i++){       //尝试把1,.....9放在椎栈里
if(!fn[i-1]){        //测试这个数字是否已经放在椎栈里,if not then.放到栈里.
fn[i-1]=true;  //标志数字i被用过.
re[tp]=i;    //与下一行组成压栈动作.
tp++;       //栈指针上移.
all();     //在栈里放下一个数字.直到栈满所有数字都放完.
tp--;    //出栈,尝试下一个数字.
fn[i-1]=false;//置当前数字为无用过,因为已经出栈了.
}
}
}
}
v

Answer 8

可以用9个连续嵌套的循环，在第1个循环中产生一个b[0]，b[0]=a[A](A为控制循环的变量),下一个循环中产生b[1]，b[1]=a[B](B为控制循环的变量)，依此类推，在最后一个循环中ArrayList的add()方法把数组b加入到ArrayList，使之作为ArrayList的一个元素，要注意的是,在每个循环中需要赋给b[]的a[i]值不能和前面已赋值的b[]相等！这样下来ArraList中共有9!个数组，然后一个数组一个数组的判断就可以了
if(((int[])arralist.get(i))[0]+((int[])arralist.get(i))[4]+((int[])arralist.get(i))[8]==15) {code;}

Answer 9

int[] num = {1,2,3,4,5,6,7,8,9};
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
{
for(int x=1;x<=9;x++)
{
if((num[i]+num[j]+num[x]==15)&&(i!=j)&&(j!=x)&&(i!=x))
{
System.out.println(num[i]+" "+num[j]+" "+num[x]);
}
}
}
}

Answer 10

public class Calgon2  {
int[] re;
boolean[] fn;
int len,tp,w,sum,xi;
Calgon2(int n){
w=n;
len=n*n;
fn=new boolean[len];
re=new int[len];
sum=(int)((1+w*w)*w/2);
xi=w*(w-1);
}
void print(){
for(int i=0;i<w;i++){
    for(int j=0;j<w;j++){
        System.out.print(Integer.toString(re[i*w+j])+"  ");
    }
    System.out.println();
}
System.out.println();
}
boolean preTest(){
if(((tp+1)%w)==0){
int hen=0;
for(int j=0;j<w;j++){
hen+=re[tp-j];
}
if(hen!=sum){
return false;
}
}
if(tp==xi){
int xie=0;
for(int i=0;i<w;i++){
xie+=re[(w-1)*(i+1)];
}
if( xie!=sum){
return false;
}
}
if(tp>=xi){
int shu=0;
for(int j=0;j<w;j++){
shu+=re[tp-j*w];
}
if(shu!=sum){
return false;
}
}
if(tp==(len-1)){
int xie=0;
for(int i=0;i<w;i++){
xie+=re[i+i*w];
}
if( xie!=sum){
return false;
}
}
return true;
}
public void all(){
if(tp==len){
print();
return;
}
for(int i=1;i<=len;i++){
if(!fn[i-1]){
re[tp]=i;
if(preTest()){
fn[i-1]=true;
tp++;
all();
tp--;
fn[i-1]=false;
}
}
}
}
public static void main(String[] args){
Calgon2 a=new Calgon2(4);
a.all();
}
} ,改进算法,可求出四价幻方

Answer 11

1  2  15  16  
12  14  3  5  
13  7  10  4  
8  11  6  9  1  2  15  16  
13  14  3  4  
12  7  10  5  
8  11  6  9  1  2  16  15  
13  14  4  3  
12  7  9  6  
8  11  5  10  1  3  14  16  
10  13  4  7  
15  6  11  2  
8  12  5  9  1  3  14  16  
12  13  4  5  
15  8  9  2  
6  10  7  11  1  3  14  16  
15  13  4  2  
10  6  11  7  
8  12  5  9  1  3  14  16  
15  13  4  2  
12  8  9  5  
6  10  7  11  1  3  16  14  
8  15  2  9  
13  6  11  4  
12  10  5  7  1  3  16  14  
12  15  2  5  
13  10  7  4  
8  6  9  11  1  3  16  14  
13  15  2  4  
8  6  11  9  
12  10  5  7  1  3  16  14  
13  15  2  4  
12  10  7  5  
8  6  9  11  1  4  13  16  
8  14  3  9  
15  5  12  2  
10  11  6  7  1  4  13  16  
8  15  2  9  
14  5  12  3  
11  10  7  6  
.......................too many

Answer 12

import java.util.*;
final public class Calgon4  {
int[] re;
boolean[] fn;
int len;
int tp;
int w;
int sum;
int xi;
int count;
int[] shen;
int[] sshu;
int xie1,xie2;
boolean pri;
Calgon4(int n){
w=n;
len=n*n;
fn=new boolean[len];
re=new int[len];
sshu=new int[w];
shen=new int[w];
sum=(int)((1+w*w)*w/2);
xi=len-w;
}
void print(){
for(int i=0;i<w;i++){
for(int j=0;j<w;j++){
System.out.print(Integer.toString(re[i*w+j])+"\t");
}
System.out.println();
}
System.out.println();

}
boolean preTest(){
int hang=(int)(tp/w);
int hen=shen[hang];
int x1=xie1;
int x2=xie2;
int set=tp%w;
int shu=sshu[set];
hen+=re[tp];
shu+=re[tp];
if((hen>(sum-w+set+1)) || (shu>(sum-w+(int)(tp/w)+1))|| (hen+len*(w-(tp%w)-1)<sum)|| (shu+len*(w-(int)(tp/w)-1)<sum)){
return false;
}
if( (set==(w-1)) && hen!=sum){
return false;
}
if( tp>=xi && shu!=sum){
return false;
}
if( ((tp%(w-1))==0) && tp!=0 && tp!=(len-1)){
x1+=re[tp];
if( (x1>(sum-w+(int)(tp/w)+1)) || (x1+len*(w-(int)(tp/w)-1)<sum) ){
return false;
}
if(tp==xi && x1!=sum){
return false;
}
}
if( (tp%(w+1))==0){
x2+=re[tp];
if(x2>(sum-w+(int)(tp/w)+1) || (x2+len*(w-(int)(tp/w)-1)<sum) ){
return false;
}
if(tp==(len-1)&&x2!=sum){
return false;
}
}
if(tp==len-2*w-1 && shu==xie2){
return false;
}
if(tp==len+2-3*w && x1==sshu[0]){
return false;
}
if(tp==len-1-w && shu!=xie2){
return false;
}
if(tp==len-2-w&&hen==shu){
return false;
}
shen[hang]=hen;
xie1=x1;
xie2=x2;
sshu[set]=shu;
return true;
}
void all(){
if(tp==len){
count++;
if(pri){
print();
}
return;
}
int i;
if( tp>=len-w){
i=sum-sshu[tp%w];
if(i>0&&i<=len){
tryput(i);
}
}else if(((tp+1)%w)==0){
i=sum-shen[(int)(tp/w)];
if(i>0&&i<=len){
tryput(i);
}
}else if(tp==len+1-2*w){
i=sshu[0]-xie1;
if(i>0&&i<=len){
tryput(i);
}
}else{
for(i=1;i<=len;i++){
tryput(i);
}
}
}
void tryput(int i){
if(!fn[i-1]){
re[tp]=i;
if(preTest()){
fn[i-1]=true;
tp++;
all();
tp--;
fn[i-1]=false;
rolTest();
}
}
}
void rolTest(){
shen[(int)(tp/w)]-=re[tp];
sshu[tp%w]-=re[tp];
if( (tp%(w-1))==0&& tp!=0 && tp!=(len-1)){
xie1-=re[tp];
}
if( (tp%(w+1))==0){
xie2-=re[tp];
}
}
public static void main(String[] args){
long  i= (new Date()).getTime();
Calgon4 a;
if(args.length>0){
a=new Calgon4(Integer.parseInt(args[0]));
if(args.length==2){
a.pri=true;
}
}else{
a=new Calgon4(3);
}
a.all();
System.out.println("all print: "+a.count );
i=(new Date()).getTime()-i;
System.out.println("use time: "+i+"  millisecond");
}
}
改进版,速度有了提升.可求出五价幻方,