HDU2049神、上帝以及老天爷题解及错排问题

mathjax: true

做到这道题的时候没有搜到讲得比较好的题解(主要原因是这题太简单,而我太弱不会写

我正在写的这篇讲得也不好(逃,而且这道题所考察的错排问题也是我的盲点,于是赶紧上网搜索了一下,做完了题,简略地写个题解复习一下

言归正传,想要做这道题,要先了解”错排问题”

问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法?

这个问题推广一下,就是错排问题,是组合数学中的问题之一。考虑一个有n个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n)。 研究一个排列错排个数的问题,叫做错排问题或称为更列问题。

错排问题最早被尼古拉·伯努利和欧拉研究,因此历史上也称为伯努利-欧拉的装错信封的问题。这个问题有许多具体的版本,如在写信时将n封信装到n个不同的信封里,有多少种全部装错信封的情况?又比如四人各写一张贺年卡互相赠送,有多少种赠送方法?自己写的贺年卡不能送给自己,所以也是典型的错排问题。

以上摘自百度百科

然后这个问题怎么解呢?其实百度百科上已经有详细的证明了(但是我没学会,所以就讲一下递推式的推导,对于这道题来说已经完全够用了。
(以下参考自百度百科)

显然,D(1) = 0(因为根本没法错),D(2) = 1。所以可以开始考虑n大于等于3的情况。那么我们设第n个元素放在了第k位(哪个元素都无所谓,就有两种情况

  • 第k个元素放在第n位,也就是k,n互换,即他们两个已经完成错排了,那么又显然,问题与这两个元素无关了,变成了剩下的n-2个元素错排,也就是D(n-2)

  • 第k个元素没放在第n位,再显然问题就变成了包括第k个元素在内的剩下(n-1)个元素的错排。即为D(n-1)

除第n个元素外每个元素都有D(n-1)+d(n-2)种放法,所以总放法

D(n) = n-1*(D(n-1)+D(n-2))

错排问题还有通项公式,大家可以自行学习我说过我不会

掌握了这个,本题就很简单了本来就很简单,只需要算出错排数D(n)和总排列n!,再除一下弄成百分数就好了

(有一个小坑,正常人都能看出来,会爆int

上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<cstdio>
#include<iostream>
#include<cmath>
const int MAXN = 21;
long long d[MAXN];
long long j[MAXN];
int main()
{
d[1] = 0;//没办法错
d[2] = 1;//只有互换
for(int i = 3;i <= 20;i ++)
{
d[i] = (i-1)*(d[i-1]+d[i-2]);
}
j[0] = 1;
for(int i = 1;i <= 20;i ++)
j[i] = j[i-1] * i;
int n;
scanf("%d",&n);
for(int i = 1;i <= n;i ++)
{
int t;
scanf("%d",&t);
double ans = double(d[t])*100/double(j[t]);
printf("%.2f%\n",ans);
}
return 0;
}