题目链接: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,全称为Happy DingO Online Judge,是一个在线编程竞赛平台,它为参赛者提供了大量编程题目进行练习和比赛,旨在提升编程技能和算法理解。HDOJ的题目分类是帮助用户...
【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...
【标题】"HDOJ 80题 Java"是一份专为Java程序员设计的在线编程挑战集合,源自杭州电子科技大学(HDOJ)的在线评测系统。这些题目旨在帮助Java开发者提升算法理解与编程能力,同时也为那些习惯于C++但希望在Java环境...
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
HDOJ1000.java HDOJ1001.java HDOJ1089.java HDOJ1090.java HDOJ1091.java HDOJ1092.java HDOJ1093.java HDOJ1094.java HDOJ1095.java HDOJ1108.java HDOJ1406.java HDOJ2001.java HDOJ2002.java HDOJ2003.java HDOJ...
hdoj1004,解题代码,答案代码,欢迎下载
离线版通常包含HDOJ平台上的所有题目、题目描述、样例输入和输出、以及解题思路等信息。以压缩包中的"hdoj.chm"文件为例,它是一个帮助文件格式,用于存储离线版的所有数据。CHM文件是微软的Compiled HTML Help...
"hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...
ACM ICPC HDOJ1003
ACM ICPC HDOJ1008
【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...
### hdoj1002——大整数相加 #### 题目背景与目的 本题目来源于杭州电子科技大学的在线评测系统(HDOJ),编号为1002的大整数相加问题。该题目主要考察的是编程者对于大整数处理的基本技巧以及对数组、循环等基础...
【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...
ACM ICPC HDOJ1000
根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
【ACM HDOJ 课件】是一套涵盖了多种计算机科学竞赛中常见算法与理论的教育资源,主要针对ACM(国际大学生程序设计竞赛)和HDOJ(华中地区大学生在线编程题库)的训练。这些课件深入浅出地讲解了在解决复杂问题时所需...
【标题】"HDOJ.rar_HD_HDOJ" 是一个与HDU(杭州电子科技大学)在线判题系统HDOJ相关的压缩包文件,其中包含了大量编程题目的源代码。 【描述】提到,这个压缩包包含了几百道HDOJ题目的源代码,这意味着它是一个宝贵...