java - 使用递归求解 Hadamard 矩阵

Question

我正在尝试构建类似于 Hadamard matrix 的东西递归地，我需要一些帮助。我在网上没有找到任何递归执行此操作的解决方案。

如果有人知道某件事或知道解决方案，并且可以友善地将其发布在这里，这对我来说将非常有帮助。

谢谢!

编辑:这是一个非递归代码:

public class Hadamard
{
    public static void main(String[] args)
    {
    int N = Integer.parseInt(args[0]);
    boolean[][] H = new boolean[N][N];
    H[0][0] = true;
    for(int n = 1; n < N; n += n)
        {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
            {
                H[i+n][j] = H[i][j];
                H[i][j+n] = H[i][j];
                H[i+n][j+n] = !H[i][j];
            }
        }
    for(int i = 0; i < N; i++)
        {
        for(int j = 0; j < N; j++)
            {
            if(H[i][j]) System.out.print("* ");
            else        System.out.print(". ");
            }
        System.out.println();
        }
    }

}

来自:https://gist.github.com/guitarkitten/3937264

Answer 1

好吧，如果有人愿意解决这个问题并试图找到解决方案，我找到了一个非常干净且很好的解决方案。这个想法是调用四次递归调用，矩阵的每四分之一调用一次(每个 Hadamard 矩阵分为四个单元，左上角为 1，右上角为 1，左下角为 1，右下角为 - 1)。因此前三个调用填充正 1，第四个调用填充 (-1)*sign。

public static void fillHadamard (int mat[][])
{
    fillHadamard(mat, 0,0,mat.length, 1); //overloading, assuming mat.length is pow of 2 
}
private static void fillHadamard (int [][] mat, int top, int left, int size, int sign)
{
    if (size == 1)
        mat[top][left] = sign;
    else
    {
       fillHadamard (mat, top, left, size/2, sign);
       fillHadamard (mat, top+size/2, left, size/2, sign);
       fillHadamard (mat, top, left+size/2, size/2, sign);
       fillHadamard (mat, top+size/2, left+size/2, size/2, (-1)*sign);
    }
}

看看这个与非递归方法相比是多么干净整洁。