現(xiàn)在做到的兩道有關(guān)于錯(cuò)排的題目有：
2048：http://acm.hdu.edu.cn/showproblem.php?pid=2048
神、上帝以及老天爺
做這道題剛開始沒(méi)有什么頭緒，后來(lái)上網(wǎng)查了一下才發(fā)現(xiàn)原來(lái)有一個(gè)錯(cuò)排公式，也就是元素都不在對(duì)應(yīng)原來(lái)位置的方法數(shù)。公式為：f(n) = (n-1) [f(n-2) + f(n-1)]
推導(dǎo)過(guò)程為：
第一步：假如一共有n個(gè)元素，那么如果把第n個(gè)元素放在某一個(gè)位置k，一共有n-1種方法；
第二步：放編號(hào)為k的元素有兩種情況：(1)如果把它放到位置n，那么除了n和k元素外的n-2個(gè)元素一共有f(n-2)種方法。(2)如果不把它放到位置n，那么對(duì)于剩下的n-1個(gè)元素有f(n-1)種方法。
綜上所述，錯(cuò)排公式為:f(n) = (n-1) f(n-2) + (n-1)f(n-1)=(n-1) [f(n-2) + f(n-1)]
有了錯(cuò)排公式，這道題就很容易解決了，總的排列方法數(shù)有n的階乘個(gè)，而全部錯(cuò)排的方法數(shù)有?(n-1) [f(n-2) + f(n-1)]個(gè)，最后直接把錯(cuò)排方法數(shù)除以總的排列數(shù)，然后注意輸出格式就可以了。
解題代碼如下：
#include<stdio.h>
int main()
{?
int m;
scanf("%d",&m);
while(m--)
{
long long a[100],sum=1;
int i,j,n;
scanf("%d",&n);
a[1]=0;
a[2]=1;
if(n>2)
{
for(i=3;i<=n;i++)
{
a[i]=(i-1)*((a[i-1]+a[i-2]));
}
}
for(i=1;i<=n;i++)
{
sum=sum*i;
}
printf("%.2lf%%\n",(double)a[n]/sum*100);
}
return 0;
}? ? ? ? ?
還有道題目：http://acm.hdu.edu.cn/showproblem.php?pid=2049
不容易系列之(4)——考新郎
這道題和上面類似，也用到錯(cuò)排公式，不同的是他不一定需要把全部實(shí)例錯(cuò)排，在給出總共m對(duì)夫婦后要求指定其中n個(gè)新郎找錯(cuò)新娘的方法數(shù)。解題思路是先用數(shù)學(xué)的排列組合知識(shí)求出從n對(duì)夫婦中隨機(jī)挑出的(m-n)個(gè)新郎和新娘配對(duì)成功的方法數(shù)，即,然后求n個(gè)新郎沒(méi)有和新娘配對(duì)成功的方法數(shù)，即a[i]=(i-1)*((a[i-1]+a[i-2]))，最后兩個(gè)數(shù)相乘便可以得到結(jié)果。
解題代碼如下:
#include<stdio.h>
int main()
{?
int k;
scanf("%d",&k);
while(k--)
{
long long a[25];
long long sum1=1,sum2=1,p,i;
int m,n;
scanf("%d%d",&m,&n);
a[1]=0;
a[2]=1;
if(n>2)
{
for(i=3;i<=n;i++)
{
a[i]=(i-1)*((a[i-1]+a[i-2]));
}
}
if(m==n)
{
printf("%lld\n",a[n]);
}
else
{
p=m;
for(i=1;i<=m-n;i++)
{
sum1=sum1*p;
p=p-1;
}
for(i=1;i<=m-n;i++)
{
sum2=sum2*i;
}
printf("%lld\n",sum1/sum2*a[n]);
}
}
return 0;
}?
通過(guò)這道題除了學(xué)習(xí)了重要的錯(cuò)排公式之外，還要注意在寫這種題時(shí)要把變量類型設(shè)置為long long型，以免數(shù)值太大超過(guò)int的范圍！
