c/c++语言开发共享错排公式浅谈(推导+应用)

给出一个已经排好的长度为n的数列,问全部排错一共有多少排法? 典型利用错排公式去解决问题, (搜一下)我们不难知道错排公式递推式为 $$ D(n)=(n 1)(D(n 1)+D(n 2)) $$ 特殊地, D(1) = 0, D(2) = 1. 进一步的化简即可得出 $$ D(n) = n! [( …

给出一个已经排好的长度为n的数列,问全部排错一共有多少排法?

典型利用错排公式去解决问题,

(搜一下)我们不难知道错排公式递推式为
[ d(n)=(n-1)(d(n-1)+d(n-2)) ]
特殊地,d(1) = 0, d(2) = 1.

进一步的化简即可得出
[ d(n) = n! [(-1)^2/2! + … + (-1)^{(n-1)}/(n-1)!+(-1)^n/n!] ]

推导

首先先来解释一下递推公式(分布乘法):

假设这组数列中有两个数a,b以及他们原来的位置(a),(b);

现在将a,b单独取出来看;错排公式浅谈(推导+应用)

第一步错排a:去除最初存在的位置还剩下n-1个位置满足a错排的要求,即n-1

错排公式浅谈(推导+应用)

第二步排b:这里有两种情况:

​ 1、b在a位置上:这里只有1种剩下的n-2项再进行上述的错排,即1 * d(n-2)

错排公式浅谈(推导+应用)

​ 2、b不在a位置上:这里相当于n-1项再进行上述的错排,即d(n-1)

错排公式浅谈(推导+应用)

综上即可得出递推公式
[ d(n)=(n-1)(d(n-1)+d(n-2)) ]
之后进行整理:
[ d(n)=n*d(n-1)+n*d(n-2)-d(n-1)-d(n-2) ]
递推可得
[ d(n)-n*d(n-1)=-[d(n-1)-(n-1)*d(n-2)]················1项 ]

[ d(n-1)-(n-1)d(n-2)=-[d(n-2)-(n-2)*d(n-3)]·········2项 ]

[ d(n-2)-(n-2)d(n-3)=-[d(n-3)-(n-3)*d(n-4)]·········3项 ]

[ d(n-3)-(n-3)d(n-4)=-[d(n-4)-(n-4)*d(n-5)]·········4项 ]

[ ······ ]

[ d(3)-3*d(2)=-[d(2)-2*d(1)]······························n-2项 ]

同时设d(n)=n!*nn

错项相消得
[ n(n)-n(1)=1/2!-1/3!+1/4!+······+(-1)^{(n-1)}/(n-1)!+(-1)^n/(n)! ]
移项进一步整理(特殊的n(1)=0,n(2)=0)即可得出
[ d(n) = n! [(-1)^2/2! + … + (-1)^{(n-1)}/(n-1)!+(-1)^n/n!] ]

应用

(懒得复制,上链接)

t1、hdu 2048 神、上帝以及老天爷

要计算概率=全不中奖组合数/所有组合数;

全不中奖组合数采用上面推导的错排公式即可求解

代码样例

#include <bits/stdc++.h> using namespace std;  int main() {     long long f[21]= {0};     f[1]=0;     f[2]=1;     for(int i=3; i<21; i++)         f[i]=(i-1)*(f[i-1]+f[i-2]);     int t,n;     cin >> t;     for(int i=0; i < t; i++)     {         cin >> n;         long long sum=1;         for(int j=2; j<=n; j++)                 sum*=j;         double b=100.0*f[n]/sum;         printf("%.2f%%n",b);        }     return 0; }

t2、hdu 2049 不容易系列之(4)——考新郎

这道题先用排列组合计算出所有m个找错新娘的新郎的组合数,之后乘以利用错排公式计算出的数据;

代码样例

#include <bits/stdc++.h> using namespace std; #define maxn 21  long long ci(int m,int n) {         long long sum1=1,sum2=1;         for(int j=2; j <= m; j++)         sum1*=j;         for(int j=n; j > n-m; j--)         sum2*=j;         return sum2/sum1; }  int main() {     long long f[maxn]={0};     f[1]=0;     f[2]=1;     for(int i=3; i < maxn; i++)         f[i]=(i-1)*(f[i-1]+f[i-2]);     int c;     cin >> c;     for(int i=1; i <= c; i++)     {         int n,m;         cin >> n >> m;         printf("%lldn",ci(m,n)*f[m]);           }     return 0; }
www.ctvol.com true Article c/c++语言开发共享错排公式浅谈(推导+应用)

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址:https://www.ctvol.com/c-cdevelopment/605909.html

(0)
上一篇 2021年5月13日 下午3:16
下一篇 2021年5月13日 下午3:22

精彩推荐