Chương trình tìm ra số phần tử liên tiếp trong ma trận có gcd lớn hơn 1 trong Python

Giả sử chúng ta được đưa ra một ma trận chứa n hàng và m cột. Chúng ta phải tìm ra số phần tử liên tiếp lớn nhất trong ma trận mà gcd của các phần tử lớn hơn 1. Các phần tử liên tiếp có thể nằm ngang hoặc dọc trong ma trận.

Vì vậy, nếu đầu vào giống như

và m =4, n =3; thì đầu ra sẽ là 3.

Cột thứ tư của ma trận đã cho là 12, 6, 10. Gcd của các phần tử của cột này là 2. Vì có ba phần tử nên câu trả lời là 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• mat:=danh sách 3d mới về kích thước m x ​​n x n
• res:=0
  • đối với tôi trong phạm vi từ 0 đến n, thực hiện
    • đối với j trong phạm vi từ i đến n, thực hiện
      • gcd_temp:=0
      • x:=0
      • đối với k trong phạm vi từ 0 đến m, thực hiện
        • nếu tôi giống với j, thì
          • mat [i, j, k]:=input_list [i, k]
        • nếu không,
          • mat [i, j, k] =gcd của các phần tử (mat [i, j-1, k], input_list [j, k])
        • gcd_temp =gcd của các phần tử (gcd_temp, mat [i, j, k])
        • nếu gcd_temp> 1, thì
          • x:=x + j - i + 1
        • nếu không,
          • res:=tối đa res, x
          • nếu mat [i, j, k]> 1, thì
            • gcd_temp:=mat [i, j, k]
            • x:=j - i + 1
  • res:=tối đa res, x
• trả lại res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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]]))

Đầu vào

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

Đầu ra

3