1
2

50.00%

N張字條的所有排列可能自然是A(N,N)= N!種排列方式
現在的問題就是N張字條的錯排方式有幾種。分兩種情況討論
①：如果前面N-1個人拿的都不是自己的字條，即前N-1個人滿足錯排，那麼只要第N個人把自己的票與前面N-1個人中的任意一個交換，就可以滿足N個人的錯排。這時有f(N-1)種方法。

②：如果前N-1個人不滿足錯排，而第N個人把自己的字條與其中一個人交換後恰好滿足錯排。即在前面N-1人中，有N-2個人滿足錯排，有且只有一個人拿的是自己的字條，而第N個人恰好與他做了交換，這時候就滿足了錯排。這時有f(n-2)種方法

對於①，因為前N-1個人中，每個人都有機會與第N個人交換，所以有N-1種交換的可能。
對於②，因為前N-1個人中，每個人都有機會拿著自己的字條。所以也有N-1種交換的可能。

所以得錯排遞推公式
1.D[n] = (n-1)*(D[n-1]+D[n-2])

D(1)=0;D(2)=1;

由於計算n!和D[n]數字會非常大，所以我們采用邊做邊除而不是先算D(n)，再除n!的方法。
1.已知D[n]=(n-1)(D[n-1]+D[n-2]);
2.f[n]=D[n]/n!;則有D[n]=n!*f[n];
3.代入可得f[n]=(n-1)(f[n-1]*(n-1)!+f[n-2]*(n-2)!)/n!;
4.即得到錯排概率公式f[n]=(f[n-1](n-1)+f[n-2])/n;

#include 
int main()
{
    double a[22]={0,0,1};
    __int64 i,n=3,m,t,j;
    char d='%';
    while(n<22)
    {
        a[n]=(n-1)*(a[n-1]+a[n-2]);
        n++;
    }
    while(scanf("%d",&i)!=EOF)
    {
        while(i--)
        {
            t=1;
            scanf("%d",&m);
            for(j=1;j<=m;j++) t*=j;
            printf("%.2lf%%\n",a[m]*100/t);
        }
    }
    return 0;
}

ac代碼；

#include 
int main()
{
    double a[22]={0,0,0.5};
    int i,n=3,m,t,j;
    while(n<22)
    {
        a[n]=(a[n-1]*(n-1)+a[n-2])/n;
        n++;
    }
    while(scanf("%d",&i)!=EOF)
    {
        while(i--)
        {
            scanf("%d",&m);
            printf("%.2lf%%\n",a[m]*100);
        }
    }
    return 0;