Problem Description
HDU 2006'10 ACM contest的颁奖晚会隆重开始了!为了活跃气氛,组织者举行了一个别开生面、奖品丰厚的抽奖活动,这个活动的具体要求是这样的: 首先,所有参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中;然后,待所有字条加入完毕,每人从箱中取一个字条;最后,如果取得的字条上写的就是自己的名字,那么“恭喜你,中奖了!” 大家可以想象一下当时的气氛之热烈,毕竟中奖者的奖品是大家梦寐以求的Twins签名照呀!不过,正如所有试图设计的喜剧往往以悲剧结尾,这次抽奖活动最后竟然没有一个人中奖! 我的神、上帝以及老天爷呀,怎么会这样呢? 不过,先不要激动,现在问题来了,你能计算一下发生这种情况的概率吗? 不会算?难道你也想以悲剧结尾?!
Input
输入数据的第一行是一个整数C,表示测试实例的个数,然后是C 行数据,每行包含一个整数n(1<n<=20),< span="">表示参加抽奖的人数。</n<=20),<>
Output
对于每个测试实例,请输出发生这种情况的百分比,每个实例的输出占一行, 结果保留两位小数(四舍五入),具体格式请参照sample output。
Sample Input
1
2
Sample Output
50.00%
要解决这个问题,你应该要了解错排:
问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法? 这个问题推广一下,就是错排问题,是组合数学中的问题之一。考虑一个有n个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n)。 研究一个排列错排个数的问题,叫做错排问题或称为更列问题。 错排问题最早被尼古拉·伯努利和欧拉研究,因此历史上也称为伯努利-欧拉的装错信封的问题。这个问题有许多具体的版本,如在写信时将n封信装到n个不同的信封里,有多少种全部装错信封的情况?又比如四人各写一张贺年卡互相赠送,有多少种赠送方法?自己写的贺年卡不能送给自己,所以也是典型的错排问题。--百度搜索
解决题目问题只需要:n个人错排种类/n个人总排列种类(n!)
那么问题就变为n个人错排种类
核心代码:
num[i]=(i-1)*(num[i-1]+num[i-2]);//i个人错排种类数等于i-1个和i-2个人种类数和的i-1倍 |
---|
那么讨论一下错排问题的递推公式吧
假如说现在知道了i-1个人与i-2个人的错排种类数num[i-1]num[i-2],现在加入一个人x变为i个人。那么此时如何实现错排呢?我们从x考虑,如果错排,x可以拿除他自己以外i-1个人的名字,即有i-1种情况,那么现在假设x拿了i-1人中y的名字,此时y拿了x的名字,那么y的名字肯可能在x手上也可能不在,如果在x手上,此时剩下i-2个人全部错排,如果不在x手上,除y以外i-1个人错排(因为x不能拿y,理解的时候可以把x看做y,与其他i-2个人错排),这样就考虑完全了。
代码如下:
#include
#include
#include
using namespace std;
int main()
{
int c,i;
long long sum[30],num[30];
sum[1]=1;
num[0]=num[1]=0;num[2]=1;
for(i=2;i<=20;i++)
sum[i]=i*sum[i-1];
for(i=3;i<=20;i++)
num[i]=(i-1)*(num[i-1]+num[i-2]);
cin>>c;
while(c--)
{
int n;
cin>>n;
//注意长整型与百分号的输出格式
printf("%.2llf%%\n",(double)num[n]/sum[n]*100);
}
return 0;
}
那么扩充一下(Hdu 2049思想)
如果不是n个人完全错排呢?假如n个人中有m个错排有多少种情况呢?
m个错排意味着其余n-m个人已经确定自己拿自己的名字,其余m个人单独错排即
num[m]*Cnm(即n中抽取n-m个已经确定了的人,其他人错排)