ค้นหาตัวประกอบของ N สี่ตัวด้วยผลคูณสูงสุดและผลรวมเท่ากับ N - Set-2 ใน Python

สมมติว่าเรามีตัวเลข N; เราต้องหาตัวประกอบของ N และส่งกลับเฉพาะผลคูณของปัจจัยสี่ตัวของ N เท่านั้น −

• ผลรวมของปัจจัยทั้งสี่มีค่าเท่ากับ N.

• ผลคูณของปัจจัยทั้งสี่มีค่าสูงสุด

ปัจจัยทั้งสี่สามารถมีค่าเท่ากันเพื่อเพิ่มผลผลิตให้สูงสุด

ดังนั้นหากอินพุตเป็น N =60 เอาต์พุตจะเป็น 50625 เนื่องจากปัจจัยทั้งหมดคือ → 1 2 3 4 5 6 10 12 15 20 30 60 และผลิตภัณฑ์ของมันคือ 50625 เนื่องจากเรา 15 ถูกเลือกสี่ครั้ง ทำให้สินค้ามีขนาดใหญ่ที่สุด

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

• my_map :=แผนที่ใหม่

• v :=รายการใหม่ v1 :=รายการใหม่

• สำหรับฉันอยู่ในช่วง 1 ถึงเพดานของรากที่สองของ (n) + 1 ทำ

  • ถ้า n mod i เหมือนกับ 0 แล้ว

    • ใส่ i ต่อท้าย v

    • ถ้าฉันไม่เหมือนส่วนจำนวนเต็มของ (n / i) และฉันไม่เหมือน 1 แล้ว

      • แทรกส่วนจำนวนเต็มของ (n / i) ที่ส่วนท้ายของ v

• s :=ขนาดของวี

• สูงสุด :=-1

• map1 :=อาร์เรย์ขนาด (n + 5) เติมด้วย 0

• สำหรับฉันอยู่ในช่วง 0 ถึง s ทำ

  • สำหรับ j ในช่วง i ถึง s ทำ

    • ถ้า v[i] + v[j]

      • ใส่ v[i] + v[j] ต่อท้าย v1

      • map1[v[i] + v[j]] :=[v[i], v[j]]

      • my_map[v[i] + v[j]] :=1

• s :=ขนาดของ v1

• สำหรับฉันอยู่ในช่วง 0 ถึง s ทำ

  • องค์ประกอบ :=n - (v1[i])

  • ถ้าองค์ประกอบใน my_map แล้ว

    • a :=map1[v1[i], 0]

    • b :=map1[v1[i], 1]

    • c :=map1[n - v1[i], 0]

    • d :=map1[n - v1[i], 1]

    • สูงสุด :=สูงสุดของ a * b * c * d สูงสุด

• ถ้าค่าสูงสุดเท่ากับ -1 แล้ว

  • แสดง "เป็นไปไม่ได้"

• มิฉะนั้น

  • แสดงผลสูงสุด

ตัวอย่าง

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

from math import sqrt, ceil, floor
def get_product(n):
   my_map = dict()
   v = []
   v1 = []
   for i in range(1,ceil(sqrt(n)) + 1):
   if (n % i == 0):
      v.append(i)
      if (i != (n // i) and i != 1):
         v.append(n // i)
   s = len(v)
   maximum = -1
   map1 = [0]*(n + 5)
   for i in range(s):
      for j in range(i, s):
         if (v[i] + v[j] < n):
            v1.append(v[i] + v[j])
            map1[v[i] + v[j]] =[v[i], v[j]]
            my_map[v[i] + v[j]] = 1
   s = len(v1)
   for i in range(s):
      element = n - (v1[i])
      if (element in my_map):
         a = map1[v1[i]][0]
         b = map1[v1[i]][1]
         c = map1[n - v1[i]][0]
         d = map1[n - v1[i]][1]
         maximum = max(a * b * c * d, maximum)
   if (maximum == -1):
      print("Not Possible")
   else :
      print("Maximum product", maximum)
n = 60
get_product(n)

อินพุต

60

ผลลัพธ์

Maximum product 50625