【C++】2歩または3歩ずつ進むとき指定地点に到達する確率を求める方法

人物「A」が開始位置 X = 0 から歩き始めます。この課題では、一度に2歩または3歩ずつ進むことができる場合に、ちょうど X = num の地点に到達する確率を求めます。ステップ長が2である確率を P、ステップ長が3である確率を 1 − P とします。

入力例

num = 5, p = 0.2

出力例

0.32

説明

num = 5 に到達する方法は2通りあります。
2+3 の順に進む場合：確率 0.2 × 0.8 = 0.16
3+2 の順に進む場合：確率 0.8 × 0.2 = 0.16
したがって、合計確率は 0.16 + 0.16 = 0.32 となります。

別の例も見てみましょう。

入力例

num = 2, p = 0.1

出力例

0.1

問題を解くためのアプローチ

この問題は動的計画法（Dynamic Programming）を用いることで効率的に解くことができます。各地点に到達する確率を小さい問題から順に求めていくことで、重複する計算を避けられます。

解法の手順は以下のとおりです。

• サイズ num + 1 の確率配列 probab を宣言し、初期値を次のように設定します。
  probab[0] = 1、probab[1] = 0、probab[2] = p、probab[3] = 1 − p

• i を 4 から num までインクリメントしながら反復処理を行います。

• 各 i に対して、probab[i] = (p) * probab[i − 2] + (1 − p) * probab[i − 3] と計算します。

• 最後に probab[num] を返します。

• 結果を出力します。

アルゴリズム

Start
Step 1 → 一度に2歩または3歩で地点に到達する確率を計算する関数を宣言
    float probab(int num, float p)
        double probab[num + 1] を宣言
        probab[0] = 1 を設定
        probab[1] = 0 を設定
        probab[2] = p を設定
        probab[3] = 1 − p を設定
        int i = 4 から i <= num まで ++i でループ
            probab[i] = (p) * probab[i − 2] + (1 − p) * probab[i − 3] を設定
        ループ終了
        return probab[num]
Step 2 → main() 内での処理
    int num = 2 を宣言
    float p = 0.1 を宣言
    probab(num, p) を呼び出す
Stop

実装例

#include <bits/stdc++.h>
using namespace std;
// 一度に2歩または3歩で地点に到達する確率を計算する関数
float probab(int num, float p){
    double probab[num + 1];
    probab[0] = 1;
    probab[1] = 0;
    probab[2] = p;
    probab[3] = 1 - p;
    for (int i = 4; i <= num; ++i)
        probab[i] = (p)*probab[i - 2] + (1 - p) * probab[i - 3];
    return probab[num];
}
int main(){
    int num = 2;
    float p = 0.1;
    cout<<"probability is : "<<probab(num, p);
    return 0;
}

実行結果

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

probability is : 0.1

このように、動的計画法を活用することで、各地点への到達確率を漸化式的に求めることができ、num が大きくなっても線形時間 O(num) で効率的に計算できます。確率の問題をDPで扱う際は、初期条件の設定（到達できない地点は確率0とするなど）が重要なポイントになります。