前言： 首先这是一题解，但是重点最代码之后，有耐心的可以直接从代码后看。
上题目：n个人，每个人都有一件礼物想送给他人，他们决定把礼物混在一起，然后每个人随机拿走一件，问恰好有m个人拿到的礼物恰好是自己的概率是多少？ 输出结果四舍五入，保留8位小数，为了保证精度，我们用字符串作为返回类型。
输入：n,m (0<n<100, 0<=m<=n) 例如： n = 2，m = 1，输出：0.00000000； n = 99，m = 0，输出：0.36787944
上代码：
*******************************************************************************/
/* OS : 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 UTC 2013 GNU/Linux
* Compiler : g++ (GCC) 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)
* Encoding : UTF8
* Date :
* All Rights Reserved by yaolong.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/
//*
#include <stdio.h>
#include <iostream>
#include <string> using namespace std;
double jcf(int r){ //计算 1/r! ;
double res=1;
for(int i=1;i<=r;i++){ res*=i;
}
return 1/res; }
class Test {
public: static string calculate (int n,int m)
{
double r_=jcf(m);
double res=0;
for(int i=0;i<=n-m;i++){
if(i%2==1)
res-=jcf(i);
else{
res+=jcf(i);
}
}
res=res*r_;
string tmp;
res=res*100000000;
int tot=(int)(res+0.5);
int k=8;
while(k--){
tmp.insert(0,1,tot%10+'0');
tot/=10;
}
tmp.insert(0,1,'.');
tmp.insert(0,1,'0');
return tmp;
}
};
//start 提示：自动阅卷起始唯一标识，请勿删除或增加。
int main() {
cout<< Test::calculate(36,3)<<endl;
cout<< Test::calculate(12,6);
cout<<endl;
cout<<Test::calculate(99,0)<<endl;
}
//end //提示：自动阅卷结束唯一标识，请勿删除或增加。
本文将以此题引出并解释一下这种匹配问题。
比如 N个信封N封信，k个匹配正确的概率，方法等等。
还有各种变还说法，比如本题的 N个人N份礼物，k个正确的概率。
还有一堆新郎和新娘，k个人选对自己的新娘的组合数等的功能。
这种问题，都源于信封匹配啦。当然这种博文多的是，我也只是在前人的基础上去理解以及解释。
1.先看错位排列的问题。即k=0的情况。
m个朋友，0个人拿对自己的礼物。
我们假设编号从1 到 m,从1号开始拿礼物，这时候1号有m-1个选择，
假设 1号拿到k号的礼物,
1.k如果拿到1的礼物，那么问题就归结到m-2个人的问题，
2.如果k没有拿到1的礼物，则k可以看做是1（因为k不拿1的礼物），问题归结到m-1的问题。
即得到递推式子: A_m = (m-1)*(A_m-1 + A_m-2)用习惯的数列表示就是
A_n = (n-1)*(A_n-1 + A_n-2);
显然A_1 =0 ,A_2 =1(一个人的时候为0，二个人的时候是1.)
解这种数列的通向公式方法不算少，最基本的一个解法就是用高中的数列手段啦。
A_n -n* A_n-1 = - [ A_n-1 - (n-1) * A_n-2 ]
即有
[ A_n - n* A_n-1 ]/[ A_n-1 - (n-1) * A_n-2 ]=-1;
记B_n=[A_n- n* A_n-1 ,累乘一下，B_n=(-1)^(n-2) * B_2=(-1)^n (n>=2);
即有
A_n- n*A_n-1 = (-1)^n;
A_n / (-1)^n = - n * A_n-1 /(-1)^(n-1) +1;
记C_n= A_n / (-1)^n ,即解C_n = - n* C_n-1 +1;
求解这个数列，也是高中的数列方法了，C_n= f(n) *C_n-1 +C;
构造h(n)，使得f(n)=h(n-1)/h(n) ，之后转换成 h(n)*C_n = h(n-1)*C_n-1 +C*h(n) ,累加求解就可以了。
对于n显然构造的是 h(n)=1/n!;（为什么？我能说是经验吗？）
之后，这个累加过程我就不写了，最后给出华丽丽的公式：
A_n= n!*[1-1/1!+1/2!-1/3!+1/4!-…+(-1)^n*1/n!]
而全排列是n! ，所以概率则为 P(n)=A_n/n! =1-1/1!+1/2!-1/3!+1/4!-…+(-1)^n*1/n!
2.m个人拿对（m!=0）的时候
有了上一步的支持，这个就异常的简单，则C(n,m)*A_n-m 即可
即 F(n,m) = C(n,m)*(n-m)!*[1-1/1!+1/2!-1/3!+1/4!-…+(-1)^(n-m)*1/(n-m)!]
P(n,m) = F(n,m)/n!=(1/m! )*[1-1/1!+1/2!-1/3!+1/4!-…+(-1)^(n-m)*1/(n-m)!]
3.对应 英雄会的朋友的礼物，就是套用2的公式，so easy(之前我也看过其他博文写的这题，但是文字太多，看得有点烦。)