错排列的概率–递推

现在的位置: 首页 > 综合 > 正文

错排列的概率–递推

2012年11月11日 ⁄ 综合 ⁄ 共 894字 ⁄ 字号小中大 ⁄ 评论关闭

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2048

N张字条的所有排列可能自然是A(N,N)= N!种排列方式
现在的问题就是N张字条的错排方式有几种。分两种情况讨论
①：如果前面N-1个人拿的都不是自己的字条，即前N-1个人满足错排，那么只要第N个人把自己的票与前面N-1个人中的任意一个交换，就可以满足N个人的错排。这时有f(N-1)种方法。

②：如果前N-1个人不满足错排，而第N个人把自己的字条与其中一个人交换后恰好满足错排。即在前面N-1人中，有N-2个人满足错排，有且只有一个人拿的是自己的字条，而第N个人恰好与他做了交换，这时候就满足了错排。这时有f(n-2)种方法

对于①，因为前N-1个人中，每个人都有机会与第N个人交换，所以有N-1种交换的可能。
对于②，因为前N-1个人中，每个人都有机会拿着自己的字条。所以也有N-1种交换的可能。

所以得错排递推公式
1.D[n] = (n-1)*(D[n-1]+D[n-2])

由于计算n!和D[n]数字会非常大，所以我们采用边做边除而不是先算D(n)，再除n!的方法。
1.已知D[n]=(n-1)(D[n-1]+D[n-2]);2.f[n]=D[n]/n!;则有D[n]=n!*f[n];3.代入可得f[n]=(n-1)(f[n-1]*(n-1)!+f[n-2]*(n-2)!)/n!; 4.即得到错排概率公式f[n]=(f[n-1](n-1)+f[n-2])/n;

代码如下：
#include <iostream><br />
#include <iomanip><br />
using namespace std;<br />
const int MAXN = 20;<br />
double f[MAXN];<br />
int main()<br />
{<br />
    int n,x;<br />
    f[1] = 0;<br />
    f[2] = 0.5;<br />
    for (int i = 3;i <= MAXN;i++)<br />
        f[i] = ((i-1)*f[i-1]+f[i-2]) / i;<br />
    cin >> n;<br />
    for (int i = 0;i < n;i++)<br />
    {<br />
        cin >> x;<br />
        cout << fixed << setprecision(2) << f[x] * 100 << '%' << endl;<br />
    }<br />
    return 0;<br />
}

【上篇】Red Hat Linux、rhel 和 Fedora Core 以及 Centos 区别与联系
【下篇】查看数据库表中的数据

作者: kuba

该日志由 kuba 于11年前发表在综合分类下，最后更新于 2012年11月11日.
转载请注明: 错排列的概率–递推 | 学步园 +复制链接

抱歉!评论已关闭.

学步园

错排列的概率–递推

作者: kuba

书签

最新文章New

本站推荐

返回首页