程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDN2048(遞推之錯排列)

HDN2048(遞推之錯排列)

編輯:關於C++

神、上帝以及老天爺

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 26725 Accepted Submission(s): 11121



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

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

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

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

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

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

Input 輸入數據的第一行是一個整數C,表示測試實例的個數,然後是C 行數據,每行包含一個整數n(1

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


Sample Input
1
2

Sample Output
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;



 


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved