hdu-2048，2048游戲

hdu-2048，2048游戲

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%     錯排，WA了好幾次因為沒有定義全局變量。 double way[25], sum;應該定義在前面，

/*全局變量是會自動初始化為0的，這是OJ中使用全局變量的一個目的；
全局數據存儲在靜態區，如果數據很大的話，棧會溢出，堆會慢，存在靜態區比較好。*/

 

代碼如下：

#include<stdio.h>

double way[25], sum;

double fac(int x)
{
int i;
double f=1;
for(i=1;i<=x;i++)
f=f*i;
return f;
}

int main()
{
int c,n,i,j;

while(scanf("%d",&c)!=EOF)
{
for(i=1;i<=c;i++)
{
scanf("%d",&n);
way[1]=0;
way[2]=1;
for(j=3;j<=n;j++)
{
way[j]=(way[j-1]+way[j-2])*(j-1);
}
sum=fac(n);
printf("%.2lf%%\n",(way[n]*100.0)/sum);
}
}
return 0;
}