描述 某人写了N封信,用去N个信封,结果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况。可用下面公式(错位排列的递推公式): 基本形式:D(1)=0; D(2)=1 递归形式:D(n)=(n-1)*( D(n-1)+D(n-2)) 输入描述 一个正整数N,N<13。 输出描述 所有的信都装错信封的不同情况数。 C++递归完成
时间: 2024-02-13 18:05:30 浏览: 32
好的,以下是使用C++语言实现的递归方式来求解D(n)的代码:
```cpp
#include <iostream>
using namespace std;
int D(int n) {
if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
} else {
return (n-1) * (D(n-1) + D(n-2));
}
}
int main() {
int n;
cin >> n;
cout << D(n) << endl;
return 0;
}
```
首先定义一个递归函数D(n)来求解D(n),当n等于1时返回0,当n等于2时返回1,否则使用递推公式D(n) = (n-1) * (D(n-1) + D(n-2))来递归求解D(n)。
在main函数中读入n,调用D(n)函数求解D(n)并输出结果即可。
需要注意的是,由于递推公式的复杂度为O(n),因此n不能太大,题目中规定n<13,所以可以使用递归方式求解。
相关问题
小民同学写了n封信和n个信封,如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。
这是一个经典的错排问题。
设将第i封信装错的情形为Ai,则共有n种不同的情形。显然,所有信都被装错,当且仅当每一封信都被装到了一封与其编号不同的信封里,即要求每个Ai中的元素都不等于i本身。
考虑计算所有的情形中,符合要求的情形数T。根据容斥原理,有:
$T = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \binom{n}{3}(n-3)! + \cdots + (-1)^n\binom{n}{n}(0)!$
其中,$\binom{n}{k}$表示从n个元素中选择k个元素的组合数,$(n-k)!$表示剩下的n-k个元素的全排列数,最后一项为0,因为没有元素可选择。
将上面的式子化简,得到:
$T = \sum_{i=0}^n (-1)^i \binom{n}{i}(n-i)!$
这是一个经典的错排公式,也被称为第二类斯特林数定理,记作$!n$:
$!n = \sum_{i=0}^n (-1)^i \binom{n}{i}(n-i)!$
所以,所有的信都装错信封,共有$!n$种不同情况。
小民同学写了n封信和n个信封,如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。用c++语言写出程序
解题思路:
根据错排公式,对于n个元素的错排,有D(n)=(n-1)*(D(n-1)+D(n-2)),其中D(0)=1, D(1)=0
对于本题,n封信和n个信封一一对应,因此可以直接套用错排公式即可。
代码如下:
```c
#include <stdio.h>
int main()
{
int n;
printf("请输入信封数量:");
scanf("%d", &n);
int dp[100];
dp[0] = 1;
dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = (i - 1) * (dp[i-1] + dp[i-2]);
}
printf("所有的信都装错信封共有 %d 种不同情况。\n", dp[n]);
return 0;
}
```
运行结果:
请输入信封数量:3
所有的信都装错信封共有 2 种不同情况。