问题描述
考虑一个n个数字的排列，使所有的数字都不在自己所对应序号的位置上，这样的一个排列就称为原排列的一个错排，现在给定一个数字n，求解所有可能的错排的个数。
分析
首先使用
D(n)
D
(
n
)
表示n个数字的错排数目，
D(n−1)
D
(
n
−
1
)
表示n-1个数字的全排列数目，以此类推，推导过程：
- 对于第
N
N
个位置的数字，首先选取一个位置
K
K
（任意的非的位置）放置，共有
(n−1)
(
n
−
1
)
种情况
- 然后考虑第
K
K
个位置的数字，如果
k
k
放在第个位置，那么相当于剩下的
(n−2)
(
n
−
2
)
个数字进行错排，即共有
D(n−2)
D
(
n
−
2
)
种情况,（
n
n
，都已经确定了位置），如果
k
k
不放在第个位置，那么就相当于
(n−1)
(
n
−
1
)
个数字进行错排，也就是
D(n−1)
D
(
n
−
1
)
，（这种情况，只有
n
n
的位置确定了）
综上，所有的情况就是：
这就是n个数字进行错排的递推公式，很多题目，例如SDUT2058，都考察到了这一点：
代码：
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
using namespace std;
long long int sav[25];
int n;
int main(){
sav[1]=0;
sav[2]=1;
for(int i=3; i<21; i++){
sav[i] = (i-1) * (sav[i-1] + sav[i-2]);
}
while(cin>>n){
cout<<sav[n]<<endl;
}
return 0;
}
以上~
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/116769.html
