โปรแกรมหาจำนวนองค์ประกอบที่ต่อเนื่องกันในเมทริกซ์ที่มี gcd มากกว่า 1 ใน Python

สมมติว่าเราได้รับเมทริกซ์ที่มี n แถวและ m คอลัมน์ เราต้องหาจำนวนองค์ประกอบที่ต่อเนื่องกันมากที่สุดในเมทริกซ์โดยที่ gcd ขององค์ประกอบมากกว่า 1 องค์ประกอบที่ต่อเนื่องกันสามารถวางในแนวนอนหรือแนวตั้งในเมทริกซ์

ดังนั้นหากอินพุตเป็นแบบ

และ m =4, n =3; แล้วผลลัพธ์จะเป็น 3

คอลัมน์ที่สี่ของเมทริกซ์ที่กำหนดคือ 12, 6, 10 gcd ขององค์ประกอบของคอลัมน์นี้คือ 2 เนื่องจากมีสามองค์ประกอบ คำตอบคือ 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• mat :=รายการมิติข้อมูล 3 มิติใหม่ ม. x น x น.
• res :=0
  • สำหรับ i ในช่วง 0 ถึง n ให้ทำ
    • สำหรับ j ในช่วง i ถึง n ทำ
      • gcd_temp :=0
      • x :=0
      • สำหรับ k ในช่วง 0 ถึง m ให้ทำ
        • ถ้าฉันเหมือนกับ 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 :=สูงสุดของความละเอียด x
          • ถ้า mat[i, j, k]> 1 แล้ว
            • gcd_temp :=mat[i, j, k]
            • x :=j - i + 1
  • res :=สูงสุดของความละเอียด x
• ผลตอบแทน

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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