Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม C

การประยุกต์ใช้ Bertrand's Ballot Theorem ใน C/C++


ในเอกสารต้นฉบับของ Bertrand เขาอธิบาย proof ที่พึ่งพา general formula สำหรับจำนวน favorable sequences โดยใช้ recursion relation

ตัวอย่าง

สมมติมีผู้โหวต 5 คน 3 คนโหวตให้ผู้สมัคร A และ 2 คนโหวตให้ B (p = 3, q = 2) มี 10 ลำดับที่เป็นไปได้ −

  • AAABB
  • AABAB
  • ABAAB
  • BAAAB
  • AABBA
  • ABABA
  • BAABA
  • ABBAA
  • BABAA
  • BBAAA

สำหรับลำดับ AABAB tally ของโหวตตามความคืบหน้าคือ

Candidate A A B A B
A 1 2 2 3 3
B 0 0 1 1 2

สำหรับแต่ละคอลัมน์ tally ของ A มากกว่า B เสมอ ดังนั้น A นำอยู่เสมอ สำหรับ AABBA tally คือ

Candidate A A B B A
A 1 2 2 2 3
B 0 0 1 2 2

ในลำดับนี้ B เสมอกับ A หลังโหวตครั้งที่ 4 ดังนั้น A ไม่นำเสมอ จาก 10 ลำดับ A นำเสมอแค่ AAABB และ AABAB ความน่าจะเป็นคือ 2/10 = 1/5 เท่ากับ (3-2)/(3+2) ตามทฤษฎี