错排问题（Derangement）是一个经典的组合数学问题，描述的是将 \( n \) 个元素进行排列，使得没有一个元素出现在它原来的位置上。换句话说，错排问题要求所有元素都不在它们原来的位置上。
### 错排问题的公式
错排问题的公式可以通过递推关系来推导。设 \( D(n) \) 表示 \( n \) 个元素的错排数。错排数 \( D(n) \) 可以通过以下递推关系来计算：
\[ D(n) = (n - 1) \left( D(n - 1) + D(n - 2) \right) \]
其中，初始条件为：
\[ D(0) = 1 \]
\[ D(1) = 0 \]
### 错排数的递推关系解释
1. **D(0) = 1**: 没有元素时，错排数为1（空排列）。
2. **D(1) = 0**: 只有一个元素时，不可能有错排。
对于 \( n \geq 2 \) 的情况：
- 假设第一个元素放在第 \( k \) 个位置（\( k \neq 1 \)），那么我们有两种情况：
1. 第 \( k \) 个元素放在第一个位置，剩下的 \( n-2 \) 个元素进行错排，即 \( D(n-2) \)。
2. 第 \( k \) 个元素不放在第一个位置，剩下的 \( n-1 \) 个元素进行错排，即 \( D(n-1) \)。
由于 \( k \) 有 \( n-1 \) 种选择（因为 \( k \neq 1 \)），所以总的错排数为：
\[ D(n) = (n - 1) \left( D(n - 1) + D(n - 2) \right) \]
### 错排数的直接公式
错排数 \( D(n) \) 也可以通过以下公式直接计算：
\[ D(n) = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n \frac{1}{n!} \right) \]
这个公式是通过泰勒级数展开得到的，表示错排数与阶乘的关系。
### 错排概率
错排的概率 \( P(n) \) 是错排数 \( D(n) \) 与总排列数 \( n! \) 的比值：
\[ P(n) = \frac{D(n)}{n!} \]
### 示例
1. **n = 2**:
- 总排列数：\( 2! = 2 \)
- 错排数：\( D(2) = 1 \)
- 错排概率：\( P(2) = \frac{1}{2} = 0.5 \)
2. **n = 3**:
- 总排列数：\( 3! = 6 \)
- 错排数：\( D(3) = 2 \)
- 错排概率：\( P(3) = \frac{2}{6} = \frac{1}{3} \approx 0.3333 \)
### 代码实现
以下是计算错排数和错排概率的C语言代码：
```c
#include <stdio.h>
// 计算n的阶乘
long long factorial(int n) {
long long result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
// 计算n个元素的错排数
long long derangement(int n) {
if (n == 0) return 1;
if (n == 1) return 0;
long long D[n + 1];
D[0] = 1;
D[1] = 0;
for (int i = 2; i <= n; i++) {
D[i] = (i - 1) * (D[i - 1] + D[i - 2]);
}
return D[n];
}
// 计算错排的概率
double calculate_probability(int n) {
long long D_n = derangement(n);
long long n_factorial = factorial(n);
double probability = (double)D_n / n_factorial;
return probability;
}
int main() {
int C;
scanf("%d", &C);
for (int i = 0; i < C; i++) {
int N;
scanf("%d", &N);
double probability = calculate_probability(N);
double percentage = probability * 100;
printf("%.2f%%\n", percentage);
}
return 0;
}
```
这个代码会计算每组测试数据的错排概率，并将结果以百分比形式输出，保留两位小数。
