Computer >> Máy Tính >  >> Lập trình >> lập trình C

Một ứng dụng về định lý lá phiếu Bertrandís trong C / C ++

Trong bài báo gốc của Bertrand, ông giải thích một bằng chứng phụ thuộc vào một công thức chung cho số chuỗi thuận lợi thực hiện một quan hệ đệ quy.

Ví dụ

Có 5 cử tri, trong đó 3 người bầu cho ứng cử viên A và 2 người bầu cho ứng viên B (do đó p =3 và q =2). Mười khả năng tồn tại đối với thứ tự của các phiếu bầu -

  • AAABB

  • AABAB

  • ABAAB

  • BAAAB

  • AABBA

  • ABABA

  • BAABA

  • ABBAA

  • BABAA

  • BBAAA

Đối với lệnh AABAB, việc kiểm phiếu khi cuộc bầu cử diễn ra được đưa ra bên dưới -

Ứng viên A A B A B
A 1 2 2 3 3
B 0 0 1 1 2

Đối với mỗi cột, số phiếu của A luôn lớn hơn số của B nên A luôn dẫn trước B. Đối với thứ tự AABBA, việc kiểm phiếu khi cuộc bầu cử diễn ra được đưa ra dưới đây -

Ứng viên A A B B A
A 1 2 2 2 3
B 0 0 1 2 2

Đối với thứ tự này, B được ràng buộc với A sau lần bỏ phiếu thứ tư, vì vậy A không phải lúc nào cũng đi trước B. Trong số 10 thứ tự có thể có, A luôn đi trước B chỉ trong trường hợp AAABB và AABAB. Vì vậy, xác suất để A luôn dẫn trước đúng là 2/10 =1/5 và điều này thực sự bằng 3-2 / 3 + 2 như định lý dự đoán.