Решение для матрицы Адамара с использованием рекурсии

Question

Я пытаюсь создать что-то похожее на Hadamard matrix рекурсивно, и мне нужна помощь. Я не нашел в Интернете никаких решений, которые рекурсивно решают.

Если кто-то знает что-то или знает решение и может быть добрым и опубликовать его здесь, это будет очень полезно для меня.

Спасибо!

Edit: Это нерекурсивна код для этого:

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

Ну, если кто-то будет решать этот вопрос пытается найти решение, я нашел довольно чистый и хороший для этого. Идея состоит в том, чтобы называть четыре рекурсивных вызова, по одному для каждой четверти матрицы (каждая матрица Адамара делится на четыре ячейки, верхний левый - 1, верхний правый - 1, нижний левый - 1, а нижний правый - -1). Таким образом, первые три вызова заполняют положительные 1, а четвертая заполняется знаком (-1) *.

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

Посмотрите, как чисто и аккуратно это объединение не-рекурсивному методу.

Answer 2

Вот реализация на основе рекурсивного определения для матриц Адамара, размерность которых степень 2.

H(0) = [1] 

     | H(k-1)  H(k-1) | 
H(k) = |     | 
     | H(k-1) -H(k-1) | 

Я замещенный true для 1 и false для -1, чтобы быть последовательным с твоим. Также обратите внимание, что я использую индекс 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(); 
    } 
    } 
} 

Запуск этого производит:

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