โปรแกรมค้นหาลำดับการสืบทอดในครอบครัวใน Python

สมมติว่ามีครอบครัวที่ประกอบด้วยสมาชิกจากรุ่นต่างๆ เช่นครอบครัวมีพ่อลูกและยาย แต่การเกิดและการตายเกิดขึ้นในแต่ละครอบครัว

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

ฟังก์ชันที่สองใช้เมื่อมีคนตาย ใช้ชื่อของสมาชิกในครอบครัวที่เสียชีวิตเป็นข้อมูลป้อนเข้าและนำออกจากบันทึก

ฟังก์ชันที่สามให้ลำดับการสืบทอด ลำดับมรดกปัจจุบันจะถูกพิมพ์ทุกครั้งที่มีการเรียกใช้

ดังนั้นสำหรับชุดอินพุต เราต้องหาลำดับของมรดก ดังนั้นถ้าลำดับของข้อมูลเข้าเหมือนการเกิด เกิด เกิด เกิด เกิด ตาย มรดก ความตาย มรดก ผลที่ได้ก็จะเป็น ['Zach', 'Jesse' , 'Ursula', 'Ryan', 'Thea'] ['Jesse', 'Ursula', 'Ryan', 'Thea']

ตอนแรกหัวหน้าครอบครัวคือพอล

จากนั้น Paul ก็มีบุตรชื่อ Zach และ Jesse ตามลำดับ

เจสซีมีลูกสามคน; Ursula, Ryan และ Thea, Ursula เป็นพี่คนโตและ Thea เป็นน้องคนสุดท้อง

จากนั้นพอลก็ตาย ลำดับการสืบทอดคือ ['Zach', 'Jesse', 'Ursula', 'Ryan', 'Thea'].

จากนั้นแซคก็ตาย ลำดับการสืบทอดกลายเป็น ['Jesse', 'Ursula', 'Ryan', 'Thea']

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

• family :=แผนที่ใหม่ที่มีรายการเป็นค่า

• head :=หัวหน้าครอบครัวคนปัจจุบัน

• ตาย :=ชุด

• กำหนดฟังก์ชัน birth() นี่จะใช้เวลา p_name, c_name

  • ใส่ c_name ต่อท้ายตระกูล[p_name]

• กำหนดฟังก์ชัน death() นี้จะใช้ชื่อ

  • เพิ่ม (ชื่อ) ให้กับชุดที่ตายแล้ว

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

  • ans :=รายการใหม่

  • deep_search(หัว)

  • กลับมาอีกครั้ง

• กำหนดฟังก์ชั่น deep_search() นี่จะเป็นปัจจุบัน

  • ถ้ากระแสไม่ตายแล้ว

    • แทรกกระแสที่ส่วนท้ายของ ans

  • สำหรับเด็กแต่ละคนในครอบครัว[ปัจจุบัน] ทำ

    • deep_search(ลูก)

ตัวอย่าง

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

from collections import defaultdict
class Solution:

   def __init__(self, head_name):
      self.family = defaultdict(list)
      self.head = head_name
      self.dead = set()

   def birth(self, p_name, c_name):
      self.family[p_name].append(c_name)

   def death(self, name):
      self.dead.add(name)

   def inheritance(self):
      self.ans = []
      self.depth_search(self.head)
      return self.ans

   def depth_search(self, current):
      if current not in self.dead:
         self.ans.append(current)
      for child in self.family[current]:
         self.depth_search(child)

ob = Solution('Paul')
ob.birth('Paul', 'Zach')
ob.birth('Paul', 'Jesse')
ob.birth('Jesse', 'Ursula')
ob.birth('Jesse', 'Ryan')
ob.birth('Jesse', 'Thea')
ob.death('Paul')
print(ob.inheritance())
ob.death('Zach')
print(ob.inheritance())

อินพุต

ob = Solution('Paul')
ob.birth('Paul', 'Zach')
ob.birth('Paul', 'Jesse')
ob.birth('Jesse', 'Ursula')
ob.birth('Jesse', 'Ryan')
ob.birth('Jesse', 'Thea')
ob.death('Paul')
print(ob.inheritance())
ob.death('Zach')
print(ob.inheritance())

ผลลัพธ์

['Zach', 'Jesse', 'Ursula', 'Ryan', 'Thea']
['Jesse', 'Ursula', 'Ryan', 'Thea']