HDU 2048 神、上帝以及老天爺：錯排問題與遞推公式

問題描述

n 人各寫一張名條放入箱中，隨機取一張。若有人取到自己的名條則中獎。求「無人中獎」的概率（百分比，保留兩位小數）。n ≤ 20，多測試案例。

錯排數遞推公式

設 f(n) 為 n 個元素的錯排數（無元素在原位置）。考慮第 1 個人：
- 若他取到第 k 張（k≠1），則第 k 人有兩種情況：
1) 第 k 人取第 1 張 → 剩餘 n-2 人錯排：f(n-2)
2) 第 k 人不取第 1 張 → 剩餘 n-1 人錯排（將第 1 張視為第 k 人的「原位置」）：f(n-1)
共有 n-1 種選擇 k，故：
f(n) = (n-1) * (f(n-1) + f(n-2))
初值：f(1)=0, f(2)=1。

概率計算

總排列數 n!。概率 = f(n) / n! × 100%。預計算 f[1..20] 和 fact[1..20]（long long 足夠）。

代碼實現

#include 
using namespace std;
long long f[21], fact[21];
int main() {
    f[1]=0; f[2]=1; fact[1]=1; fact[2]=2;
    for (int i=3;i<=20;++i) {
        fact[i] = fact[i-1]*i;
        f[i] = (i-1)*(f[i-1]+f[i-2]);
    }
    int C; cin >> C;
    while (C--) {
        int n; cin >> n;
        double p = 100.0 * f[n] / fact[n];
        printf("%.2f%%\n", p);
    }
    return 0;
}

樣例驗證

n=2: f(2)=1, 2!=2, 概率 50.00% → 輸出 "50.00%"。

擴展

錯排數也稱子階乘，通項公式：f(n) = n! * Σ_{k=0..n} (-1)^k/k!。遞推法編程更簡便。