โปรแกรม Python หาจำนวนครั้งในการแพ็คแท่งโลหะหลายๆอันในคอนเทนเนอร์

สมมติว่าเราได้รับมอบหมายให้ขนส่งแท่งโลหะหลายแท่งที่มีขนาดต่างกัน แต่ตู้คอนเทนเนอร์ขนส่งมีความยาวสั้น สามารถบรรจุแท่งยาว 1 เท่านั้น เรามีบาร์จำนวน n แท่ง และความยาวของแท่งเหล่านั้นอยู่ในรายการ ดังนั้นเพื่อให้พอดีกับแถบทั้งหมดในภาชนะ เราต้องตัดและแบ่งแท่งทั้งหมดเพื่อให้มีขนาดหน่วย นอกจากนี้ เราใส่แท่งทั้งหมดลงในคอนเทนเนอร์ที่ทำให้เราเสียค่าดำเนินการเพียงครั้งเดียว เราต้องหาจำนวนการดำเนินการที่เราต้องทำบนบาร์

ดังนั้น หากอินพุตเป็นเหมือน input_arr =[6, 3, 7] เอาต์พุตจะเป็น 22

• ในการทำให้แท่งขนาด 6 เป็นแท่งขนาด 1 เราต้องดำเนินการ 10 ครั้ง

• ในการทำให้แท่งขนาด 3 เป็นแท่งขนาด 1 เราต้องดำเนินการ 4 ครั้ง

• ในการทำให้แท่งขนาด 7 เป็นแท่งขนาด 1 เราต้องดำเนินการ 8 ครั้ง

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

• กำหนดฟังก์ชัน prime_find() นี่จะใช้เวลา input_num

  • prime_check :=รายการใหม่ของค่าขนาดพื้นของ ((input_num-1)/2) ที่มีค่า True

  • สำหรับ p_num ในช่วง 3 ถึงพื้นของสแควร์รูทของ (input_num) +1 เพิ่มขึ้น 2 ทำ

    • ถ้า prime_check[floor value of (p_num-3)/2] ไม่ใช่ศูนย์ แล้ว

      • สำหรับแต่ละองค์ประกอบในช่วงค่าพื้นของ (p_num ^ 2-3)/2 ถึง p_num ใน prime_check ทำ

        • prime_check[element] :=รายการขนาดใหม่ (ค่าพื้นของ ((input_num-p_num ^2)/(2*p_num) + 1)) มีค่าเป็นเท็จ

  • สำหรับฉันในช่วง 0 ถึงค่าพื้นของ (input_num - 1) / 2 ทำ

    • ถ้า prime_check[i] เป็น True −

      • ส่งคืนรายการที่มีค่า 2 + 2 * i + 3

• จากหน้าที่หลัก ให้ทำดังต่อไปนี้ -

  • prime_nums :=prime_find(10^6 + 100)
  • ผลลัพธ์ :=0
  • สำหรับแต่ละค่าใน input_arr ให้ทำ
    • ผลลัพธ์ :=ผลลัพธ์ + ค่า
    • f_list :=รายการใหม่
    • สำหรับแต่ละ p_num ใน prime_nums ให้ทำ
      • ในขณะที่ค่า mod p_num เหมือนกับ 0, do
        • ใส่ p_num ต่อท้าย f_list
        • value :=ค่าพื้นของ (value / p_num)
      • ถ้า p_num^2> ค่า แล้ว
        • ถ้าค่า> 1 แล้ว
          • ใส่ค่าที่ท้าย f_list
        • ออกจากลูป
    • 
      
      • อุณหภูมิ :=1
      • สำหรับแต่ละ p_num ใน f_list ในลำดับที่กลับกัน ทำ
        • ผลลัพธ์ :=ผลลัพธ์ + อุณหภูมิ
        • อุณหภูมิ :=อุณหภูมิ * p_num
  • ผลตอบแทน

ตัวอย่าง

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

from math import floor,sqrt
def prime_find(input_num):
   prime_check = [True]*((input_num-1)//2)
   for p_num in range(3,floor(sqrt(input_num))+1,2):
      if prime_check[(p_num-3)//2]: prime_check[(p_num**2-3)//2::p_num] = [False] * ((input_num-p_num**2)//(2*p_num) + 1)
   return [2]+[2*i+3 for i in range((input_num - 1) // 2) if prime_check[i]]
def solve(input_arr):
   prime_nums = prime_find(10**6+100)
   result = 0
   for value in input_arr:
      result += value
      f_list = []
      for p_num in prime_nums:
         while value % p_num == 0:
            f_list.append(p_num)
            value //= p_num
         if p_num**2 > value:
            if value > 1:
               f_list.append(value)
         break
      temp = 1
      for p_num in f_list[-1::-1]:
         result += temp
         temp *= p_num
   return result
if __name__ == "__main__":
print(solve([6, 3, 7]))

อินพุต

[6, 3, 7]

ผลลัพธ์

22