第二類斯特林(Stirling)數

問題描述:

組合數學中一個典型的問題是：把從1到n标号的n個球放到k個無差別的盒子裡，要求每個盒子裡至少有一個小球，問不同的放法數量。例如，如果用A、B、C、D分别表示4個球，要分成兩組（即放入無差別的盒子裡），其方法有7種： {A,B},{C,D} {A,C},{B,D} {A,D},{B,C} {A},{B,C,D} {B},{A,C,D} {C},{A,B,D} {D},{A,B,C} 　　這個數量可以用第二類斯特林 (Stirling) 數來計算，表示為S(n,k)，S(4,2)=7。第二類斯特林 (Stirling) 數也是計算機科學應用中很常見的公式。它有如下的遞推公式： 整數參數n≥k≥0，且初始條件滿足 式中 是Knuth推薦的第二類斯特林數的表示方式。 本題要求計算第二類斯特林數。（擴充：感興趣的同學可以再看看相關的Bell數，以及第一類斯特林數） 輸入： 參數n,k(n≥k≥0) 輸出： 對應的第二類斯特林數值 樣例輸入： 4□2↵ 樣例輸出： 7↵

參考代碼(java實作)：

1. import java.util.Scanner; 
2. public class Stirling{ 
3.     public static void main(String[] args) 
4.     { 
5.         Scanner cin; int n,k; 
6.         cin=new Scanner(System.in); 
7.         n=cin.nextInt(); k=cin.nextInt(); 
8.         System.out.println(Stirling(n,k)); 
9.     } 
10.     public static int Stirling(int n, int k) 
11.     { 
12.         if(n==1 && k==0) return 1;    
13.         else if( k==1 || n==k ) return 1;    
14.         else return Stirling(n-1, k)*k+Stirling(n-1, k-1); 
15.     } 
16. } 

轉載于:https://blog.51cto.com/pengjh/568221