淺析錯排問題

淺析錯排問題

定義：n個有序的元素應有n！種不同的排列。如果一個排列使得所有的元素都不在原來的位置上，則稱這個排列為錯排。任給一個n，求出1，2，3，。。。，n的錯排個數D為多少，並且給出所有的錯排方案

推理：

第一步，把第n個元素放在一個位置，比如位置k，一共有n-1種方法；

第二步，放編號為k的元素，這時有兩種情況：⑴把它放到位置n，那麼，對於剩下的n-1個元素，由於第k個元素放到了位置n，剩下n-2個元素就有D(n-2)種方法；⑵第k個元素不把它放到位置n，這時，對於這n-1個元素，有D(n-1)種方法； so： D(n)=(n-1)*[D(n-1)+D(n-2)]; D(1)=0,D(2)=1 e.g

Oh, my God!

時間限制：1000 ms | 內存限制：65535 KB 難度：2

描述

In order to happy everyone, organizer HRW held an open up partythere have specific requirements for this activity is this:
First of all, all person in the party will have to write a note to his name into the box;Then, after all the note added is completed, each taking a note from the box;Finally, if made note of your name, then "Congratulations, won the party!"
Oh, my God!
Now to the question, you can calculate the probability of this happening?Don't count? Don't you want said by others as a DouBi?! AC it！

輸入

Input file contains several test cases. Each test case consists of a integer numbers n on a line(one≤n≤ten ).The last test case is followed by a line that contains one zeroes. This line must not be processed.

輸出

print the the probability
See the following example.

樣例輸入

2
3
0

樣例輸出

Case [1]: 50.00%.
Case [2]: 33.33%.

提示

要用到錯排公式，計算所有人都抽到自己名字的概率

來源

原創

上傳者

ACM_賀榮偉 題目翻譯：首先，所有參加晚會的人員都將一張寫有自己名字的字條放入抽獎箱中；
然後，待所有字條加入完畢，每人從箱中取一個字條；
最後，如果取得的字條上寫的就是自己的名字，那麼“恭喜你，中獎了！”
求計算一下發生這種情況的概率嗎？
思路：其實就錯排公式的運用 p=D（n）/n!;

#include
int main()
{
    double a[55];
    double b[55];
    a[0]=1;
    for(int i=1;i<=22;i++)
        a[i]=a[i-1]*i;
    b[1]=0;
    b[2]=1;
    b[3]=2;
    for(int i=4;i<=22;i++)
        b[i]=(i-1)*(b[i-1]+b[i-2]);
        int n,d=1;
    while(~scanf("%d",&n),n)
    {
        printf("Case [%d]: ",d++);
        if(n==1)
            printf("100.00%%.\n");
        else
        {
            printf("%.2lf%%.\n",100*b[n]/a[n]);
        }
    }
}