home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรมหาค่าสูงสุดของนิพจน์จากชุดตัวเลขที่กำหนดใน Python

สมมติว่าเรามีอาร์เรย์สองตัว nums1 และ nums2 ขนาดเท่ากัน N พิจารณาชุด S ที่มีสมาชิก 1 ถึง N เราต้องหาค่าสูงสุดของนิพจน์:

(nums1[i1] + nums1[i2] + ... + nums1[ik])2 + (nums2[i1] + nums2[i2] + ... + nums2[ik])2

โดยที่ {i1, i2, ..., ik} เป็นสับเซตไม่ว่างของ S

ตัวอย่าง: nums1 = [-1, 6], nums2 = [5, 4] ผลลัพธ์คือ 106 เพราะ:

  • (-1)2 + 52 = 26
  • 62 + 42 = 50
  • (-1+6)2 + (5+4)2 = 106 ← สูงสุด

ขั้นตอนการแก้ปัญหา

  1. สร้างลิสต์คู่ vs = [(nums1[i], nums2[i]) for i in range(N)]
  2. เรียง vs ตามมุม atan2(v[1], v[0]) (มุมเชิงขั้ว)
  3. วนลูปแต่ละจุดเริ่มต้น i ลองขยายเซตทั้งทิศทางตามเข็มนาฬิกาและทวนเข็มนาฬิกา
  4. คำนวณผลรวมเวกเตอร์และเก็บค่ากวาดรูปทรง (magnitude squared) สูงสุด

ตัวอย่างโค้ด

from math import atan2

def solve(nums1, nums2):
    vs = list(zip(nums1, nums2))
    vs.sort(key=lambda v: atan2(v[1], v[0]))
    best = 0
    n = len(vs)
    for i in range(n):
        u = vs[i]
        l = u[0]*u[0] + u[1]*u[1]
        # ทิศทางตามเข็มนาฬิกา
        for v in (vs + vs)[i+1 : i+n]:
            t1 = (u[0]+v[0], u[1]+v[1])
            t2 = t1[0]*t1[0] + t1[1]*t1[1]
            if t2 >= l:
                u = t1
                l = t2
        if l > best:
            best = l
        # ทิศทางทวนเข็มนาฬิกา
        u = vs[i]
        l = u[0]*u[0] + u[1]*u[1]
        for v in reversed((vs + vs)[i+1 : i+n]):
            t1 = (u[0]+v[0], u[1]+v[1])
            t2 = t1[0]*t1[0] + t1[1]*t1[1]
            if t2 >= l:
                u = t1
                l = t2
        if l > best:
            best = l
    return best

nums1 = [-1, 6]
nums2 = [5, -4]
print(solve(nums1, nums2))  # Output: 52

อินพุต

[-1, 6], [5, -4]

เอาต์พุต

52