信息学奥赛一本通 1315：【例4.5】集合的划分

【题目链接】

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

【题目考点】

1. 递归/递推

2. 第二类斯特林数

【解题思路】

本题为求第二类斯特林数。
该问题可以描述为：将n个不相同的球放入k个相同的盒子，没有空盒子，求方案数。

解法1： 递推

• 递推状态：s[i][j]表示将i个不相同的球放入j个盒子的方案数
• 递推关系：
  (1) 将前i-1个球放入j个盒子，没有空盒，有s[i-1][j]种情况，每种情况下，第i个球可以放入j个盒子中的任意一个，有j*s[i-1][j]种情况。
  (2) i-1个球放入j-1个盒子，留下1个空盒给第i个球，有s[i-1][j-1]种情况
  所以将i个不相同的球放入j个盒子的方案数为s[i][j] = s[i-1][j-1] + j*s[i-1][j]
• 初始状态：
  (1) i个球放进j个盒子，当盒子数大于球数时，一定存在空盒，不存在摆放方案。所以一定有i >= j
  (2) i个球放进1个盒子，只有1种方案 s[i][1] = 1

2. 递归求解

• 递归问题：求将i个不相同的球放入j个盒子的方案数，记为s(i, j)
• 递归关系：要想将i个不相同的球放入j个盒子，有以下两种放法：
  (1) 先将前i-1个球放入j个盒子，没有空盒，有s(i-1, j)种情况，每种情况下，第i个球可以放入j个盒子中的任意一个，共有j*s(i-1, j)种情况。
  (2) 将i-1个球放入j-1个盒子，留下1个空盒给第i个球，共有s(i-1, j-1)种情况 。
• 递归出口：
  (1) i个球放进j个盒子，当盒子数大于球数时，一定存在空盒，不存在摆放方案。所以当i < j时，方案数s(i, j)为0。
  (2) i个球放进1个盒子，只有1种方案 s(i, 1)为1

注意：结果会很大，要设成long long类型。

【题解代码】

解法1： 递推

#include<bits/stdc++.h> using namespace std; long long s[40][40];//s[i][j]:将i个球装j个盒子的情况数。 int main() {int n, k; cin >> n >> k;for(int i = 1; i <= n; ++i)//球数 for(int j = 1; j <= i && j <= k; ++j)//盒子数，不会比球数多 {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个不相同的球放入j个盒子的方案数 {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个球装j个盒子的情况数。 long long stirling(int i, int j)//求将i个不相同的球放入j个盒子的方案数 {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; }

总结

以上是生活随笔为你收集整理的信息学奥赛一本通 1315：【例4.5】集合的划分的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。