โปรแกรมค้นหาผลคูณสเกลาร์ของเวกเตอร์ที่สร้างขึ้นจากลำดับอนันต์ใน Python

สมมติว่าเราได้รับเลขจำนวนเต็มสามจำนวน c, m และ n เราต้องสร้างลำดับอนันต์ โดยที่ค่าแรกเป็น 0 ค่าที่สองคือ c และจากค่าที่สามเป็นต้นไป จะเท่ากับ ki =(ki-2 + ki-1) mod m เราต้องสร้างค่าทั้งหมดในชุดข้อมูลจนถึงรายการ k2n+1 ตอนนี้จากค่าของชุด; เราใช้ค่าที่ต่อเนื่องกันสองค่าในลำดับเป็นพิกัด x และ y ของเวกเตอร์สองมิติ และสร้างเวกเตอร์จำนวน n ตัว ข้อสังเกต เราใช้ค่าตามลำดับจากค่าที่สาม มีอีกชุดหนึ่ง S โดยที่แต่ละค่าเป็นผลคูณของสเกลาร์ของเวกเตอร์ i และเวกเตอร์ j โดยที่ 1 <=i, j <=n และ i !=j เราต้องหาจำนวนสารตกค้างต่าง ๆ ในชุด S ถ้าค่ามากก็ปรับเป็น m

ดังนั้นหากอินพุตเป็น 5, 6, 4 เอาต์พุตจะเป็น 3

ลำดับที่สร้างคือ [0, 5, 5, 4, 3, 1, 4, 5, 3, 2]

เวกเตอร์คือ:(5, 4), (3, 1), (4, 5), (3, 2).

จากผลคูณสเกลาร์ของเวกเตอร์ มีเพียงสามค่าเรซิดิว mod 6 ในชุด S

ผลลัพธ์ที่ได้คือ 3 mod 6 =3

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

• ถ้า n เหมือนกับ 1 แล้ว
  • คืน 0
• มิฉะนั้น
  • temp_arr:=รายการใหม่ของขนาด 2*n+2 เริ่มต้นด้วย 0s
  • temp_arr[0] :=0
  • temp_arr[1] :=c
  • arr2 :=รายการใหม่
  • สำหรับฉันในช่วง 2 ถึง 2 * n+2 ทำ
    • temp_arr[i] :=(temp_arr[i - 1] + temp_arr[i - 2]) mod ม
  • สำหรับ i ในช่วง 2 ถึง 2 * n-2, เพิ่มขึ้น 2, ทำ
    • อุณหภูมิ :=(temp_arr[i] * temp_arr[i + 2] + temp_arr[i + 1] * temp_arr[i + 3]) mod ม
    • ใส่อุณหภูมิที่ส่วนท้ายของ arr2
    • temp :=(temp_arr[i] * temp_arr[i+4] + temp_arr[i+1] * temp_arr[i+5]) mod m
    • ใส่อุณหภูมิที่ส่วนท้ายของ arr2
  • อุณหภูมิ :=(temp_arr[2 * n-2] * temp_arr[2 * n] + temp_arr[2 * n-1] * temp_arr[2 * n+1]) mod ม
  • ใส่อุณหภูมิที่ส่วนท้ายของ arr2
  • ลบรายการที่ซ้ำกันออกจาก arr2
  • ขนาดผลตอบแทนของ arr2

ตัวอย่าง

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

def solve(c, m, n):
   if (n == 1):
      return 0
   else:
      temp_arr=[0 for i in range(2 * n+2)]
      temp_arr[0] = 0
      temp_arr[1] = c
      arr2 = []
      for i in range(2, 2 * n+2):
         temp_arr[i] = (temp_arr[i - 1] + temp_arr[i - 2]) % m
      for i in range(2, 2 * n-2, 2):
         temp = (temp_arr[i] * temp_arr[i + 2] + temp_arr[i + 1] * temp_arr[i + 3]) % m
         arr2.append(temp)
         temp = (temp_arr[i] * temp_arr[i+4] + temp_arr[i+1] * temp_arr[i+5]) % m
         arr2.append(temp)
      temp = (temp_arr[2 * n-2] * temp_arr[2 * n] + temp_arr[2 * n- 1] * temp_arr[2 * n+1]) % m
      arr2.append(temp)
      arr2 = set(arr2)
      return len(arr2)

print(solve(5, 6, 4))

อินพุต

5, 6, 4

ผลลัพธ์

3