ความน่าจะเป็นในการเดินถึงจุดหมายด้วยก้าว 2 หรือ 3 ใน C++

บุคคล "A" เดินจากตำแหน่ง X = 0 ต้องการไปถึง X = num โดยแต่ละก้าวเดินได้ 2 หรือ 3 หน่วย ความน่าจะเป็นก้าว 2 คือ P ก้าว 3 คือ 1-P หาความน่าจะเป็นที่จะถึง พอดี ตำแหน่ง num

ตัวอย่าง

num = 5, P = 0.2

วิธีถึง 5:

• 2 + 3: โอกาส = 0.2 × 0.8 = 0.16
• 3 + 2: โอกาส = 0.8 × 0.2 = 0.16

รวม = 0.32

num = 2, P = 0.1

ก้าวเดียว 2: โอกาส = 0.1

Output: 0.1

แนวทางแก้ปัญหา: Dynamic Programming

กำหนด dp[i] = ความน่าจะเป็นถึงตำแหน่ง i ได้พอดี

Base Cases:

dp[0] = 1      // เริ่มที่ 0
dp[1] = 0      // ไปไม่ถึง (ก้าวขั้นต่ำ 2)
dp[2] = P      // ก้าว 2 ครั้งเดียว
dp[3] = 1 - P  // ก้าว 3 ครั้งเดียว

Recurrence (i ≥ 4):

dp[i] = P × dp[i-2] + (1-P) × dp[i-3]

เพราะมาถึง i ได้จาก i-2 (ก้าว 2) หรือ i-3 (ก้าว 3)

ตัวอย่างโค้ด

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

double probabilityReach(int target, double P) {
    if (target < 0) return 0;
    if (target == 0) return 1;
    if (target == 1) return 0;
    
    vector<double> dp(target + 1, 0.0);
    dp[0] = 1.0;
    if (target >= 1) dp[1] = 0.0;
    if (target >= 2) dp[2] = P;
    if (target >= 3) dp[3] = 1.0 - P;
    
    for (int i = 4; i <= target; i++) {
        dp[i] = P * dp[i - 2] + (1.0 - P) * dp[i - 3];
    }
    
    return dp[target];
}

int main() {
    cout << fixed << setprecision(6);
    
    cout << "num=5, P=0.2: " << probabilityReach(5, 0.2) << endl;  // 0.32
    cout << "num=2, P=0.1: " << probabilityReach(2, 0.1) << endl;  // 0.1
    cout << "num=7, P=0.5: " << probabilityReach(7, 0.5) << endl;
    
    // ตารางค่า num=1..10, P=0.5
    cout << "\nTable for P=0.5:\n";
    for (int n = 1; n <= 10; n++) {
        cout << "num=" << n << ": " << probabilityReach(n, 0.5) << endl;
    }
    
    return 0;
}

ผลลัพธ์

num=5, P=0.2: 0.320000
num=2, P=0.1: 0.100000
num=7, P=0.5: 0.312500

Table for P=0.5:
num=1: 0.000000
num=2: 0.500000
num=3: 0.500000
num=4: 0.250000
num=5: 0.250000
num=6: 0.125000
num=7: 0.312500
num=8: 0.156250
num=9: 0.156250
num=10: 0.078125

การเพิ่มประสิทธิภาพพื้นที่ (Space Optimization)

ต้องการแค่ 3 ค่าล่าสุด:

double probabilityReachO1(int target, double P) {
    if (target == 0) return 1;
    if (target == 1) return 0;
    if (target == 2) return P;
    if (target == 3) return 1 - P;
    
    double dp0 = 1, dp1 = 0, dp2 = P, dp3 = 1 - P;
    for (int i = 4; i <= target; i++) {
        double dpi = P * dp2 + (1 - P) * dp1;
        dp0 = dp1; dp1 = dp2; dp2 = dp3; dp3 = dpi;
    }
    return dp3;
}

ความซับซ้อน

• เวลา: O(num)
• พื้นที่: O(num) หรือ O(1) แบบ optimized

ข้อสังเกต

• โจทย์นี้เป็นกรณีพิเศษของ Random Walk with Step Distribution
• Generating Function: G(x) = 1 / (1 - P·x² - (1-P)·x³)
• หา Closed-form ได้จากการแก้ Characteristic Equation: r³ - P·r - (1-P) = 0