错排原理的应用
错排原理的应用一：
HDOJ2048神、上帝以及老天爷
题目链接地址：http://acm.hdu.edu.cn/showproblem.php?pid=2048
问题分析：
这就是一道典型的错排原理的应用：
N张票的所有排列可能自然是Ann = N!种排列方式
N张票N个人的错排情况：
f(n) = (i - 1) * [f(n - 1) + f(n - 2)]
/*
N张票的所有排列可能自然是Ann = N!种排列方式
N张票的所有错排情况是:(N-1)*(f[N-1]+f[N-2])
*/
#include
using namespace std;
int main(){
__int64 error[21],ticket[21];
int i,nCase,n;
char c='%';
error[1]=0; //1个人的错排情况
error[2]=1; //2个人的错排情况
error[3]=2; //3个人的错排情况
ticket[1]=1; //1张票的排列方式
ticket[2]=2; //2张票的排列方式
ticket[3]=6; //3张票的排列方式
for(i=4;i<21;i++){
ticket[i]=i*ticket[i-1];
error[i]=(i-1)*(error[i-1]+error[i-2]);
}
cin>>nCase;
while(nCase--){
cin>>n;
printf("%.2f%c\n",(double)error[n]*100/ticket[n],c);
}
return 0;
}
错排原理的应用二：
HDOJ2049不容易系列之(4)——考新郎
题目链接地址：http://acm.hdu.edu.cn/showproblem.php?pid=2049
问题分析：
此题目就是先求从N个新郎中找出M个冤大头。方法就不用多讲了，就是求组合Cmn
然后就再利用错排公式
#include
using namespace std;
//计算 n!/r!*(n-r)!
__int64 C(int n,int r){
int i;
__int64 nsum;
__int64 rsum;
__int64 n_rSum;
nsum=1;
rsum=1;
n_rSum=1;
if(n==0){
nsum=1;
}
if(r==0){
rsum=1;
}
if(n-r==0){
n_rSum=1;
}
for(i=1;i<=n;i++){
//cout<<"i="<
//printf("sum:%I64d\n",sum);
nsum=nsum*i;
}
for(i=1;i<=r;i++){
rsum=rsum*i;
}
for(i=1;i<=n-r;i++){
n_rSum=n_rSum*i;
}
return nsum/rsum*n_rSum;
}
int main(){
int nCase,n,m,i;
__int64 error[21];
error[1]=0;
error[2]=1;
error[3]=2;
for(i=4;i<21;i++){
error[i]=(i-1)*(error[i-1]+error[i-2]);
}
cin>>nCase;
while(nCase--){
cin>>n>>m;
printf("%I64d\n",C(n,m)*error[m]);
}
return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！