轉自

http://xuyemin520.is-programmer.com/posts/26265.html

題目：

就是給你N個房間，然后每個房間1把鑰匙，你最初手里沒有任何鑰匙，要靠破門而入！這里只有第一個房間不能破門進去，其他都可以，

給你房間數N，和最多能破門的個數，讓你求能全部把房間打開的概率！

題目分析：

又是是我的第一次啊！受教育了？有木有？這種題目是斯特林第一類數的應用，雖然很裸，但是很經典啊 ！

首先這題其實讓我們求的是給 N個元素，讓我們求K個環排列的 方法數。

斯特林第一類數的第推公式：

S（N，0）=0；

S（N，N）=1；

S（0，0）=0；

S（N，K）=S（N-1，K-1）+S（N-1，K）*（N-1）；

這個公式的意思是：

當前N-1個數構成K-1 個環的時候，加入第N個 ，N只能構成單環！---S（N-1，K-1）

如果N-1個數構成K個環的時候，加入第N個，N可以任意加入，N-1內的一個環里，所以是--（N-1）*S（N-1，K）

這個題目里，因為不能破壞第1個門：

所以

S（N，K）-S（N-1，K-1）才是能算構成K個環的方法數！就是去掉1自己成環的情況！

?

View Code #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=20;
long long f[25],stir[25][25];
int solve()
{
int i,j;
f[0]=1;
for(i=1;i<=maxn;i++)
f[i]=i*f[i-1];
//因為N有N！種排列順序，這作為總數
//計算概率
for(i=1;i<=maxn;i++)
stir[i][0]=0;
stir[1][1]=1;
for(i=1;i<=maxn;i++)
for(j=1;j<=i;j++)
{
if(i==j)
stir[i][j]=1;
else
stir[i][j]=stir[i-1][j-1]+(i-1)*stir[i-1][j];
}
for(i=1;i<=maxn;i++)
for(j=1;j<=maxn;j++)
if(stir[i][j]<0)
stir[i][j]=-stir[i][j];
return 0;
}
int main()
{
int cas,n,i,k;
long long sum;
solve();
scanf("%d",&cas);
while(cas--)
{
scanf("%d %d",&n,&k);
sum=0;
for(i=1;i<=k;i++)
sum+=stir[n][i]-stir[n-1][i-1];
printf("%.4lf\n",1.0*sum/f[n]);
//因為寫成printf("%.4lf\n",(double)sum/f[n]);
//run time error! 下次一定記好了！
}
return 0;
}

轉載于:https://www.cnblogs.com/nanke/archive/2011/09/07/2170290.html

總結

以上是生活随笔為你收集整理的斯特林数第一类数的应用 hdu3625的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。