用逻辑填充int[2000][2000]时发生java StackOverflow错误

Question

我需要用一些逻辑填充int[2000][2000]矩阵

填充数组的我的代码：

// n: (1 to 2000)
for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        uniMatrix[i][j] = (((calc(i * j * i * j)) & 1) == 0) ? 0 : 1;
    }
}

这里：i * j * i * j是我对i*j平方的理解。 calc()是一种用于获取值的方法。然后，我检查calc()返回的值是偶数还是奇数。如果它是偶数，我将0存储在(i, j)上的矩阵中，否则我将1存储在其中

我的calc()函数如下所示：

private static int calc(int n){

    // value of n=calc(1 | 2 | 3) is known
    if(n < 4) return n;

    // if value is present in HashMap, return it (don't calculate again)
    if(map.containsKey(n)) {
        return map.get(n);
    }

    // calculate the answer
    int answer = 1 * calc(n-1) + 2 * calc(n-2) + 3 * calc(n-3);

    // store it in HashMap so that we don't have to recalculate it
    map.put(n, answer);

    return answer;
}

---

现在，如果n是13，它将创建一个[13x13]矩阵。但是，对于n=14，它在map.containsKey(n)处抛出一个StackOverflowError。我需要能够制作[2000x2000]矩阵

我知道问题可能是递归。但是，有办法解决这个问题吗？我可以用位集做些什么吗（我不知道怎么做）

我可以使用其他数据类型矩阵：String[][]或boolean[][]。我不能使用Java SDK/JDK之外的库

编辑：它不是“What is StackOverflower？”（什么是StackOverflower？）的副本，我知道这是什么，我知道它们为什么会发生。我需要帮助找到一种替代我的方法来防止这个错误

Answer 1

我们只对模2的结果感兴趣，所以所有的计算都可以模2进行。然后递归减少为（为计算模2编写计算）：

calc'(1) = 1
calc'(2) = 0
calc'(3) = 1
calc'(n) = (calc'(n-1) + calc'(n-3)) % 2

我们看到，下一个值只取决于固定距离内的两个前一个值，因为每个值的数字范围是有限的（只能是0或1），我们知道序列最终必须是周期的。一些实验表明，周期为7

因此，模2的值为（对于n>；=1）：

calc'(n) = 
     1 if n%7 = 1,
     0 if n%7 = 2,
     1 if n%7 = 3,
     0 if n%7 = 4,
     0 if n%7 = 5,
     1 if n%7 = 6,
     1 if n%7 = 0.

Answer 2

无法计算所需值范围的calc。在i = j = 216您会得到一个整数溢出（i * j * i * j的结果变为负数），因此calc的结果可能不正确。更糟糕的是，你的备忘录map的大小也会爆炸

好消息是你实际上不需要计算它。 看看这个表达：

uniMatrix[i][j] = (((calc(i * j * i * j)) & 1) == 0) ? 0 : 1;

您不需要计算值，只需要知道值是偶数还是奇数。你可以知道，用简单的数学。calc实现的核心是：

int answer = calc(n - 1) + 2 * calc(n - 2) + 3 * calc(n - 3);

我们知道前三个值是1，2，3。 事实上，知道它们是奇数、偶数、奇数就足够了。 之后的值可以基于简单的数学计算：

• 将任何数字乘以2将是偶数
• 将任何数字乘以3将保持原来的状态（如果是奇数，则为奇数，即使是偶数）
• 奇数加偶数就是偶数
• 将偶数添加到任何其他数字将具有其他数字的偶数性

现在，让我们看看由calc计算的前两个值，并验证决定该值是奇数还是偶数的逻辑：

• 0->；0:偶数（给定）
• 1->；1：奇数（给定）
• 2->；2：偶数（给定）
• 3->；3：奇数（给定）
• 4->；10:偶数，因为奇数+偶数+奇数就是偶数
• 5->；22:偶数，因为偶数+偶数+偶数就是偶数
• 6->；51:奇数，因为奇数+偶数+偶数是奇数
• 7->；125：奇数，因为偶数+偶数+奇数就是奇数
• 8->；293:奇数，因为偶数+偶数+奇数就是奇数
• 9->；696:偶数，因为奇数+偶数+奇数就是偶数
• 10->；1657:奇数，因为奇数+偶数+偶数就是奇数
• 11->；3928:偶数，因为奇数+偶数+奇数就是偶数
• 12->；9330:偶数，因为偶数+偶数+偶数就是偶数
• 13->；22157:奇数，因为奇数+偶数+偶数就是奇数
• 14->；52601:奇数，因为偶数+偶数+奇数就是奇数
• 15->；124905:奇数，因为偶数+偶数+奇数就是奇数
• 16->；296578:偶数，因为奇数+偶数+奇数就是偶数

如果您注意到，出现了重复模式：

even odd even even odd odd odd

只有0会破坏模式，在这种情况下，该值为0。 因此，您的实现可以这样重写，而不会有堆栈溢出的风险：

int[] pattern = {0, 1, 0, 0, 1, 1, 1};
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        long x = (long) i * j * i * j;
        if (x < 2) {
            uniMatrix[i][j] = (int) x;
        } else {
            uniMatrix[i][j] = pattern[(int)((x - 2) % pattern.length)];
        }
    }
}

对于0，由于它不遵循该模式，因此需要进行特殊处理。对于1，x-2为负。由于0和1的正确值是其本身，因此if（x<；2）分支是处理这些情况的简单方法