用 Python 编写程序找出矩阵中最大公约数大于 1 的连续元素的数量

假设我们得到一个包含 n 行和 m 列的矩阵。我们必须找出矩阵中最大数量的连续元素，其中元素的 gcd 大于 1。连续元素可以在矩阵中水平或垂直放置。

因此，如果输入如下

且 m = 4，n = 3；那么输出将是 3。

给定矩阵的第四列是 12、6、10。此列元素的 gcd 是 2。由于有三个元素，所以答案是 3。

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

• mat := 一个新的 3d 列表，尺寸为 m x n x n
• res := 0
  • 对于范围从 0 到 n 的 i，执行
    • 对于范围从 i 到 n 的 j，执行
      • gcd_temp := 0
      • x := 0
      • 对于范围从 0 到 m 的 k，执行
        • 如果 i 与 j 相同，则
          • mat[i, j, k] := input_list[i, k]
        • 否则，
          • mat[i, j, k] = 元素的 gcd(mat[i, j-1, k], input_list[j, k])
        • gcd_temp = 元素的 gcd (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]]

输出

3

相关文章

• Python 中元组列表到字典的转换
• Python - 从两个列表中配对，使得成对的元素不相同
• 使用 Python 和 SQLite 的 SQL
• 使用 pytrie 模块在 Python 中进行前缀匹配
• 创建和访问 Python 包
• 如何使用正则表达式和数据类型选择多个 DataFrame 列
• 如何在 Pandas 中查找和过滤重复行?
• 用 Python 编写程序以正确的顺序查找机场?
• 如何在 Python Pandas 中使用字典顺序切片选择数据子集?
• 用 Python 编写程序检查我们是否可以从给定的字符串字符中创建 k 个回文?

有用资源

• python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/