把N封军事情报装在N个信封时,他居然全部都装错了信封。不管你信不信,反正我是信了,现求所有情报都装错信封共有多少种可能?c++解决
时间: 2024-04-11 16:30:42 浏览: 31
这是一个经典的错排问题,可以使用动态规划来解决。假设有n个情报和n个信封,我们要求所有情报都装错信封的可能性数量。
首先,我们考虑第一个情报,有两种情况:
1. 第一个情报装在第一个信封里,此时剩下的n-1个情报都装错了信封。
2. 第一个情报不装在第一个信封里,此时我们有两种选择:
a. 第一个情报装在某个其他的信封里,然后将该信封与第一个信封交换,此时问题转化为剩下的n-2个情报都装错了信封。
b. 第一个情报装在某个其他的信封里,然后将该信封与第一个信封之外的任意一个信封交换,此时问题转化为剩下的n-1个情报都装错了信封。
综上所述,我们可以得到递推公式:
dp[i] = (i-1) * (dp[i-1] + dp[i-2])
其中dp[i]表示有i个情报和i个信封时所有情报都装错信封的可能性数量。初始条件为dp[1] = 0, dp[2] = 1。
以下是C++代码实现:
```cpp
#include <iostream>
#include <vector>
int wrongEnvelopes(int n) {
if (n <= 2) {
return n - 1;
}
std::vector<int> dp(n + 1, 0);
dp[2] = 1;
for (int i = 3; i <= n; ++i) {
dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]);
}
return dp[n];
}
int main() {
int n = 0;
std::cout << "请输入情报和信封的数量:";
std::cin >> n;
int result = wrongEnvelopes(n);
std::cout << "所有情报都装错信封的可能性数量为:" << result << std::endl;
return 0;
}
```
希望对你有所帮助!
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![.rar](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)