C++ 解题：n 个小球和盒子，错误存放方式计数
// C++ 解题：n 个小球和箱子，错误存方方式统计
// 有 n 号重色小球和相应 n 种重色的箱子，相同重色的小球和箱子是一套，假设所有的小球全都未放到对应的箱子中去，请问这种错误的存方方式一共有多少种？
//
// 输入描述
// 一行，一个整数 n，表示小球的个数（同时也是箱子的）（1<=n<=20）
//
// 输出描述
// 一行，一个整数，表示完全错误的存方方法数。
//
// 样例1
// 输入
// 5
// 输出
// 44
//
// 解题想路：
// 对于每个小球，都有 n 种选择放入箱子中，所以一共有 n^n 种存方方式。但是这种方式中，存在一些小球被放入了正确的箱子中，所以我们需要排除这些情况。
//
// 假设有 k 个小球被放入了正确的箱子中，那么剩余的 n-k 个小球一共有 (n-k)^(n-k) 种存方方式。我们需要计算出所有可能的 k 的取值，并将这些情况累加起来就可以。
//
// 具体实现步骤如下：
// 1. 读取输入的 n；
// 2. 定义一个变量 result，并初始化为 n^n；
// 3. 循直变量 i 从 1 到 n，表示被放入正确箱子的小球个数；
// 4. 将 result 减去 C(n, i) * (n-i)^(n-i)；
// 5. 输出 result。
//
// C(n, i) 表示从 n 个小球中选择 i 个小球的组合数，可以使用动态计算的方法进行计算。
//
// 以下是代码实现：
//
```cpp#include
// 计算组合数C(n, i)int combination(int n, int i) { int dp[21][21]; for (int j = 0; j <= n; j++) { dp[j][0] = 1; dp[j][j] = 1; } for (int j = 1; j <= n; j++) { for (int k = 1; k < j; k++) { dp[j][k] = dp[j-1][k-1] + dp[j-1][k]; } } return dp[n][i];}
int main() { int n; cin >> n; int result = 1; for (int i = 1; i <= n; i++) { result += combination(n, i) * (n-i)^(n-i); } cout << result << endl; return 0
原文地址: https://www.cveoy.top/t/topic/pXya 著作权归作者所有。请勿转载和采集!