首页 > 代码库 > 配对问题

配对问题

题目描述:

某人写了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;关于推导 自己百度吧....

配对问题