0

我需要这个练习的帮助：
给出在输入中接收整数 n 并打印所有可能的矩阵 nxn 的伪代码，其中 a 的数量大于或等于 b 的数量，例如 n=2：（顺序不重要）输出：
aa aa aa ab ab ba ba
ab ba aa aa ba aa ab
算法的复杂度为 O($n^2*S(n)$)。其中 S(n) 是应打印的矩阵数。

现在我对回溯的技术算法不是很了解，因为我正在研究它......所以请如果有人可以帮助我进行练习和回溯......否则我永远不会通过这次考试。感谢你们 ;）

exercise(char[][] M,int i,int j,int[] arrRB,int[] arrCB, int n , int nelem )
{
    if(nelem == n*n)
    {
        for (int r=0 ; r<n ; r++)
        {
            for(int c=0 ; c<n ;c++)
                System.out.print(M[r][c]);
            System.out.print("\n");
        }
        System.out.print("\n");
    }
    else
    {

        if(i<n && j<n)
        {
            int r=i,c=j;
            if (arrRB[i] <= n-(i+1) && arrCB[j] <= n-(j+1))
            {
                M[i][j] = 'b';
                arrRB[i]++;
                arrCB[j]++;
                exercise(M,i,j+1,arrRB ,arrCB ,n,nelem+1); 
                exercise(M,i+1,j,arrRB ,arrCB ,n,nelem+1 ); 
                arrRB[r]--;
                arrCB[c]--;
            }
            M[r][c] = 'a';
            exercise(M,r+1,c,arrRB ,arrCB ,n, nelem+1);
            exercise(M,r,c+1,arrRB ,arrCB ,n,nelem+1 ); 
        }
    }
}
}
4

1 回答 1

0

它看起来像这样（它是一个伪代码）：

// Generates all matrices
void generate(char[][] matrix, int i, int j, int[] cntBRow, int[] cntBColumn) 
    if (i == n) // if the matrix is filled completely
        print(matrix) // just prints it
    else
        // Finds the next empty cell
        int nextI = i
        int nextJ = j + 1
        if (nextJ == n)
            nextI = i + 1
            nextJ = 0
        matrix[i][j] = 'a' // it is always possible to add 'a'
        generate(matrix, nextI, nextJ, cntBRow, cntBColumn)
        if ((cntBRow[i] + 1) * 2 <= matrix.length 
                && (cntBColumn[j] + 1) * 2 <= matrix.length) // if it is still possible to add 'b'
            cntBRow[i]++
            cntBColumn[j]++
            matrix[i][j] = 'b' // puts 'b' and continues generation
            generate(matrix, nextI, nextJ, cntBRow, cntBColumn)

 // Creates a new matrix and starts generation
 char[][] matrix = new char[n][n]
 generate(matrix, 0, 0, new int[n], new int[n])

这个想法是固定在递归填充矩阵时遍历单元格的顺序（在上面的代码中，单元格按一对（行号，列号）排序）。

于 2014-12-28T23:05:00.980 回答