C++でランダムに折った棒の断片からn角形を作れる確率を求める方法

問題概要

任意の長さの棒があり、その棒をランダムに n 個の断片(整数値または浮動小数点数)に分割することを考えます。このとき、分割された断片が n 角形(多角形)を形成できる確率を求めるのが本記事の目的です。

多角形が成立するためには、どの一辺も他のすべての辺の合計より短くなければなりません。この条件を満たす確率は、次の公式で計算できます。

P(E′) = 1 − P(E) = 1 − n / 2ⁿ⁻¹

ここで、n は棒を分割した際に生成される断片の本数です。

入力例と出力例

入力 

length = 10 , pieces = 4

出力 

probability is : 0.5

説明 − 長さ10cmの棒を4つの部分に分割するケースです。

入力 

length = 5 , pieces = 3

出力 

probability is : 0.25

説明 − 長さ5cmの棒を3つの部分に分割するケースです。

補足：公式が成り立つ理由

n 本の断片が n 角形を形成できる条件は「最も長い断片の長さが、残りの断片の合計より小さいこと」です。ランダムな分割においてこの条件を満たす割合は 1 − n / 2ⁿ⁻¹ となることが知られています。また、この確率は棒の元の長さ(len)には依存せず、分割数 n のみで決まる点にも注目してください。たとえば n=3 の場合は 1 − 3/4 = 0.25 となり、先ほどの出力例とも一致します。

プログラムで使用しているアプローチ

• 棒の長さと分割後の断片の本数を入力として受け取る

• 公式を適用して確率を計算する

• 結果を出力する

アルゴリズム

開始
ステップ1 → 確率を計算する関数を宣言する
    double probab(unsigned len, unsigned pieces)
        unsigned a = (1 << (pieces-1)) を宣言
        return 1.0 - ((double)pieces) / ((double)a)) を返す
ステップ2 → main() 内で
    unsigned pieces = 4, len = 10 を宣言
    probab(len, pieces) を呼び出す
終了

C++実装例

#include<iostream>
using namespace std;
// 確率を計算する関数
double probab(unsigned len, unsigned pieces){
    unsigned a = (1 << (pieces-1));
    return 1.0 - ((double)pieces) / ((double)a);
}
int main(){
    unsigned pieces = 4, len = 10;
    cout <<"probability is : "<<probab(len, pieces);
    return 0;
}

※ 元のコードではビットシフト演算子が誤って記述されていましたが、正しくは (1 << (pieces-1)) のように左ビットシフトを使い、2ⁿ⁻¹ を計算します。

出力

上記のコードを実行すると、次の出力が得られます −

probability is : 0.5