在 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 的最大值
- 对于 i 在 0 到 n 范围内,执行以下操作
- 返回 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