HDU 2048 遙控器概率問題：錯排公式與動態規劃 C 實現

HDU 2048 完全錯排問題：遞推公式 D(n) = (n-1)[D(n-1)+D(n-2)] 與大數概率計算

經典組合數學問題：n 人隨機抽取姓名條，無人抽到自己姓名的概率。使用錯排數遞推公式高效求解。

問題數學建模

n 個元素的完全排列中，無元素在原位置的排列數稱為錯排數 D(n) 或 !n。

遞推公式推導

考慮第 1 個人抽到第 k 個人的條 (k ≠ 1)：
情況 1：第 k 個人抽到第 1 個人的條 → 形成 2-循環
        剩餘 n-2 人錯排：D(n-2) 種
情況 2：第 k 個人不抽第 1 個人的條
        相當於 n-1 人錯排 (第 k 人視為「第 1 人」)：D(n-1) 種
k 有 n-1 種選擇
∴ D(n) = (n-1) * [D(n-1) + D(n-2)]

邊界條件

D(1) = 0  // 1人必抽到自己
D(2) = 1  // 互換

C 語言實現

#include 

double derangement[25];  // 全局自動初始化為 0

double factorial(int n) {
    double f = 1;
    for (int i = 2; i <= n; i++) f *= i;
    return f;
}

int main() {
    derangement[1] = 0;
    derangement[2] = 1;
    for (int i = 3; i <= 20; i++)
        derangement[i] = (i-1) * (derangement[i-1] + derangement[i-2]);
    
    int C, n;
    while (scanf("%d", &C) != EOF) {
        while (C--) {
            scanf("%d", &n);
            double prob = derangement[n] * 100.0 / factorial(n);
            printf("%.2f%%\n", prob);
        }
    }
    return 0;
}

關鍵技術點

• 全局靜態數組：避免棧溢出，自動零初始化
• double 精度：20! ≈ 2.4e18，double 53 位尾數足夠精確
• 遞推預計算：O(n) 預處理，O(1) 答題
• 格式化輸出：%.2f%% 百分比保留兩位小數

數值驗證

極限概率趨近 1/e ≈ 36.7879%。

擴展：包含固定點的排列計數

// 恰好 k 個固定點：C(n,k) * D(n-k)
// 至少 1 個固定點：n! - D(n)

錯排問題是組合數學與動態規劃結合的經典教學案例。