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

แอปพลิเคชันเกี่ยวกับทฤษฎีบทการลงคะแนนเสียงของ Bertrandí ใน C/C++


ในเอกสารต้นฉบับของ Bertrand เขาอธิบายการพิสูจน์ที่ขึ้นอยู่กับสูตรทั่วไปสำหรับจำนวนลำดับที่น่าพอใจซึ่งใช้ความสัมพันธ์แบบเรียกซ้ำ

ตัวอย่าง

ให้มีผู้ลงคะแนน 5 คน โดย 3 คนโหวตให้ผู้สมัคร A และ 2 คะแนนสำหรับผู้สมัคร B (ดังนั้น p =3 และ q =2) ลำดับการโหวตมีความเป็นไปได้สิบประการ -

  • AAABB

  • AABAB

  • เอบีเอบี

  • BAAAB

  • AABBA

  • อาบาบา

  • บาบา

  • เอบีเอ

  • บาบา

  • BBAAA

สำหรับคำสั่ง AABAB จะมีการนับคะแนนเสียงเมื่อการเลือกตั้งดำเนินไปด้านล่าง −

ผู้สมัคร
1 2 2 3 3
0 0 1 1 2

สำหรับแต่ละคอลัมน์ การนับสำหรับ A จะมากกว่าคะแนนสำหรับ B เสมอ ดังนั้น A จึงอยู่ข้างหน้า B อย่างเคร่งครัด สำหรับลำดับ AABBA การนับคะแนนในขณะที่การเลือกตั้งดำเนินไปมีดังนี้ -

ผู้สมัคร
1 2 2 2 3
0 0 1 2 2

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