递归问题（二）—Java教程网

前几天看到一个人在论坛里问，如何实现一个字符串数组的全排列问题，底下人都说可以用递归方法实现，我想了会，没想出来，不过有人贴出了他的代码，我这里借用一下：

public class AllSort{ 
    public static void main(String[] args) { 
        char buf[]={'a','b','c'}; 
        perm(buf,0,buf.length-1); 
    } 
    public static void perm(char[] buf,int start,int end){ 
        if(start==end){//当只要求对数组中一个字母进行全排列时，只要就按该数组输出即可 
            for(int i=0;i<=end;i++){ 
                System.out.print(buf[i]); 
            } 
            System.out.println();    
        } 
        else{//多个字母全排列 
            for(int i=start;i<=end;i++){ 
                char temp=buf[start];//交换数组第一个元素与后续的元素 
                buf[start]=buf[i]; 
                buf[i]=temp; 
                printArray(buf); 
                 
                perm(buf,start+1,end);//后续元素递归全排列 
                 
                temp=buf[start];//将交换后的数组还原 
                buf[start]=buf[i]; 
                buf[i]=temp; 
                printArray(buf); 
            } 
        } 
    } 
    public static void printArray (char[] charArray){ 
        System.out.print("Now the array includes: "); 
        for (int i=0; i<charArray.length; i++){ 
            System.out.print(charArray[i]); 
        } 
        System.out.println(""); 
    } 
}

Now the array includes: abc 
Now the array includes: abc 
abc 
Now the array includes: abc 
Now the array includes: acb 
acb 
Now the array includes: abc 
Now the array includes: abc 
Now the array includes: bac 
Now the array includes: bac 
bac 
Now the array includes: bac 
Now the array includes: bca 
bca 
Now the array includes: bac 
Now the array includes: abc 
Now the array includes: cba 
Now the array includes: cba 
cba 
Now the array includes: cba 
Now the array includes: cab 
cab 
Now the array includes: cba 
Now the array includes: abc 

还有一个比较著名的递归问题，就是n皇后问题。这里只给出实现代码，稍后会补上相应的问题说明...

class NQueen{ 
    private int noOfSolutions; 
    private int noOfQueens; 
    private int[] queensInRow; 
     
    public NQueen (){ 
        this.noOfQueens = 8; 
        this.queensInRow = new int[8]; 
        this.noOfSolutions = 0; 
    } 
     
    public NQueen (int queens){ 
        this.noOfQueens = queens; 
        this.queensInRow = new int[noOfQueens]; 
        this.noOfSolutions = 0; 
    } 
     
    public boolean canPlaceQueen (int k, int i){ 
        for (int j=0; j<k; j++){ 
            if ((queensInRow[j]==i) || (Math.abs(queensInRow[j]-i)== Math.abs(j-k))){ 
                return false; 
            } 
        } 
        return true; 
    } 
     
    public void queensConfiguration (int k){ 
        for (int i=0; i<noOfQueens; i++){ 
            if (canPlaceQueen(k, i)){ 
                queensInRow[k] = i; 
                 
                if (k == noOfQueens-1){ 
                    printConfiguration(); 
                } 
                else{ 
                    queensConfiguration(k+1); 
                } 
            } 
        } 
    } 
     
    public void printConfiguration (){ 
        noOfSolutions ++; 
        System.out.print("("); 
         
        for (int i=0; i<noOfQueens-1; i++){ 
            System.out.print(queensInRow[i] +", "); 
        } 
        System.out.println(queensInRow[noOfQueens-1] +")"); 
    } 
     
    public int solutionsCount(){ 
        return noOfSolutions; 
    } 
} 
public class TestNQueen { 
    public static void main (String args[]){ 
        NQueen queen = new NQueen(); 
         
        queen.queensConfiguration(0); 
    } 
} 

(0, 4, 7, 5, 2, 6, 1, 3) 
(0, 5, 7, 2, 6, 3, 1, 4) 
(0, 6, 3, 5, 7, 1, 4, 2) 
(0, 6, 4, 7, 1, 3, 5, 2) 
(1, 3, 5, 7, 2, 0, 6, 4) 
(1, 4, 6, 0, 2, 7, 5, 3) 
(1, 4, 6, 3, 0, 7, 5, 2) 
(1, 5, 0, 6, 3, 7, 2, 4) 
(1, 5, 7, 2, 0, 3, 6, 4) 
(1, 6, 2, 5, 7, 4, 0, 3) 
(1, 6, 4, 7, 0, 3, 5, 2) 
(1, 7, 5, 0, 2, 4, 6, 3) 
(2, 0, 6, 4, 7, 1, 3, 5) 
(2, 4, 1, 7, 0, 6, 3, 5) 
(2, 4, 1, 7, 5, 3, 6, 0) 
(2, 4, 6, 0, 3, 1, 7, 5) 
(2, 4, 7, 3, 0, 6, 1, 5) 
(2, 5, 1, 4, 7, 0, 6, 3) 
(2, 5, 1, 6, 0, 3, 7, 4) 
(2, 5, 1, 6, 4, 0, 7, 3) 
(2, 5, 3, 0, 7, 4, 6, 1) 
(2, 5, 3, 1, 7, 4, 6, 0) 
(2, 5, 7, 0, 3, 6, 4, 1) 
(2, 5, 7, 0, 4, 6, 1, 3) 
(2, 5, 7, 1, 3, 0, 6, 4) 
(2, 6, 1, 7, 4, 0, 3, 5) 
(2, 6, 1, 7, 5, 3, 0, 4) 
(2, 7, 3, 6, 0, 5, 1, 4) 
(3, 0, 4, 7, 1, 6, 2, 5) 
(3, 0, 4, 7, 5, 2, 6, 1) 
(3, 1, 4, 7, 5, 0, 2, 6) 
(3, 1, 6, 2, 5, 7, 0, 4) 
(3, 1, 6, 2, 5, 7, 4, 0) 
(3, 1, 6, 4, 0, 7, 5, 2) 
(3, 1, 7, 4, 6, 0, 2, 5) 
(3, 1, 7, 5, 0, 2, 4, 6) 
(3, 5, 0, 4, 1, 7, 2, 6) 
(3, 5, 7, 1, 6, 0, 2, 4) 
(3, 5, 7, 2, 0, 6, 4, 1) 
(3, 6, 0, 7, 4, 1, 5, 2) 
(3, 6, 2, 7, 1, 4, 0, 5) 
(3, 6, 4, 1, 5, 0, 2, 7) 
(3, 6, 4, 2, 0, 5, 7, 1) 
(3, 7, 0, 2, 5, 1, 6, 4) 
(3, 7, 0, 4, 6, 1, 5, 2) 
(3, 7, 4, 2, 0, 6, 1, 5) 
(4, 0, 3, 5, 7, 1, 6, 2) 
(4, 0, 7, 3, 1, 6, 2, 5) 
(4, 0, 7, 5, 2, 6, 1, 3) 
(4, 1, 3, 5, 7, 2, 0, 6) 
(4, 1, 3, 6, 2, 7, 5, 0) 
(4, 1, 5, 0, 6, 3, 7, 2) 
(4, 1, 7, 0, 3, 6, 2, 5) 
(4, 2, 0, 5, 7, 1, 3, 6) 
(4, 2, 0, 6, 1, 7, 5, 3) 
(4, 2, 7, 3, 6, 0, 5, 1) 
(4, 6, 0, 2, 7, 5, 3, 1) 
(4, 6, 0, 3, 1, 7, 5, 2) 
(4, 6, 1, 3, 7, 0, 2, 5) 
(4, 6, 1, 5, 2, 0, 3, 7) 
(4, 6, 1, 5, 2, 0, 7, 3) 
(4, 6, 3, 0, 2, 7, 5, 1) 
(4, 7, 3, 0, 2, 5, 1, 6) 
(4, 7, 3, 0, 6, 1, 5, 2) 
(5, 0, 4, 1, 7, 2, 6, 3) 
(5, 1, 6, 0, 2, 4, 7, 3) 
(5, 1, 6, 0, 3, 7, 4, 2) 
(5, 2, 0, 6, 4, 7, 1, 3) 
(5, 2, 0, 7, 3, 1, 6, 4) 
(5, 2, 0, 7, 4, 1, 3, 6) 
(5, 2, 4, 6, 0, 3, 1, 7) 
(5, 2, 4, 7, 0, 3, 1, 6) 
(5, 2, 6, 1, 3, 7, 0, 4) 
(5, 2, 6, 1, 7, 4, 0, 3) 
(5, 2, 6, 3, 0, 7, 1, 4) 
(5, 3, 0, 4, 7, 1, 6, 2) 
(5, 3, 1, 7, 4, 6, 0, 2) 
(5, 3, 6, 0, 2, 4, 1, 7) 
(5, 3, 6, 0, 7, 1, 4, 2) 
(5, 7, 1, 3, 0, 6, 4, 2) 
(6, 0, 2, 7, 5, 3, 1, 4) 
(6, 1, 3, 0, 7, 4, 2, 5) 
(6, 1, 5, 2, 0, 3, 7, 4) 
(6, 2, 0, 5, 7, 4, 1, 3) 
(6, 2, 7, 1, 4, 0, 5, 3) 
(6, 3, 1, 4, 7, 0, 2, 5) 
(6, 3, 1, 7, 5, 0, 2, 4) 
(6, 4, 2, 0, 5, 7, 1, 3) 
(7, 1, 3, 0, 6, 4, 2, 5) 
(7, 1, 4, 2, 0, 6, 3, 5) 
(7, 2, 0, 5, 1, 4, 6, 3) 
(7, 3, 0, 2, 5, 1, 6, 4) 

（阅读次数：）