โปรแกรมนับจำนวนแมตช์ที่เล่นในทัวร์นาเมนต์ใน Python

สมมติว่าเรามีตัวเลข n ดังนั้นในทัวร์นาเมนต์จึงมีทีมจำนวน n ทีมที่มีกฎเกณฑ์บางประการ -

• ถ้าจำนวนทีมเท่ากัน แต่ละทีมก็จะรวมทีมกับอีกทีมหนึ่ง และมีการเล่นแมตช์ทั้งหมด (n/2) จากพวกเขา (n/2) ทีมที่ชนะจะเข้าสู่รอบต่อไป

• หากจำนวนทีมเป็นเลขคี่ จะมีการสุ่มย้ายทีมหนึ่งทีมในทัวร์นาเมนต์ ที่เหลือจะถูกรวมเข้าด้วยกัน จึงมีการแข่งขันทั้งหมด (n-1)/2 แมตช์ และทีม (n-1)/2+1 จะถูกย้ายไปยังรอบถัดไปในฐานะผู้ชนะ

เราต้องหาจำนวนแมตช์ที่เล่นทั้งหมดเพื่อให้ได้ผู้ชนะในขั้นสุดท้าย

ดังนั้นหากอินพุตเท่ากับ n =10 เอาต์พุตจะเป็น 9 เพราะ

• เริ่มแรกจะมี 5-5 ดิวิชั่น โดย 5 คนจะผ่านเข้ารอบ

• ตอนนี้ส่งหนึ่งทีมเข้าสู่เกมและแบ่ง 2-2 ทีม ดังนั้น 3 จะผ่านเข้ารอบ

• ตอนนี้ส่งหนึ่งทีมเข้าสู่เกมและแบ่งทีม 1-1 ดังนั้น 2 ทีมจึงจะผ่านเข้ารอบ

• หาร 1-1 และหนึ่งจะผ่านเข้ารอบเป็นผู้ชนะ

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

• ตอบ :=0

• ในขณะที่ n ไม่เหมือนกับ 1 ทำ

  • f :=ชั้นของ (n/2)

  • ส่วนที่เหลือ :=n mod 2

  • ans :=ans + f

  • n :=f + เศษ

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

ตัวอย่าง (Python)

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

def solve(n):
   ans = 0
   while n != 1:
      f = n//2
      remainder = n % 2
      ans += f
      n = f + remainder

   return ans

n = 10
print(solve(n))

อินพุต

10

ผลลัพธ์

9