โปรแกรมค้นหาขนาดสูงสุดของลำดับของอาร์เรย์ที่กำหนดโดยที่ทุกคู่ดีใน Python

สมมติว่าเรามีลำดับตัวเลขขนาด n เราต้องหาขนาดสูงสุดของลำดับรองของ nums ที่ทุกคู่ (p, q) เป็นคู่ที่ดี? กล่าวได้ว่า pait เป็นคู่ที่ดีก็ต่อเมื่อมีเงื่อนไขเหล่านี้อย่างน้อยหนึ่งข้อ:1. ความเท่าเทียมกันของจำนวนตัวหารเฉพาะเฉพาะของ p เท่ากับของ b ตัวอย่างเช่น ค่า 18 มีตัวหารเฉพาะที่แตกต่างกันสองตัว:2 และ 3 2. ความเท่าเทียมกันของผลรวมของตัวหารบวกทั้งหมดของ p จะเหมือนกับ q

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[2,3,6,8] ผลลัพธ์จะเป็น 3

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

• n :=ขนาดของ nums
• กำหนดรายการว่างสามรายการ cnt, รวม, ผลลัพธ์
• สำหรับแต่ละ i ใน nums ทำ
  • นับ :=0, tot :=0
  • prime :=รายการใหม่
  • สำหรับแต่ละ j ใน nums ทำ
    • ถ้า (j mod k สำหรับ k ทั้งหมดในช่วง 2 ถึง j) เป็นจริง ดังนั้น
      • แทรก j ที่ส่วนท้ายของไพรม์
  • สำหรับแต่ละ j ในไพรม์ ให้ทำ
    • ถ้าฉัน mod j เป็น 0 แล้ว
      • นับ :=นับ + 1
  • ถ้านับเป็นคู่
    • ใส่ 'odd' ต่อท้าย cnt
  • มิฉะนั้น
    • แทรก 'คู่' ที่ส่วนท้ายของ cnt
  • สำหรับ j ในช่วง 1 ถึง i ทำ
    • ถ้าฉัน mod j เหมือนกับ 0 แล้ว
      • tot :=tot + j
  • ถ้า tot เป็นเลขคี่
    • แทรก 'คี่' ที่ส่วนท้ายของผลรวม
  • มิฉะนั้น
    • แทรก 'คู่' ที่ส่วนท้ายของผลรวม
• สำหรับฉันในช่วง 0 ถึง n-2 ทำ
  • สำหรับ j ในช่วง i+1 ถึง n - 1 ทำ
    • ถ้า cnt[i] เหมือนกับ cnt[j] หรือ total[i] เหมือนกับ total[j] แล้ว
      • ใส่ nums[i] ที่ส่วนท้ายของผลลัพธ์
      • ถ้า j เหมือนกับ n-2 แล้ว
        • ใส่ nums[j] ที่ส่วนท้ายของผลลัพธ์
• ผลลัพธ์ :=รายการใหม่จากชุดใหม่จากผลลัพธ์
• ขนาดผลตอบแทนของผลลัพธ์

ตัวอย่าง

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

def solve(nums):
   n = len(nums)
   cnt = []
   total = []
   result = []
   for i in nums:
      count = 0
      tot = 0

      prime = []
      for j in nums:
         if all(j % k for k in range(2, j)) == True:
            prime.append(j)

      for j in prime:
         if i % j == 0:
            count += 1
      if count % 2:
         cnt.append('odd')
      else:
         cnt.append('even')

      for j in range(1,i+1):
         if i % j == 0:
            tot += j

      if tot % 2:
         total.append('odd')
      else:
         total.append('even')

   for i in range(n-1):
      for j in range(i+1, n):

         if cnt[i] == cnt[j] or total[i] == total[j]:
            result.append(nums[i])

            if j == n-1:
               result.append(nums[j])

   result = list(set(result))
   return len(result)

nums = [2,3,6,8]
print(solve(nums))

อินพุต

15, 3, 8

ผลลัพธ์

3