C++で一度に2つまたは3つのステップでポイントに到達する確率

入力

num = 5, p = 0.2

出力

0.32

説明

There can be 2 ways to reach num, i.e, 5
2+3 with probability 0.2 * 0.8 = 0.16
3+2 with probability 0.8 * 0.2 = 0.16
So, total probability will be 0.16 + 0.16 = 0.32

入力

num = 2, p = 0.1

出力

0.1

問題を解決するために以下で使用するアプローチは次のとおりです

問題を解決するために動的計画法を使用します。

ソリューションでは、-

• サイズがnum+1の確率配列を宣言し、その値を次のように割り当てます。Set probab [0] =1、Set probab [1] =0、Set probab [2] =p、Set probab [3] =1 – p

• 値をインクリメントしながら、iを0からnumまで繰り返します

• すべてのiについて、probab [i] =（p）* probab [i-2] +（1-p）* probab [i-3]

  を設定します。

• 確率を返す[num]

• 結果を印刷します。

アルゴリズム

Start
Step 1→ declare function to calculate probability of reaching a point with 2 or 3 steps
at a time
   float probab(int num, float p)
      Declare double probab[num + 1]
         `Set probab[0] = 1
         Set probab[1] = 0
         Set probab[2] = p
         Set probab[3] = 1 – p
         Loop For int i = 4 and i <= num and ++i
            Set probab[i] = (p)*probab[i - 2] + (1 - p) * probab[i - 3]
         End
         return probab[num]
Step 2→ In main()
   Declare int num = 2
   Declare float p = 0.1
   Call probab(num, p)
Stop

例

#include <bits/stdc++.h>
using namespace std;
//function to calculate probability of reaching a point with 2 or 3 steps at a time
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