計算以下代碼對函數

Question

的recusive調用次數，我希望能夠計算到placeQueens()的遞歸調用次數以及調用isUnderAttack()的次數。我試着在地方的第一行添加int counter = 0Queens（）並在queenPlaced = placeQueens(column+1);之後增加它，但我不斷收到一些奇怪的數字。有沒有辦法做到這一點？我的代碼看起來有多高效？

這是輸出：

1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 
Queen PLACED in [3][7] 
Queen Placed: 1 
Queen Placed: 1 
Queen Placed: 1 
Queen Placed: 1 
Queen Placed: 2 
Queen Placed: 3 
Queen Placed: 3 
Queen Placed: 1 

當我爲此在placeQueens（）

if (!isUnderAttack(row, column)) 
{ 
setQueen(row, column); //consider next square in column 
queenPlaced = placeQueens(column+1); 
counter++; 
System.out.println("Queen Placed: "+counter); 
//if no queen is possible in next column, 

。

public class Queens 
{ 
    //squares per row or column 
    public static final int BOARD_SIZE = 8; 

    //used to indicate an empty square 
    public static final int EMPTY = 0; 

    //used to indicate square contains a queen 
    public static final int QUEEN = 1; 

    private int board[][]; //chess board 

    //public int queens=0; 

    public Queens() 
    { 
     //constructor: Creates an empty square board. 
     board = new int[BOARD_SIZE][BOARD_SIZE]; 

     for (int row = 0; row < BOARD_SIZE; row++) 
     { 
      for (int column = 0; column < BOARD_SIZE; column++) 
      { 
        board[row][column] = EMPTY; 
      } 
     } 
    } 


    //clears the board 
    //Precondition: None 
    //Postcondition: Sets all squares to EMPTY 
    public void clearBoard() 
    { 
     //loops through the rows 
     for(int row = 0; row < BOARD_SIZE; row++) 
     { 
      //loops through the columns 
      for (int column = 0; column < BOARD_SIZE; column++) 
      { 
       board[row][column] = EMPTY; 
      } 
     } 
    } 


    //Displays the board 
    //precondition: None 
    //postcondition: Board is written to standard output; 
    //zero is an EMPTY square, one is a square containing a queen (QUEEN). 
    public void displayBoard() 
    { 
     //int counter = 0; 
     for (int row = 0; row < BOARD_SIZE; row++) 
     { 
      System.out.println(""); 

      for (int column = 0; column < BOARD_SIZE; column++) 
      { 
       System.out.print(board[row][column] + " "); 
       //if (board[row][column] == QUEEN) 
       //{  
       // counter++; 
       //} 
      } 
     } 
     System.out.println(); 
     //System.out.println("Number of Recursive Calls to placeQueens: " + counter); 
    } 



    //Places queens in columns of the board beginning at the column specified. 
    //Precondition: Queens are placed correctly in columns 1 through column-1. 
    //Postcondition: If a solution is found, each column of the board contains one queen and 
    //method returns true; otherwise, returns false (no solution exists for a queen anywhere in column specified). 
    public boolean placeQueens(int column) 
    { 
     if(column >= BOARD_SIZE) 
     { 
      return true; //base case 
     } 
     else 
     { 
      boolean queenPlaced = false; 
      int row = 0; // number of square in column 
      int queensRemoved = 0; 
      while(!queenPlaced && (row < BOARD_SIZE)) 
      { 
       //if square can be attacked 
       if (!isUnderAttack(row, column)) 
       { 
        setQueen(row, column); //consider next square in column 
        queenPlaced = placeQueens(column+1); 
        //if no queen is possible in next column, 
        if(!queenPlaced) 
        { 
         //backtrack: remover queen placed earlier 
         //and try next square in column 
         removeQueen(row, column); 
         queensRemoved ++ ; 
         System.out.println("Queen Removed: "+queensRemoved); 
         //++row; 
        } 
       } 
       ++row; 
      } 
      return queenPlaced; 
     } 

    } 



    //Sets a queen at square indicated by row and column 
    //Precondition: None 
    //Postcondition: Sets the square on the board in a given row and column to Queen. 
    private void setQueen(int row, int column) 
    { 
     board[row][column] = QUEEN; 
     displayBoard(); 
     System.out.printf("Queen PLACED in [%d][%d]\n", row, column); 
    } 



    //removes a queen at square indicated by row and column 
    //Precondition: None 
    //Postcondition: Sets the square on the board in a given row and column to EMPTY. 
    private void removeQueen(int row, int column) 
    { 

     board[row][column] = EMPTY; 
     displayBoard(); 
     System.out.printf("Queen REMOVED from [%d][%d]\n", row, column); 

    } 


    //Determines whether the square on the board at a given row and column is 
    //under attack by any queens in the columns 1 through column-1. 
    //Precondition: Each column between 1 and column-1 has a queen paced in a square at 
    //a specific row. None of these queens can be attacked by any other queen. 
    //Postcondition: If the designated square is under attack, returns true: otherwise return false. 
    private boolean isUnderAttack(int row, int column) 
    { 
     for (int y = 0; y < BOARD_SIZE; y++) 
     { 
      int x1 = row - column + y; 
      int x2 = row + column - y; 
      if (board[row][y] == QUEEN) //possible horizontal attack 
       return true; 
      if (0 <= x1 && x1 < BOARD_SIZE && board[x1][y] == QUEEN) //diagonal NW 
       return true; 
      if (0 <= x2 && x2 < BOARD_SIZE && board[x2][y] == QUEEN) //diagonal SW 
       return true; 
     } 

     return false; 
    } 





    private int index(int number) 
    { 
     //Returns the array index that corresponds to a row or column number. 
     //Precondition: 1 <= number <= BOARD_SIZE. 
     //Postcondition: Returns adjusted index value 

     return number -1 ; 
    } 



    //main to test program 
    public static void main(String[] args) 
    { 
     Queens Q = new Queens(); 
     if(Q.placeQueens(0)) 
     { 
      //Q.displayBoard(); 
     } 
     else 
     { 
      System.out.println("Not Possible"); 
     } 
    } 


} 

Answer 1

您需要使用計數器的靜態變量，以便在遞歸調用時更新相同的變量。

Answer 2

首先計數器必須是類的成員，而不是局部變量。其次，您可能希望在方法的頂部執行此操作，而不是在循環內執行操作。在循環中可能是什麼導致你的「奇怪的數字」