HDU 2048 神、上帝以及老天爺：錯排問題與概率計算

題目背景

n 人各寫一張字條放入箱中，隨機抽取。若無人抽到自己的字條，求該事件發生的概率（百分比，保留兩位小數）。n ≤ 20。

錯排數遞推

設 D(n) 為 n 個元素的錯排數。考慮第 n 個人的字條：
① 前 n-1 人已錯排，第 n 人與任意一人交換：(n-1)·D(n-1) 種。
② 前 n-1 人中恰有一人拿到自己字條，其餘錯排，第 n 人與那人交換：(n-1)·D(n-2) 種。
遞推：D(n) = (n-1) * (D(n-1) + D(n-2))，D(1)=0, D(2)=1。
概率 f(n) = D(n)/n!，遞推化簡為 f(n) = ((n-1)*f(n-1) + f(n-2)) / n，f(1)=0, f(2)=0.5。直接預計算 f[1..20] 即可。

代碼 (C)

#include <stdio.h>
int main() {
    double f[22] = {0, 0, 0.5};
    for (int n = 3; n < 22; n++)
        f[n] = ((n-1)*f[n-1] + f[n-2]) / n;
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        printf("%.2lf%%\n", f[n] * 100);
    }
    return 0;
}