Cプログラミング
 Computer >> コンピューター >  >> プログラミング >> Cプログラミング

C/C++で学ぶベルトランの投票定理：開票順序から導くリード維持確率

はじめに

ベルトランの原論文では、漸化式（再帰関係）を用いて「有利な投票順列の総数」を求める一般公式に基づく証明が示されています。この定理（Bertrand's Ballot Theorem）は、開票の過程において一方の候補者が他方の候補者に対して常に厳密にリードし続ける確率を与えるものであり、組合せ論やアルゴリズム設計の分野でも重要な概念です。

具体例

有権者が5人おり、そのうち3人が候補者Aに、残りの2人が候補者Bに投票するとします（すなわち p = 3、q = 2）。このとき、投票が投じられる順序としては、以下の10通りが考えられます。

  • AAABB

  • AABAB

  • ABAAB

  • BAAAB

  • AABBA

  • ABABA

  • BAABA

  • ABBAA

  • BABAA

  • BBAAA

ケース1：投票順序が AABAB の場合

まず、開票が進むにつれて各候補者の累積得票数がどのように変化するかを表にまとめます。

候補者AABAB
A12233
B00112

どの列を見ても A の累積得票数が常に B のそれよりも大きいため、A は最初から最後まで B を厳密にリードしています。

ケース2：投票順序が AABBA の場合

次に、別の順序 AABBA の場合の得票数の推移を見てみましょう。

候補者AABBA
A12223
B00122

この場合、4票目の時点で B が A と同票になり、A は終始厳密にリードしているとは言えません。

確率の計算結果

上記の10通りの可能な順序のうち、A が開票の全過程で B をリードし続けるのは AAABB と AABAB の2通りだけです。したがって、A が常に厳密に先行する確率は次のように求まります。

2 / 10 = 1 / 5

これは、定理が予測する値 (p − q) / (p + q)、すなわち (3 − 2) / (3 + 2) = 1/5 と正確に一致しています。このように、ベルトランの投票定理は実際の開票順列の数え上げとも整合することが確認できます。

  1. C/C++のmemcpy()関数の使い方と実例解説

    この記事では、C++ STLにおけるmemcpy()関数の動作、構文、および具体的な使用例について詳しく解説します。 memcpy()とは? memcpy()関数は、C++ STLに組み込まれた標準関数の一つで、<cstring>ヘッダーファイルで定義されています。この関数はメモリブロックをコピーするために使用され、あるメモリ位置から別のメモリ位置へ、指定されたバイト数分のデータを転送します。 関数の実行結果は、データのバイナリコピーとなります。重要な点として、memcpy()は終端のNULL文字やその他の終端記号をチェックしません。単純にソースから指定されたバイト数(num)をそ

  2. C/C++で学ぶAA木（AA Tree）とは？基本概念と平衡化操作を徹底解説

    AA木（AA Tree）とはコンピュータサイエンスにおいて、AA木（AA Tree）とは、順序付きデータを効率的に格納・検索するために実装された平衡木（バランスドツリー）の一種です。AA木は、赤黒木（Red-Black Tree）の変種として扱われます。赤黒木は二分探索木の一形態であり、要素の追加や削除を効率的にサポートします。赤黒木と大きく異なる点は、AA木では赤いノードを右の子としてのみ追加でき、左の子としては配置できないという制約があることです。この制約により、2-3-4木ではなく2-3木をシミュレートすることになり、その結果、木の保守操作が大幅に簡素化されます。赤黒木の平衡化アルゴリズ