โปรแกรม Python หาขนาดของบัสที่บรรจุเพื่อนในกลุ่มได้หมด

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

ดังนั้น หากอินพุตเป็นเหมือนกลุ่มหรือ gr_no =[3, 4, 2, 2, 1, 4, 3, 5] ผลลัพธ์จะเป็น [12, 24]

หากรถบัสขนาด 12 สามารถมีกลุ่ม 1-5 ในการเดินทางครั้งแรก และกลุ่มอื่นๆ ในทริปที่สองได้

หากขนาดรถบัสเป็น 24 ก็จะมีทุกกลุ่มและขนส่งได้เที่ยวเดียวเท่านั้น

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

• กำหนดฟังก์ชัน factor_ret() นี่จะใช้เวลา n
  • สำหรับ i ในช่วง (0 ถึง n ^ 0.5), ทำ
    • ถ้า n mod i เหมือนกับ 0 แล้ว
      • เพิ่ม tuple(i, ค่าพื้นของ (n/i)) ลงใน output_list
  • เรียงลำดับรายการ output_list
  • ส่งคืน output_list เป็นชุด
• ทำตามขั้นตอนต่อไปนี้ -
• รวม :=รายการใหม่ที่มีรายการ gr_no[0]
• สำหรับฉันในช่วง 1 ถึงขนาด gr_no ทำ
  • ใส่ผลรวม[i - 1] + gr_no[i] ที่ส่วนท้ายของผลรวม
• b_sizes :=รายการใหม่
• สำหรับแต่ละขนาดใน factor_ret(ผลรวมของรายการ (gr_no)) ทำ
  • temp_list :=รายการใหม่จากองค์ประกอบทั้งหมดที่ไม่ใช่ศูนย์จากทั้งหมด
  • ดัชนี :=1
  • ตัวบ่งชี้ :=จริง
  • สำหรับแต่ละจุดใน temp_list ให้ทำ
    • ถ้า point ไม่เหมือนกับ size * index แล้ว
      • ตัวบ่งชี้ :=เท็จ
      • ออกมาจากวงจร
    • ดัชนี :=ดัชนี + 1
  • ถ้าตัวบ่งชี้เป็นจริง ดังนั้น
    • ใส่ขนาดที่ส่วนท้ายของ b_sizes
• ส่งคืน b_sizes

ตัวอย่าง

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

from functools import reduce
def solve(gr_no):
   total = [gr_no[0]]
   for i in range(1, len(gr_no)):
      total.append(total[i - 1] + gr_no[i])
   b_sizes = []
   for size in factor_ret(sum(gr_no)):
      temp_list = list(filter(lambda x : x % size == 0, total))
      index = 1
      indicator = True
      for point in temp_list:
         if point != size * index:
            indicator = False
            break
         index += 1
      if indicator:
         b_sizes.append(size)
   return b_sizes
def factor_ret(n):
   return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
print(solve([3, 4, 2, 2, 1, 4, 3, 5]))

อินพุต

[3, 4, 2, 2, 1, 4, 3, 5]

ผลลัพธ์

[12, 24]