java - 生成一个 'special matrix'

Question

我正在尝试解决以下问题:

给定一个数字 n，生成一个大小为 2^n * 2^n 的矩阵，满足以下规则:

n = 1 
[ 1 2 ]
[ 3 4 ]

n = 2 
[ 1   2    5  6 ]
[ 3   4    7  8 ]
[ 9  10   13 14 ]
[ 11 12   15 16 ]

这是我的算法:

static void generare(int i , int j , int x , int y){
    if(x - i == 1 && y - j == 1)
        {
        mat[i][j] = counter++;
        mat[i][j+1] = counter++;
        mat[i+1][j] = counter++;
        mat[i+1][j+1] = counter++;
        }
    else{
        generare(i,j,x/2,y/2);
        generare(i,y/2+1,x/2,y);
        generare(x/2+1,j,x,y/2);
        generare(x/2+1,y/2+1,x,y);
    }
}

它适用于 n = 1,2，但当我尝试任何大于 2 的数字时，它会崩溃。我该如何修复我的递归函数？

Answer 1

首先，我认为您调用函数的方式不正确。对我来说，您发布的代码甚至不适用于 4X4 数组。我认为应该使用 (0, 0, 2^n, 2^n)

调用递归函数

无论如何，解决方案如下(我会解释):

private static int[][] mat;
private static int counter = 1;

public static void generare(int i, int j, int x, int y) {
    if (x - i <= 2 && y - j <= 2) {

        mat[i][j] = counter++;
        mat[i][j+1] = counter++;
        mat[i+1][j] = counter++;
        mat[i+1][j+1] = counter++;
    } else {
        generare(i, j, x/2+i/2, y/2+j/2);
        generare(i, j+(y-j)/2, x/2 +i/2, y);
        generare(i+(x-i)/2, j, x, y/2+j/2);
        generare(i+(x-i)/2, j+(y-j)/2, x, y);
    }
}

public static void main(String[] args) {
    int power=3;
    int n =(int) Math.pow(2, power);
    mat = new int[n][n];
    generare(0, 0, n, n);
    for(int i=0;i<n;i++) {
        for(int j=0; j<n; j++){
            System.out.print(mat[i][j] +" ");
        }
        System.out.println();
    }
}

我的解决方法是:

1. 递归函数应该在我们到达 2 x 2 数组时停止。
2. 如果数组大于 2 x 2 数组。我们应该用 4 个调用(就像你做的那样)调用函数，但用 4 个子数组。你错在哪里，只是计算本身。

它适用于 n=1,2，因为递归调用只发生了一次。一旦您的代码运行不止一次，计算就会不正确。我所做的是绘制一个 8 x 8 数组并尝试仅使用 i、j、x 和 y 来表示调用。希望这会有所帮助:)