错排详解

错排问题

一个寝室有四个人，过节时，每个人都会送出一封贺卡，假如一个盒子里有四封贺卡，寝室的每个成员都要拿出一封，但是肯定不能拿自己写的贺卡，如果每个人拿到的是别人送的贺卡，问这种情况有多少种？

这就是典型的错排问题。

先给出公式：f(n) = (n-1)*(f(n-1) + f(n-2)).

分两步：

第一步：第一个人的贺卡放到2,3,4中的一个，此时有n-1种情况。

第二步：接到第一步，假如第一个人的贺卡放到了位置k（k当然不等于1了），那么先处理这第k个位置的贺卡，两种情况：①把第k个位置的贺卡放到第一个位置，那也就是说还有n-2个贺卡没排，这n-2个贺卡与第1个第k个位置的贺卡就没有关系了，那直接把这n-2个贺卡错排，有f(n-2)种情况；②那么会产生第二种情况，就是第k个位置的贺卡如果不放到第1个位置又该怎样？（我看别人写的很多不是很清楚）这时要转换一下观念，第k个位置的贺卡不是不能放到第一个位置吗，好，我这时就把第k个位置的贺卡放到第一个位置，然后对除第一个贺卡的剩下的n-1个贺卡错排，那错排后，第k个位置的贺卡肯定不在第一个位置了，这时不就满足了条件。

这时就可以总结出公式了：只有同时完成第一步和第二部才算完成一件事，

所以：公式如上

杭电 2048

[cpp]
#include<stdio.h>
int f(int n)
{
int i,sum=1;
for(i=1;i<=n;++i)
sum=sum*i ;
return sum;
}
main()
{
    int C,n,i,j,k;
    __int64 a[21],sum;
    scanf("%d",&C);
    for(i=0;i<C;++i)
    {
        scanf("%d",&n);
        sum=1;
        for(k=1;k<=n;++k)
        sum=sum*k;
        a[1]=0;
        a[2]=1;
        for(j=3;j<=n;++j)
        a[j]=(j-1)*(a[j-1]+a[j-2]);

        printf("%.2f%%\n",(a[n]*1.0)/sum*100);
    }
}

杭电 2049

[cpp]
#include<stdio.h>
main(){
    int n, m, i, k, j;
    __int64 str[21],sum;
    str[1] = 0;
    str[2] = 1;
    str[3] = 2;
    for(i=4; i<=20; i++){
        str[i]=(i-1)*(str[i-1]+str[i-2]);
    }
    scanf("%d", &k);
    while(k --){
        scanf("%d%d", &n, &m);
        sum = 1;
        i = 1;
        /*C(n, m)的排列*/
        while(i<=m){
             sum=sum*n/i;
             i ++;
             n --;
        }
        printf("%I64d\n", str[m]*sum);
    }
}

补充：软件开发 , C++ ,