神、上帝以及老天爷
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/32768 K (Java/Others)
Problem Description
HDU 2006'10 ACM contest的颁奖晚会隆重开始了!
为了活跃气氛,组织者举行了一个别开生面、奖品丰厚的抽奖活动,这个活动的具体要求是这样的:
首先,所有参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中;
然后,待所有字条加入完毕,每人从箱中取一个字条;
最后,如果取得的字条上写的就是自己的名字,那么“恭喜你,中奖了!”
大家可以想象一下当时的气氛之热烈,毕竟中奖者的奖品是大家梦寐以求的Twins签名照呀!不过,正如所有试图设计的喜剧往往以悲剧结尾,这次抽奖活动最后竟然没有一个人中奖!
我的神、上帝以及老天爷呀,怎么会这样呢?
不过,先不要激动,现在问题来了,你能计算一下发生这种情况的概率吗?
不会算?难道你也想以悲剧结尾?!
Input
输入数据的第一行是一个整数C,表示测试实例的个数,然后是C 行数据,每行包含一个整数n(1<n<=20),表示参加抽奖的人数。
Output
对于每个测试实例,请输出发生这种情况的百分比,每个实例的输出占一行, 结果保留两位小数(四舍五入),具体格式请参照sample output。
Sample Input
Sample Output
思路:
1. N张字条的所有可能排列自然是N!(分母)。
现在的问题就是求N张字条的错排数f(N)(分子)。
首先我们考虑,如果前面N-1个人拿的都不是自己的票,即前N-1个人满足错排,现在又来了一个人,他手里拿的是自己的票。只要他把自己的票与其他N-1个人中的任意一个交换,就可以满足N个人的错排。这时有(N-1)*f(N-1)种方法。
Besides,我们考虑,如果前N-1个人不满足错排,而第N个人把自己的票与其中一个人交换后恰好满足错排。
这种情况发生在原先N-1人中,N-2个人满足错排,有且仅有一个人拿的是自己的票,而第N个人恰好与他做了交换,这时候就满足了错排。
又因为前N-1个人中,每个人都有机会拿着自己的票。所以有N-1种交换的可能。故这时有(N-1)*f(N-2)种方法。
综上所述:f(N)=(N-1)*[f(N-1)+f(N-2)]
2. 另一种推导思路是先通过容斥定理直接计算出错排数f(n)=n!(1/2!-1/3!+…..+((-1)^n)/n!)
所以f(n)/n!-f(n-1)/(n-1)!=((-1)^n)/n!
两边同时乘上n!有f(n)-n*f(n-1)=(-1)^n
所以f(n-1)-(n-1)*f(n-2)=(-1)^(n-1)=(-1)*[f(n)-n*f(n-1)]
化简得f(n)=(n-1)*[f(n-1)+f(n-2)]
3. 通过错位排列数的简化公式来计算(参考维基百科)
完整代码:
/*0ms,224KB*/
#include<cstdio>
#include<cmath>
const double e = exp(1.0);
double p[21];
int main()
{
double temp = 1.0;
int t, n, i;
for (i = 2; i <= 20; ++i)
{
temp *= i;
p[i] = round(temp / e) / temp;
}
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
printf("%.2f%%\n", p[n] * 100.0);
}
return 0;
}
分享到:
相关推荐
杭电ACM课件2014版之 (HDUACM201403版_04)递推求解
HDUACM2010版03递推求解.ppt
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 (lecture_...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
蟠桃记 1 折线分割平面 2 不容易系列之一 2 骨牌铺方格 3 不容易系列之(3)—— LELE的RPG难题 3 Children’s Queue 3 献给杭电五十周年校庆的礼物 3 ...神、上帝以及老天爷 3 不容易系列之(4)——考新郎 3
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦