【題目鏈接】

ybt 1315：【例4.5】集合的劃分

【題目考點(diǎn)】

1. 遞歸/遞推

2. 第二類斯特林?jǐn)?shù)

【解題思路】

本題為求第二類斯特林?jǐn)?shù)。
該問(wèn)題可以描述為：將n個(gè)不相同的球放入k個(gè)相同的盒子，沒(méi)有空盒子，求方案數(shù)。

解法1： 遞推

• 遞推狀態(tài)：s[i][j]表示將i個(gè)不相同的球放入j個(gè)盒子的方案數(shù)
• 遞推關(guān)系：
  (1) 將前i-1個(gè)球放入j個(gè)盒子，沒(méi)有空盒，有s[i-1][j]種情況，每種情況下，第i個(gè)球可以放入j個(gè)盒子中的任意一個(gè)，有j*s[i-1][j]種情況。
  (2) i-1個(gè)球放入j-1個(gè)盒子，留下1個(gè)空盒給第i個(gè)球，有s[i-1][j-1]種情況
  所以將i個(gè)不相同的球放入j個(gè)盒子的方案數(shù)為s[i][j] = s[i-1][j-1] + j*s[i-1][j]
• 初始狀態(tài)：
  (1) i個(gè)球放進(jìn)j個(gè)盒子，當(dāng)盒子數(shù)大于球數(shù)時(shí)，一定存在空盒，不存在擺放方案。所以一定有i >= j
  (2) i個(gè)球放進(jìn)1個(gè)盒子，只有1種方案 s[i][1] = 1

2. 遞歸求解

• 遞歸問(wèn)題：求將i個(gè)不相同的球放入j個(gè)盒子的方案數(shù)，記為s(i, j)
• 遞歸關(guān)系：要想將i個(gè)不相同的球放入j個(gè)盒子，有以下兩種放法：
  (1) 先將前i-1個(gè)球放入j個(gè)盒子，沒(méi)有空盒，有s(i-1, j)種情況，每種情況下，第i個(gè)球可以放入j個(gè)盒子中的任意一個(gè)，共有j*s(i-1, j)種情況。
  (2) 將i-1個(gè)球放入j-1個(gè)盒子，留下1個(gè)空盒給第i個(gè)球，共有s(i-1, j-1)種情況 。
• 遞歸出口：
  (1) i個(gè)球放進(jìn)j個(gè)盒子，當(dāng)盒子數(shù)大于球數(shù)時(shí)，一定存在空盒，不存在擺放方案。所以當(dāng)i < j時(shí)，方案數(shù)s(i, j)為0。
  (2) i個(gè)球放進(jìn)1個(gè)盒子，只有1種方案 s(i, 1)為1

注意：結(jié)果會(huì)很大，要設(shè)成long long類型。

【題解代碼】

解法1： 遞推

#include<bits/stdc++.h> using namespace std; long long s[40][40];//s[i][j]:將i個(gè)球裝j個(gè)盒子的情況數(shù)。 int main() {int n, k; cin >> n >> k;for(int i = 1; i <= n; ++i)//球數(shù) for(int j = 1; j <= i && j <= k; ++j)//盒子數(shù)，不會(huì)比球數(shù)多 {if(j == 1)s[i][j] = 1;elses[i][j] = s[i-1][j-1] + j*s[i-1][j];}cout << s[n][k];return 0; }

解法2： 遞歸

#include<bits/stdc++.h> using namespace std; long long stirling(int i, int j)//求將i個(gè)不相同的球放入j個(gè)盒子的方案數(shù) {if(j > i)return 0;else if(j == 1)return 1;elsereturn stirling(i-1, j-1) + j*stirling(i-1, j); } int main() {int n, k; cin >> n >> k;cout << stirling(n, k);return 0; }

解法3： 記憶化遞歸

#include<bits/stdc++.h> using namespace std; long long s[40][40];//s[i][j]:將i個(gè)球裝j個(gè)盒子的情況數(shù)。 long long stirling(int i, int j)//求將i個(gè)不相同的球放入j個(gè)盒子的方案數(shù) {if(s[i][j] > 0)return s[i][j];if(j > i)return 0;else if(j == 1)return 1;elsereturn s[i][j] = stirling(i-1, j-1) + j*stirling(i-1, j); } int main() {int n, k; cin >> n >> k;cout << stirling(n, k);return 0; }

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通 1315：【例4.5】集合的划分的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。