本文主要是介绍错排 问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
不容易系列之(4)——考新郎
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 17265 Accepted Submission(s): 6469
Problem Description 国庆期间,省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做"考新郎",具体的操作是这样的: 
首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个.最后,揭开盖头,如果找错了对象就要当众跪搓衣板...看来做新郎也不是容易的事情...假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.
Input 输入数据的第一行是一个整数C,表示测试实例的个数，然后是C行数据，每行包含两个整数N和M(1<M<=N<=20)。
Output 对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。
Sample Input 2
2 2
3 2
Sample Output 1
3
n各有序的元素应有n！种不同的排列。如若一个排列式的所有的元素都不在原来的位置上，则称这个排列为错排。任给一个n，求出1,2,……,n的错排个数Dn共有多少个。
递归关系式为：D(n)=(n-1)(D(n-1)+D(n-2))
D(1)=0,D(2)=1
可以得到:
错排公式为 f(n) = n![1-1/1!+1/2!-1/3!+……+(-1)^n*1/n!]
其中,n!=1*2*3*.....*n,
特别地,有0!=0,1!=1.
解释：
n 个不同元素的一个错排可由下述两个步骤完成：
第一步，“错排” 1 号元素（将 1 号元素排在第 2 至第 n 个位置之一），有 n - 1 种方法。
第二步，“错排”其余 n - 1 个元素，按如下顺序进行。视第一步的结果，若1号元素落在第 k 个位置，第二步就先把 k 号元素“错排”好， k 号元素的不同排法将导致两类不同的情况发生：
1、 k 号元素排在第1个位置，留下的 n - 2 个元素在与它们的编号集相等的位置集上“错排”，有 f(n -2) 种方法；
2、 k 号元素不排第 1 个位置，这时可将第 1 个位置“看成”第 k 个位置(也就是说本来准备放到k位置为元素，可以放到1位置中),于是形成（包括 k 号元素在内的） n - 1 个元素的“错排”，有 f(n - 1) 种方法。据加法原理，完成第二步共有 f(n - 2)+f(n - 1) 种方法。
根据乘法原理， n 个不同元素的错排种数
f(n) = (n-1)[f(n-2)+f(n-1)] (n>2) 。
可以分为两部，一个是求解Cmn，从N中挑选M个。另一个是全错位排列。公式是a[i]=(i-1)*(a[i-1]+a[i-2]。
#include<iostream>#include <cstdio>using namespace std; int main(){ int c; cin>>c; while(c>0) { c--; int n,m,i,j; __int64 c=1; __int64 x; cin>>n>>m; for(i=n,j=1;j<=m;i--,j++) { c*=i; c/=j; } __int64 a[21]; a[2]=1,a[3]=2; for(i=4;i<21;i++) { a[i]=(i-1)*(a[i-1]+a[i-2]); } x=c*a[m]; printf("%I64d\n", x); } return 0; }这篇关于错排 问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
