使用递归解决Hadamard矩阵(Solution for Hadamard matrix using recursion)

我试图以递归方式构建类似于Hadamard矩阵的东西，我需要一些帮助。我没有在网上找到任何递归执行的解决方案。

如果有人知道某些事情或知道解决方案并且可以善待并在此发布，那对我来说将非常有帮助。

谢谢！

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

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

I'm trying to build something similar to a Hadamard matrix recursively and I need some assistance. I didn't find in the web any solution that do it recursively.

If someone know something or know the solution and can be kind and post it here, It will be very helpful for me.

Thanks!

Edit: This is a non-recursive code for this:

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(); } } }

From: https://gist.github.com/guitarkitten/3937264

最满意答案

这是一个基于Hadamard矩阵的递归定义的实现，其维数是2的幂。

H(0) = [1] | H(k-1) H(k-1) | H(k) = | | | H(k-1) -H(k-1) |

我将1替换为false ，将-1替换为false以与您的一致。另请注意，我使用的是Hadamard索引号k而不是维N

public class Hadamard { public static boolean[][] hadamard(int k) { if (k > 0) { boolean[][] a = hadamard(k - 1); int dim = a.length; boolean[][] h = new boolean[2*dim][2*dim]; for(int i = 0; i < dim; ++i) { for(int j = 0; j < dim; ++j) { h[i][j] = a[i][j]; h[i][j + dim] = a[i][j]; h[i + dim][j] = a[i][j]; h[i + dim][j + dim] = !a[i][j]; } } return h; } else { return new boolean[][]{{true}}; } } public static void main(String[] args) { boolean[][] H = hadamard(4); for(int i = 0; i < H.length; i++) { for(int j = 0; j < H[i].length; j++) { if(H[i][j]) System.out.print("* "); else System.out.print(". "); } System.out.println(); } } }

运行它会产生：

* * * * * * * * * * * * * * * * * . * . * . * . * . * . * . * . * * . . * * . . * * . . * * . . * . . * * . . * * . . * * . . * * * * * . . . . * * * * . . . . * . * . . * . * * . * . . * . * * * . . . . * * * * . . . . * * * . . * . * * . * . . * . * * . * * * * * * * * . . . . . . . . * . * . * . * . . * . * . * . * * * . . * * . . . . * * . . * * * . . * * . . * . * * . . * * . * * * * . . . . . . . . * * * * * . * . . * . * . * . * * . * . * * . . . . * * . . * * * * . . * . . * . * * . . * * . * . . *

Well, if anyone will tackle this question trying to find a solution, I found a pretty clean and good one for this. The idea is to call four recursive calls, one for each quarter of the matrix (every Hadamard matrix is divided to four cells, top-left is 1, top-right is 1, bottom-left is 1, and bottom-right is -1). So the first three calls fills the positive 1's, and the fourth fill is with (-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); } }

Look how clean and neat this compering to none-recursive method.

更多推荐