如何理解错排问题 小灰灰 2023-07-24 09:26 5阅读 0赞 ## 一、什么是错排问题 ## 举例： 十本不同的书放在书架，现重新摆放，使得每本书都不在原来的位置上，有几种摆法？ 一个人给十个同学写信，但他把所有的信都装错了信封，问共有多少种错误的方式？ 以上问题推广，就是错排问题。 一个n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的一个排列就称为原排列的一个错排。而研究一个排列的错排个数的问题，就称为错排问题（或称为更列问题）。 ## 二、错排公式 ## n个元素的错排数记为D(n) D(1)=0; D(2)=1; D(n)=D(n-1)(n-1)+D(n-2)(n-1) ## 三、错排公式的应用 ## **（1）HDU1465 装错信封事件** //n封信都装错了信封，且n的范围为[1,20] #include<iostream> using namespace std; int main(){ int n;//[1,20] long long a[21]={ 0}; a[1]=0;a[2]=1; for(int i=3;i<21;i++){ a[i]=a[i-1]*(i-1)+a[i-2]*(i-1);//错排公式的应用 } while(cin>>n){ cout<<a[n]<<endl; } } **（2）HDU2048 年会抽奖没人中奖的概率** //错排公式的应用--n张纸条和n个人刚刚好都不对应，n的范围[1,20] //概率：错排的方式总数/n张纸条的可能的排列总数 #include<iostream> #include<iomanip> using namespace std; __int64 jiechen(int n){ __int64 result=1; for(int i=n;i>0;i--){ result=result*i; } return result; } int main(){ int t; cin>>t; //错排公式 __int64 a[21]={ 0,0,1}; for(int i=3;i<=20;i++){ a[i]=a[i-1]*(i-1)+a[i-2]*(i-1); } while(t--){ int n;//人数[1,20] cin>>n; //计算n! __int64 m=jiechen(n); //概率 double x=(double)a[n]/(double)m; cout<<setiosflags(ios::fixed); cout<<setprecision(2)<<x*100<<"%"<<endl; } return 0; } **（3）HDU2049 考新郎问题** //一共有N对新婚夫妇,其中有M个新郎找错了新娘,发生这种情况一共有多少种可能. //思路：C(N,N-M)*错排M个元素的的D(M) #include<iostream> using namespace std; __int64 f(int n){ __int64 result=1; for(int i=n;i>=1;i--){ result=result*i; } return result; } int main(){ int t; cin>>t; __int64 a[21]={ 0,0,1}; for(int i=3;i<=20;i++){ //错排公式 a[i]=a[i-1]*(i-1)+a[i-2]*(i-1); } while(t--){ int n,m; cin>>n>>m;//n和m的范围[1,20],n对新婚夫妇，m对找错了; //C(n,c)的计算 int c=n-m; __int64 b=f(n)/(f(c)*f(n-c)); cout<<b*a[m]<<endl; } return 0; }
还没有评论，来说两句吧...