CSU暑期集訓day04_遞推_動態規劃_抽獎概率

NO IMAGE

題目:

HDU 2006’10 ACM contest的頒獎晚會隆重開始了! 
為了活躍氣氛,組織者舉行了一個別開生面、獎品豐厚的抽獎活動,這個活動的具體要求是這樣的: 

首先,所有參加晚會的人員都將一張寫有自己名字的字條放入抽獎箱中; 
然後,待所有字條加入完畢,每人從箱中取一個字條; 
最後,如果取得的字條上寫的就是自己的名字,那麼“恭喜你,中獎了!” 

大家可以想象一下當時的氣氛之熱烈,畢竟中獎者的獎品是大家夢寐以求的Twins簽名照呀!不過,正如所有試圖設計的喜劇往往以悲劇結尾,這次抽獎活動最後竟然沒有一個人中獎! 

我的神、上帝以及老天爺呀,怎麼會這樣呢? 

不過,先不要激動,現在問題來了,你能計算一下發生這種情況的概率嗎? 

不會算?難道你也想以悲劇結尾?! 

Input

輸入資料的第一行是一個整數C,表示測試例項的個數,然後是C 行資料,每行包含一個整數n(1<n<=20),表示參加抽獎的人數。

Output

對於每個測試例項,請輸出發生這種情況的百分比,每個例項的輸出佔一行, 結果保留兩位小數(四捨五入),具體格式請參照sample output。

Sample Input

1
2

Sample Output

50.00%

解題思路:

    全都不中獎的概率是全都沒抽中的種類數量除以所有可能的抽獎情況種類數,所有可能的情況即n的階乘,難點在於求全不中獎這種情況的組合數。可以按下述分類:假如第一個人抽到了寫有第k個人名字的紙條(第k個人肯定也中不了獎了),按第k個人是否抽到第一個人的紙條來分類,如果第k個人恰好也抽到了第一個人的紙條,則對於剩下的n-2個人,這兩個人對他們沒有任何影響了,即f(n-2);如果第k個人沒抽到第一個人的紙條,而抽了另一個倒黴的人的紙條,也就是說在這種情況下第k個人除了不可能抽到第k個自己的那張紙條外,也不能抽到第一個人的紙條(否則就不屬於這種情況),而其他人則是不能抽到寫有自己名字的紙條,這樣看來包括第k個人在內的n-1個人去抽剩下的n-1張紙條的情況就完全相同了,就是f(n-1)。所以得到了轉換方程:f(n)=(n-1)(f(n-1) f(n-2))。

程式碼:

#include <iostream>
#include <cstdio>

using namespace std;

/*long long int fun(long long int x){
    if(x==2)return 1;
    if(x==3)return 2;
    return (x-1)*(fun(x-1) fun(x-2)); 
}*///也可以用遞迴來做

long long int fu(long long int y){
    if(y==1)return 1;
    return y*fu(y-1);
}

int main(){
    int c;
    scanf(“%d”,&c);    
    long long int f[21];
    f[2]=1;
    f[3]=2;
    for(int i=4;i<21;i ){
        f[i]=(i-1)*(f[i-1] f[i-2]);
    }
    while(c–){
        long long int n;
        scanf(“%lld”,&n);
        //double ans=fun(n)/double(f(n));//也可以用遞迴來做
        double ans=f[n]/double(fu(n));
        printf(“%.2lf%%\n”,ans*100);
    }
    system(“pause”);
    return 0;