사람 "A"가 시작 위치 X =0에서 걷고 있습니다. 작업은 2 또는 3을 취할 수 있는 경우 정확히 X =num에 도달할 확률을 찾는 것입니다. 단계. 단계 길이 2의 확률, 즉 P, 단계 길이 3의 확률은 1 - P입니다.
입력
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