java - 计算函数的递归调用次数

Question

对于以下代码，我希望能够计算对 placeQueens() 的递归调用次数和对 isUn​​derAttack() 的调用次数。我尝试在 placeQueens() 的第一行添加 int counter = 0 并在 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

您需要使用静态变量作为计数器，以便在递归调用时更新相同的变量。