0

我陷入以下问题：

对于给定的指数 N、2x2 矩阵 A 和极限 L，递归计算矩阵 S：

S = I + A + A^2 + A^3 + ... + A^N

其中 I 是单位矩阵。

如果矩阵 S 的任何元素大于或等于 L。递减 L 直到它小于 L。

我的算法如下：

// Pre-condition: 
// Parameters:
// An integer indicating an exponent
// A 2d 2x2 integer array must exist as an instance attribute
// Post-condition: The matrix resulting from the sum of multiplied matrices 
// i.e. A^2 + A^1 + I
public int[][] computeMatrixSum(int exp)
{
    if(exp == 0)
    {
        return new int[][]
        {
            new int[]{ 1,0 },
            new int[]{ 0,1 }
        };
    }
    else
    {
        int[][] matrixB = new int[matrix.length][matrix[0].length];
        int[][] matrixC = new int[matrix.length][matrix[0].length];

        matrixB = matrix;

        for(int expC = exp; expC > 1; expC--)
        {
            // Multiply the matrix
            for(int i = 0; i < matrix.length; i++)
            {
                for(int k = 0; k < matrixB[0].length; k++)
                {
                    for(int j = 0; j < matrix[0].length; j++)
                    {
                        matrixC[i][k] += matrix[i][j] * matrixB[j][k];
                    }
                }
            }
            matrixB = matrixC;
            matrixC = new int[matrix.length][matrix[0].length];
        }

        // Recursively calculate the sum of the other matrix products
        int[][] tmpSum = computeMatrixSum(exp-1);

        int[][] matrixSum = new int[matrixB.length][matrixB[0].length];

        for(int row = 0; row < matrixB.length; row++)
        {
            for(int col = 0; col < matrixB[0].length; col++)
            {
                matrixSum[row][col] = matrixB[row][col] + tmpSum[row][col];
            }
        }

        return matrixSum;
    }
}

// Pre-condition:
// Parameters: 
// An integer indicating the exponent to apply on the matrix
// An integer indicating the limit of the elements of the 2d matrix sum
// An 2d 2x2 integer array must exist as an instance attribute
// Post-condition: The matrix resulting from the sum of multiplied matrices
// that has elements that are not greater than the given limit
// i.e. A^2 + A^1 + I
public int[][] solve(int exp,int limit)
{
        int[][] matrixSum = computeMatrixSum(exp);

        for(int row = 0; row < matrixSum.length; row++)
        {
            for(int col = 0; col < matrixSum.length; col++)
            {
                while(matrixSum[row][col] >= limit)
                    matrixSum[row][col] -= limit;
            }
        }

        return matrixSum;
}

我的算法有效。但是对于较大的 N 值来说太慢了。这是因为当我将所有指数相乘时，我会不断重新计算所有指数的结果。

我不知道有任何其他算法在解决这个问题方面更有效。

有人可以建议吗？

谢谢。

4

2 回答 2

1

如果A-I是可逆的，那么您可以找到S与几何级数完全相同的结果，只需记住您必须乘以倒数而不是除以：

S = I + A + A^2 + A^3 + ... + A^N
AS = A + A^2 + A^3 + ... + A^N + A^{N+1}
AS-S = A^{N+1}-I
(A-I)S = A^{N+1}-I
S = (A-I)^{-1} (A^{N+1}-I)

如果N真的很大，那么您将需要通过平方来求幂。递减 byL很容易，尽管您可能想要使用模数运算符。

如果A-I是单数，这种方法就行不通了，我能想到的最好的方法是使用乔丹范式（如果你愿意，A它也可以在第一种情况下工作）。

于 2013-10-29T15:32:22.377 回答
1

您可以应用霍纳的方法将“单项式形式转换为计算有效的形式”，正如此处和此处的多项式示例所建议的那样。您可以利用JScience该类Matrix来简化编码。

于 2013-10-29T03:47:20.690 回答