在 Python 中寻找矩阵中 GCD 大于 1 的连续元素的数量

在 Python 中寻找矩阵中 GCD 大于 1 的连续元素的数量

假设我们有一个包含 n 行和 m 列的矩阵。我们需要找出矩阵中 GCD 大于 1 的连续元素的最大数量。连续的元素可以水平或垂直地存在于矩阵中。

例如,如果输入如下所示,其中 m=4,n=3,则输出将为 3。

3 7 9 12
5 9 4 6
7 8 5 10

给定矩阵的第四列为 12、6、10。该列元素的 GCD 为 2。由于有三个元素,答案为 3。

为了解决这个问题,我们将遵循以下步骤 –

  • mat := dimensions 为 m x n x n 的新 3D 列表
  • res := 0
    • 对于 i 在 0 到 n 范围内,执行以下操作
      • 对于 j 在 i 到 n 的范围内,执行以下操作
      • gcd_temp := 0
      • x := 0
      • 对于 k 在 0 到 m 范围内,执行以下操作
        • 如果 i 与 j 相同,则
        • mat[i, j, k] := input_list[i, k]
        • 否则,
        • mat[i, j, k] = 元素(mat[i, j-1, k], input_list[j, k]) 的 GCD
        • gcd_temp = 元素(gcd_temp, mat[i, j, k]) 的 GCD
        • 如果 gcd_temp > 1,则
        • x := x + j – i + 1
        • 否则,
        • res := res 和 x 的最大值
        • 如果 mat[i, j, k] > 1,则
          • gcd_temp := mat[i, j, k]
          • x := j – i + 1
    • res := res 和 x 的最大值
  • 返回 res

示例

以下是更好地理解此实现的实现 –

from math import gcd
def solve(n, m, input_list):
    mat = [[[0] *m] *n] *n
    res = 0
    for i in range(n):
        for j in range(i, n):
            gcd_temp = 0
            x = 0
            for k in range(m):
                if i == j:
                    mat[i][j][k] = input_list[i][k]
                else:
                    mat[i][j][k] = gcd(mat[i][j-1][k], input_list[j][k])
                gcd_temp = gcd(gcd_temp, mat[i][j][k])
                if gcd_temp > 1:
                    x += j - i + 1
                else:
                    res = max(res,x)
                    if mat[i][j][k] > 1:
                        gcd_temp = mat[i][j][k]
                        x = j - i + 1
            res = max(res,x)
    return res
print(solve(3, 4, [[3, 7, 9, 12], [5, 9, 4, 6], [7, 8, 5, 10]]))

输入

3, 4, [[3, 7, 9, 12], [5, 9, 4, 6], [7, 8, 5, 10]]

输出

3

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程