首页 > 代码库 > 配对问题
配对问题
题目描述：
某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况。
基本形式：D[1]=0;d[2]=1
递归式：d[n]= (n-1)*( d[n-1] + d[n-2])
输入样例：
7
输出样例：
1854
代码如下：
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int xf(int x)
{
if(x==1)return 0;
if(x==2)return 1;
return (x-1)*(xf(x-1)+xf(x-2));
}
int main()
{
int n;
scanf("%d",&n);
cout<<xf(n);
return 0;
}
此类问题为配对问题，还可以这样问n个战士有自己固定的枪,问没有一个人拿对自己枪的情况；
接下来进行一下扩展：
错排公式：
问题： 十本不同的书放在书架上。现重新摆放，使每本书都不在原来放的位置。有几种摆法？
这个问题推广一下，就是错排问题，是组合数学中的问题之一。考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n)。 研究一个排列错排个数的问题，叫做错排问题或称为更列问题。
递推的推导错排公式
D(n) = (n-1) [D(n-2) + D(n-1)]
特殊地，D(1) = 0, D(2) = 1；关于推导 自己百度吧....
配对问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。