Một người “A” đang đi bộ từ vị trí xuất phát X =0, nhiệm vụ là tìm xác suất để đến chính xác X =num, nếu người đó có thể lấy 2 hoặc 3 các bước. Xác suất cho độ dài bước 2, tức là P, xác suất cho độ dài bước 3 là 1 - P.
Đầu vào
num = 5, p = 0.2
Đầu ra
0.32
Giải thích
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
Đầu vào
num = 2, p = 0.1
Đầu ra
0.1
Phương pháp được sử dụng dưới đây như sau để giải quyết vấn đề
Chúng tôi sẽ sử dụng phương pháp lập trình động để giải quyết vấn đề.
Trong giải pháp, chúng tôi sẽ -
-
Khai báo một mảng xác suất có kích thước là num + 1 và gán các giá trị của nó là, Đặt probab [0] =1, Đặt probab [1] =0, Đặt probab [2] =p, Đặt probab [3] =1 - p
-
Lặp lại i từ 0 đến num, trong khi tăng giá trị của nó
-
Đối với mọi i, Đặt probab [i] =(p) * probab [i - 2] + (1 - p) * probab [i - 3]
-
Trả lại bảng điều tra [num]
-
In kết quả.
Thuật toán
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
Ví dụ
#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;
} Đầu ra
Nếu chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
probability is : 0.1