Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm giá trị lớn nhất có thể có của một biểu thức bằng cách sử dụng tập hợp số nhất định trong Python

Giả sử chúng ta có hai mảng gọi là nums1 và nums2, chúng có cùng số phần tử N. Bây giờ hãy xem xét một tập S có N phần tử từ 1 đến N. Chúng ta phải tìm giá trị của (nums1 [i1] + nums1 [i2] +. .. nums1 [ik]) ^ 2 + (nums2 [i1] + nums2 [i2] + ... nums2 [ik]) ^ 2 trong đó {i1, i2, ... ik} là tập con không rỗng của tập S .

Vì vậy, nếu đầu vào giống như nums1 =[-1, 6] nums2 =[5, 4], thì đầu ra sẽ là 106 vì

  • (-1) ^ 2 + (5) ^ 2 =26
  • (6) ^ 2 + (4) ^ 2 =50
  • (-1 + 6) ^ 2 + (5 + 4) ^ 2 =106

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • vs:=danh sách các cặp (nums1 [i], nums2 [i]) cho mỗi i trong phạm vi 0 đến kích thước của nums1 - 1
  • vs:=sắp xếp so với tan-nghịch đảo của v [1] / v [0] cho mỗi v trong vs
  • tốt nhất:=0
  • đối với tôi trong phạm vi từ 0 đến kích thước vs - 1, thực hiện
    • u:=so với [i]
    • l:=u [0] * u [0] + u [1] * u [1]
    • đối với mỗi v trong danh sách nối với vs và vs lại từ chỉ mục i + 1 đến (i + kích thước của vs - 1), hãy thực hiện
      • t1:=(u [0] + v [0], u [1] + v [1])
      • t2:=t1 [0] * t1 [0] + t1 [1] * t1 [1]
      • nếu t2> =l, thì
        • u:=t1
        • l:=t2
    • nếu l> tốt nhất, thì
      • tốt nhất:=l
    • u:=so với [i]
    • l:=u [0] * u [0] + u [1] * u [1]
    • đối với mỗi v ngược lại danh sách kết hợp của vs và vs lại từ chỉ mục i + 1 đến i + kích thước của vs -1], thực hiện
      • t1:=(u [0] + v [0], u [1] + v [1])
      • t2:=t1 [0] * t1 [0] + t1 [1] * t1 [1]
      • nếu t2> =l, thì
        • u:=t1
        • l:=t2
    • nếu l> tốt nhất thì
  • trở lại tốt nhất

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

from math import atan2
def solve(nums1, nums2):
   vs = zip(nums1,nums2)
   vs = sorted(vs, key=lambda v: atan2(v[1],v[0]))

   best = 0
   for i in range(len(vs)):
      u = vs[i]
      l = u[0]*u[0]+u[1]*u[1]
      for v in (vs+vs)[i+1:(i+len(vs))]:
         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+len(vs))]):
         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))

Đầu vào 

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

Đầu ra 

52