Python程序：查找矩阵中最大连续元素个数（其最大公约数大于1）

假设我们得到一个包含n行m列的矩阵。我们需要找到矩阵中最大数量的连续元素，这些元素的最大公约数大于1。这些连续元素可以在矩阵中水平或垂直排列。

例如，输入：

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

如果m = 4，n = 3；则输出为3。

给定矩阵的第四列是12, 6, 10。该列元素的最大公约数是2。由于共有三个元素，答案是3。

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

mat := 一个新的维度为m x n x n的3维列表
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_temp = gcd_temp 和 mat[i, j, k] 的最大公约数
      - 如果 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]]

输出

Arnab Chakraborty

更新于：2021年10月20日

173 次浏览

开启你的职业生涯

完成课程获得认证

开始学习