首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

HDU 1204 糖果大戰:馬爾可夫鏈求期望(賭徒毀滅問題變體)

     編輯:關於C++

問題建模

Speakless 有 N 顆糖,Gardon 有 M 顆。每局:
Speakless 獨贏概率 p(1−q) → 獲得 1 顆糖。
Gardon 獨贏概率 q(1−p) → 失去 1 顆糖。
平局概率 1−p(1−q)−q(1−p) → 狀態不變。
求 Speakless 最終贏光所有糖的概率。

遞推方程化簡

設 f[i] = 擁有 i 顆糖時獲勝概率。
f[i] = p(1−q)f[i+1] + q(1−p)f[i−1] + (1−p(1−q)−q(1−p))f[i]。
移項得:
(f[i+1]−f[i]) × p(1−q) = (f[i]−f[i−1]) × q(1−p)。
設 k = q(1−p) / (p(1−q))。
則 f[i+1]−f[i] = k × (f[i]−f[i−1])。
邊界:f[0]=0,f[N+M]=1。
等比數列求和得閉式解:
f[N] = (1−kN) / (1−kN+M) (k≠1)。
k=1 時退化為 f[N] = N/(N+M)。

代碼實現

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    double p, q;
    while (cin >> N >> M >> p >> q) {
        if (M == 0) { cout << "1.00\n"; continue; }
        if (N == 0 || p == 0 || q == 1) { cout << "0.00\n"; continue; }
        double k = q * (1 - p) / (p * (1 - q));
        double ans;
        if (fabs(k - 1.0) < 1e-12)
            ans = 1.0 * N / (N + M);
        else
            ans = (1 - pow(k, N)) / (1 - pow(k, N + M));
        cout << fixed << setprecision(2) << ans << '\n';
    }
    return 0;
}

邊界處理

  • k 接近 1 時用極限公式避免除零。
  • p=0 或 q=1 直接輸出 0。
  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved