Python程式：查詢矩陣中最大連續元素個數（其最大公約數大於1）

假設我們得到一個包含n行m列的矩陣。我們需要找到矩陣中最大數量的連續元素，這些元素的最大公約數大於1。這些連續元素可以在矩陣中水平或垂直排列。

例如，輸入：

37912
5946
78510

如果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]]

輸出

3

更新於：2021年10月20日

173 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告