首页 > 代码库 > 斯特林数
斯特林数
一个经典的组合数学问题。求解方法:递推。
第一类斯特林数:n个数摆成m个环,有多少种方法?数各不相同。
s[i][j]表示i个数摆成j个环 的方法数目。
递推:1,摆第n+1个数时,如果前n个数摆成了m个环,那么要在环中插入一个数,总数目是s[n][m]*n;
2,如果前n个数摆成了m-1个环,方法数目是s[n][m-1].
综上:s[n+1][m]=s[n][m]*n+s[n][m-1].
这个过程和组合数公式:C[n][m]=C[n-1][n-1]+C[n-1][n] 类似。
第二类斯特林数:经典问题,n个不同的球放到m个相同的盒子里,每个盒子不为空。
和第一类很相似。
递推:1,放第n+1个球时,如果前n个球已经把m个盒子都填了,那么这个球有m中放法,S[n][m]*m;
2,如果前n个球只把n-1个盒子填了,那么这个球只有一种放法,S[n][m-1]*1.
HDU3625问题:有n个房间和n个对应的钥匙,每个房间放着一把钥匙,侦探要侦破案件,调查所有房间,他只能破门而入,1号房间的客人比较尊贵,不能破开1号门,给定数k,要求最多只能破开k个门,求侦探成功的概率。
开一个门就能开成环的所有门,破门次数对应环的个数,s[n][i];第一个房间不能破门进入,看作1号门自成一环,无法完成的情况就是s[n-1][i-1]种。
能进入的总情况数目:Σi~k s[n][i]-s[n-1][i-1]
所有情况数目和:n!
做除法
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn=25; 4 typedef unsigned long long ull; 5 ull s[maxn][maxn]; 6 void init() 7 { 8 s[0][0]=1; 9 for(int i=1;i<maxn;i++) 10 s[i][0]=0; 11 for(int i=1;i<21;i++) 12 for(int j=1;j<=i;j++) 13 s[i][j]=s[i-1][j]*(i-1)+s[i-1][j-1]; 14 } 15 int main() 16 { 17 init(); 18 int t,k,n; 19 cin>>t; 20 while(t--) 21 { 22 cin>>n>>k; 23 double fin=0; 24 for(int i=1;i<=k;i++) 25 fin=fin+s[n][i]-s[n-1][i-1]; 26 for(int i=1;i<=n;i++) 27 fin/=i; 28 printf("%.4f\n",fin); 29 } 30 return 0; 31 }
斯特林数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。