สมมติว่าเรามีอาร์เรย์ของตัวเลข เราต้องหาตัวเลข B ซึ่งเป็นตัวหารทั้งหมด ยกเว้นองค์ประกอบเดียวในอาร์เรย์ที่กำหนด เราต้องจำไว้ว่า GCD ขององค์ประกอบทั้งหมดไม่ใช่ 1
ดังนั้น หากอินพุตเป็นเหมือน {8, 16, 4, 24} ผลลัพธ์จะเป็น 8 เนื่องจากนี่คือตัวหารของทั้งหมด ยกเว้น 4
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของอาร์เรย์
- ถ้า n เหมือนกับ 1 แล้ว
- return(array[0] + 1)
- prefix :=อาร์เรย์ขนาด n และเติม 0
- suffix :=อาร์เรย์ขนาด n และเติม 0
- prefix[0] :=array[0]
- สำหรับฉันในช่วง 1 ถึง n ทำ
- คำนำหน้า[i] :=gcd ของ (อาร์เรย์[i] และคำนำหน้า[i - 1])
- คำต่อท้าย[n - 1] :=array[n - 1]
- สำหรับ i ในช่วง n - 2 ถึง -1, ลดลง 1, ทำ
- ส่วนต่อท้าย[i] :=gcd ของ (ส่วนต่อท้าย[i + 1] และอาร์เรย์[i])
- สำหรับฉันในช่วง 0 ถึง n + 1 ทำ
- cur :=0
- ถ้าฉันเหมือนกับ 0 แล้ว
- cur :=suffix[i + 1]
- มิฉะนั้น เมื่อ i เหมือนกับ n - 1 แล้ว
- cur :=prefix[i - 1]
- มิฉะนั้น
- cur :=gcd ของ (คำนำหน้า[i - 1] และส่วนต่อท้าย[i + 1])
- ถ้า array[i] mod cur ไม่เหมือนกับ 0 แล้ว
- ผลตอบแทน
- คืน 0
โค้ดตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
from math import gcd def getDivisor(array): n = len(array) if (n == 1): return (array[0] + 1) prefix = [0] * n suffix = [0] * n prefix[0] = array[0] for i in range(1, n): prefix[i] = gcd(array[i], prefix[i - 1]) suffix[n - 1] = array[n - 1] for i in range(n - 2, -1, -1): suffix[i] = gcd(suffix[i + 1], array[i]) for i in range(0, n + 1): cur = 0 if (i == 0): cur = suffix[i + 1] elif (i == n - 1): cur = prefix[i - 1] else: cur = gcd(prefix[i - 1], suffix[i + 1]) if (array[i] % cur != 0): return cur return 0; array = [8, 16, 4, 24] print(getDivisor(array))
อินพุต
[8, 16, 4, 24]
ผลลัพธ์
8
