hdu 神、上帝以及老天爺

神、上帝以及老天爺

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 7   Accepted Submission(s) : 5

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

HDU 2006'10 ACM contest的頒獎晚會隆重開始了！

為了活躍氣氛，組織者舉行了一個别開生面、獎品豐厚的抽獎活動，這個活動的具體要求是這樣的：

首先，所有參加晚會的人員都将一張寫有自己名字的字條放入抽獎箱中；

然後，待所有字條加入完畢，每人從箱中取一個字條；

最後，如果取得的字條上寫的就是自己的名字，那麼“恭喜你，中獎了！”

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

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

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

不會算？難道你也想以悲劇結尾？！

Input

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

Output

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

Sample Input

1
2
      

Sample Output

50.00%
      

Author

lcy 解題思路： 第一：算出滿足條件的情況。第二：算出總共的情況。第三：兩者相除。 具體方法：算滿足條件的情況：因為每個人拿的都不是自己的名字。是以算n個人拿錯名子的請況可以做以下考慮： 令n-1個人拿錯名字的情況是f(n-1)，第n-2個就是f(n-2), 第一種情況是：第n個人拿的是第n-1一個人中的一個，恰巧那個人拿的是第n個人的，這時f(n)=(n-1)*f(n-2)。 第二種情況是：第n個人拿的是第n-1中的一個人的，而他拿的那個人的名字的那個人，沒拿他的，這是f(n)=(n-1)*f(n-1); 綜上所述：f(n)=(n-1)*(f(n-1)+f(n-2)). 算總情況數，其實就是排列組合問題，總的情況為n*(n-1)*(n-2).........*1; 此題資料有點大對某些變量得用64位整數定義，即long long int

#include <iostream>

#include <iomanip>

using namespace std;

long long int fun(int n)

{

    long long int f;

    if(n==1)

    f=1;

    if(n>1)

    f=n*fun(n-1);

    return f;

}

long long int fu(int n)

{

    long long int k;

    if(n==2)

    k=1;

    if(n==3)

    k=2;

    if(n>3)

    k=(n-1)*(fu(n-1)+fu(n-2));

    return k;

}

int main()

{

    int n,m,i;

    double sum;

    cin>>m;

    for(i=0;i<m;i++)

    {

        cin>>n;

        sum=double(fu(n))/fun(n);

        sum*=100;

       cout<<setiosflags(ios::fixed)<<setprecision(2)<<sum;//注意輸出格式

       cout<<"%"<<endl;//别忘了%

    }

    return 0;

}