题目链接:http://acm.hdu.edu.cn/listproblem.php?vol=11
解题思路:在做此题之前,我们先来了解一下错排公式:
当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用f(n)表示,那么f(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.
第一步,把第n个元素放在一个位置(除了第n位之外),比如位置k,一共有n-1种方法;
第二步,放编号为k的元素,这时有两种情况:1,把它放到位置n,那么,对于剩下的n-2个元素,就有f(n-2)种方法错排;2,不把它放到位置n,这时可以把第n个位置看成是“第k个位置”,所以,对于这n-1个元素,有f(n-1)种方法错排;
综上得到:
f(n)=(n-1)*[f(n-1)+f(n-2)],其中:f(1)=0,f(2)=1
本题代码如下:
#include <stdio.h>
int main ()
{
int i, c, n;
double a[21], b[21];
a[0] = 1;
for(i = 1; i < 21; i++)
a[i] = a[i-1] * i; //总的排列种数
b[1] = 0;
b[2] =1;
b[3] = 2;
for(i = 3; i < 21; i++)
b[i] = (i-1) * (b[i-1] + b[i-2]);//错排的种数
while (scanf("%d",&c) != EOF)
for(i = 0; i < c; i++)
{
scanf("%d",&n);
printf ("%.2lf%%\n",b[n]*100/a[n]);
}
return 0;
}
分享到:
相关推荐
HDOJ题目分类HDOJ题目分类HDOJ题目分类
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
hdoj上的资源,代码有注释,很不错的哦
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1003
ACM ICPC HDOJ1008
杭州电子科技大学hdoj1002,大整数相加问题
杭州电子科大HDOJ
c语言 最短路 是hdoj上的一个最短路问题,写的很牛
ACM ICPC HDOJ1000
hdoj解题代码,题目为1000-1050
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
codj,hdoj的源码(50-60题)
hdoj 2013 多校训练3标程+解题报告
HDOJ 源代码 包含几百道HDOJ题目源码
hdoj1005 Number Sequence, 杭州电子科技大学oj题目代码
杭电OJ(1000-1099) AC 代码
HDOJ使用指南——公开版.docHDOJ使用指南——公开版.docHDOJ使用指南——公开版.doc