C++で解く!N回のコイントスで表が少なくともK回出る確率の求め方

確率とは、与えられたデータの集合の中から望ましい結果が得られる可能性のことです。確率は必ず0以上1以下の範囲に収まり、0は「絶対に起こらない」こと、1は「必ず起こる」ことを意味します。

確率とは何か?

数学における確率は、事象の不確実性を測定・分析するための重要な道具です。言い換えるなら、確率とはある事象が発生する見込みを0から1までの数値で表現したものであり、その数値が1に近づくほど事象が実現しやすいことを示します。

例えば、次のようなものが挙げられます。

• 偏りのないコインを1回投げたときに表が出る確率
• サイコロを1回振ったときに3の目が出る確率

問題設定：N回のトスで表がK回以上出る確率

本記事で扱うのは、「コインをN回投げたときに、表が少なくともK回出る確率を求める」という問題です。

まず具体例を見てみましょう。3枚のコインを投げ、k=2(表が2回以上)とします。コインの投げ方(結果の並び)は全部で 2³ = 8 通りあります。

すべての結果の組み合わせ：

HHH、HTH、HHT、HTT、THH、THT、TTT、TTH

このうち表が2回以上含まれる組み合わせ：

HHH、HTH、HHT、THH

該当するのは4通りなので、求める確率は 4/8、すなわち 0.5 となります。

入出力例

Input: k = 1, n = 3
Output: 0.875

Input: k = 3, n = 6
Output: 0.65625

解決のためのアプローチ

この問題は、二項分布の考え方を利用して解くことができます。表がちょうどi回出る確率は「C(n, i) / 2ⁿ」で表されるため、i = k から n までの確率をすべて足し合わせれば答えが得られます。具体的には以下の手順で進めます。

• n と k を入力として受け取ります。
• 階乗の値をあらかじめ配列に格納(前計算)しておき、必要なときにすぐ参照できるようにします。
• i = k から n までの各場合について組み合わせの数 C(n, i) を計算し、合計します。
• 合計を全事象数 2ⁿ で割り、結果を返します。

アルゴリズム

Step 1 → 「n回のトスで表が少なくともk回出る確率」を計算する関数を宣言
    double probability(int k, int n)
    double型変数 check を宣言し 0 で初期化
    ループ:i = k から i <= n まで ++i ずつ繰り返す
        check += temp[n] / (temp[i] * temp[n - i])
    ループ終了後、check = check / (1LL << n) を実行
    check を返す
Step 2 → 階乗を前計算する関数を宣言
    void precompute()
    temp[0] = temp[1] = 1 を設定
    ループ:i = 2 から i < 20 まで ++i ずつ繰り返す
        temp[i] = temp[i - 1] * i
Step 3 → main関数内
    precompute() を呼び出す
    probability(1, 3) を呼び出して結果を表示
終了

C++での実装例

#include<bits/stdc++.h>
using namespace std;
#define size 21
double temp[size];
// n回のコイントスで少なくともk回の表が出る確率を計算する
double probability(int k, int n) {
    double check = 0;
    for (int i = k; i <= n; ++i)
    check += temp[n] / (temp[i] * temp[n - i]);
    check = check / (1LL << n);
    return check;
}
void precompute() {
    temp[0] = temp[1] = 1;
    for (int i = 2; i < 20; ++i)
    temp[i] = temp[i - 1] * i;
}
int main() {
    precompute();
    // 3枚のコインから1回以上表が出る確率
    cout<<"probability is : "<<probability(1, 3) << "\n";
    // 6枚のコインから3回以上表が出る確率
    cout<<"probability is : "<<probability(3, 6) <<"\n";
    return 0;
}

実行結果

probability is : 0.875
probability is : 0.65625

まとめ

このように、階乗を事前に配列へ格納しておくことで組み合わせの計算を効率化でき、「N回のトスで表がK回以上出る確率」をシンプルなコードで求められます。二項分布の性質を理解すれば、同様の考え方はサイコロやくじなど、他の確率問題にも応用できます。