โปรแกรมหาสัมประสิทธิ์สมการเชิงเส้นที่มีคำตอบเดียวในPython

สมมติว่าเรามีค่า n เราต้องหาจำนวนคู่ (a, b) [a

ดังนั้น หากอินพุตเป็น n =4 เอาต์พุตจะเป็น 2 เนื่องจากคู่ที่ถูกต้องคือ (1, 2) และ (1, 3)

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

• กำหนดฟังก์ชัน divisors_gen() นี่จะใช้เวลา n
• divs :=รายการของขนาด n+1 และแต่ละรายชื่อภายในถือ 1
• divs[0] :=รายการที่มีองค์ประกอบเดียว 0
• สำหรับฉันในช่วง 2 ถึง n ทำ
  • สำหรับ j ในช่วง 1 ถึงชั้นของ (n / i) + 1, do
    • แทรก i ที่ท้ายรายการที่ดัชนี [i * j]
• ส่งคืน div แต่กลับรายการภายในทั้งหมด
• จากวิธีหลัก ให้ทำดังต่อไปนี้ −
• ผลลัพธ์ :=0
• d_cache :=divisors_gen(n+1)
• สำหรับ a ในช่วง 1 ถึง n - 1 ทำ
  • ผม :=1
  • s :=ชุดใหม่
  • ในขณะที่ a*i
  • b :=n - a*i
  • สำหรับแต่ละ d ใน d_cache[b] ทำ
    • ถ้า d> a แล้ว
      • ถ้า d ไม่อยู่ใน s แล้ว
        • ผลลัพธ์ :=ผลลัพธ์ + 1
    • มิฉะนั้น
      • ออกมาจากวงจร
    • ใส่ d เข้าไปในชุด s
  • ผม :=ผม + 1

ตัวอย่าง

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

def divisors_gen(n):
   divs = [[1] for x in range(0, n + 1)]
   divs[0] = [0]
   for i in range(2, n + 1):
      for j in range(1, n // i + 1):
         divs[i * j].append(i)
   return [i[::-1] for i in divs]

def solve(n):
   result = 0
   d_cache = divisors_gen(n+1)

   for a in range(1, n):
      i = 1
      s = set([])
      while a*i < n:
         b = n - a*i
         for d in d_cache[b]:
            if d > a:
               if d not in s:
                  result += 1
            else:
               break
            s.add(d)
         i += 1
   return result

n = 4
print(solve(n))

อินพุต

4

ผลลัพธ์

2