โจทย์: เริ่มที่ตำแหน่ง N บนเส้นจำนวน เดิน N ครั้ง แต่ละครั้งเดินซ้าย (probability L) หรือขวา (1-L) หาความน่าจะเป็นที่จะอยู่ที่แต่ละตำแหน่งหลังเดินครบ N ครั้ง
ตัวอย่าง: N=2, L=0.5 → ตำแหน่งเป็นไปได้: 0, 1, 2, 3, 4 (offset จาก 0 ถึง 2N) ความน่าจะเป็น: [0.25, 0, 0.5, 0, 0.25]
Dynamic Programming Approach
A[i][j]= ความน่าจะเป็นอยู่ที่ตำแหน่ง j หลัง i ครั้ง (j = 0..2N)- เริ่ม:
A[1][N+1] = 1-L(ขวา),A[1][N-1] = L(ซ้าย) - Transition:
- จากซ้าย:
A[i][j] += A[i-1][j-1] * (1-L) - จากขวา:
A[i][j] += A[i-1][j+1] * L
- จากซ้าย:
- คำตอบ:
A[N][0..2N]
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
void find_prob(int n, double low) {
double high = 1 - low;
double A[n + 1][2 * n + 1] = {{0}};
A[1][n + 1] = high;
A[1][n - 1] = low;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= 2 * n; j++)
A[i][j] += A[i - 1][j - 1] * high;
for (int j = 2 * n - 1; j >= 0; j--)
A[i][j] += A[i - 1][j + 1] * low;
}
for (int i = 0; i < 2*n+1; i++)
cout << A[n][i] << endl;
}
int main() {
int n = 2;
double low = 0.6;
find_prob(n, low);
}
อินพุต
2, 0.6
เอาต์พุท
0.36 0 0.48 0 0.16
สังเกต
- ตำแหน่งคู่/คี่ สลับกันเป็น 0 เพราะ parity ของ steps
- Sum ของ probabilities = 1 เสมอ
- เป็น Binomial Distribution ที่ปรับเปลี่ยน
