錯排問題
一個寢室有四個人，過節時，每個人都會送出一封賀卡，假如一個盒子裡有四封賀卡，寢室的每個成員都要拿出一封，但是肯定不能拿自己寫的賀卡，如果每個人拿到的是別人送的賀卡，問這種情況有多少種？
這就是典型的錯排問題。
先給出公式：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);
}
}
