HDU 2048 错排问题

本文主要是介绍HDU 2048 错排问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

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

题解：

n个人抽取的总情况为n！，所有人都没抽到自己名字的情况即错排数,存放在D[n]里，可用递推的方法求错排数D[n]。

显然D₁=0，D₂=1。当n≥3时，不妨设n排在了第k位，其中k≠n，也就是1≤k≤n-1。那么我们现在考虑第n位的情况。

• 当k排在第n位时，除了n和k以外还有n-2个数，其错排数为D_n-2。
• 当k不排在第n位时，那么将第n位重新考虑成一个新的“第k位”，这时的包括k在内的剩下n-1个数的每一种错排，都等价于只有n-1个数时的错排（只是其中的第k位会换成第n位）。其错排数为D_n-1。

所以当n排在第k位时共有D_n-2+D_n-1种错排方法，又k有从1到n-1共n-1种取法，我们可以得到：

D_n=(n-1)(D_n-1+D_n-2) ^[2]

概率就是D[n]*100.0/n!%

代码：

#include<stdio.h>
int main()
{int T;_int64 D[21];//存放错排数D[1]=0;D[2]=1;int i,n;scanf("%d",&T);while(T--){scanf("%d",&n);for(i=3;i<=n;i++){D[i]=(i-1)*(D[i-1]+D[i-2]);}double s=1.0;for(i=1;i<=n;i++){s*=i;}printf("%.2lf%%\n",D[n]*100.0/s);}return 0;
}

这篇关于HDU 2048 错排问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---