`

HDOJ 2048 神、上帝以及老天爷(错排公式)

 
阅读更多

题目链接: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题目分类 HDOJ题目分类” HDOJ,全称为Happy DingO Online Judge,是一个在线编程竞赛平台,它为参赛者提供了大量编程题目进行练习和比赛,旨在提升编程技能和算法理解。HDOJ的题目分类是帮助用户...

    hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000

    【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...

    HDOJ 80题 Java

    【标题】"HDOJ 80题 Java"是一份专为Java程序员设计的在线编程挑战集合,源自杭州电子科技大学(HDOJ)的在线评测系统。这些题目旨在帮助Java开发者提升算法理解与编程能力,同时也为那些习惯于C++但希望在Java环境...

    HDOJ1002

    ACM ICPC HDOJ1002

    HDOJ1001

    ACM ICPC HDOJ1001

    hdoj1001标程

    hdoj1001标程

    HDOJ部分简单题(JAVA)

    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 解题代码 答案

    hdoj1004,解题代码,答案代码,欢迎下载

    HDOJ离线版

    离线版通常包含HDOJ平台上的所有题目、题目描述、样例输入和输出、以及解题思路等信息。以压缩包中的"hdoj.chm"文件为例,它是一个帮助文件格式,用于存储离线版的所有数据。CHM文件是微软的Compiled HTML Help...

    hdoj--acm题目,有注释

    "hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...

    HDOJ1003

    ACM ICPC HDOJ1003

    HDOJ 1008

    ACM ICPC HDOJ1008

    OJ.tar.gz_HDOJ _OJ源码_oj

    【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...

    hdoj1002——大整数相加

    ### hdoj1002——大整数相加 #### 题目背景与目的 本题目来源于杭州电子科技大学的在线评测系统(HDOJ),编号为1002的大整数相加问题。该题目主要考察的是编程者对于大整数处理的基本技巧以及对数组、循环等基础...

    hdoj 2013 多校训练4标程+解题报告

    【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...

    HDOJ1000

    ACM ICPC HDOJ1000

    hdoj2066最短路

    根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...

    HDOJ DP题目总结

    一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧

    ACM HDOJ 课件

    【ACM HDOJ 课件】是一套涵盖了多种计算机科学竞赛中常见算法与理论的教育资源,主要针对ACM(国际大学生程序设计竞赛)和HDOJ(华中地区大学生在线编程题库)的训练。这些课件深入浅出地讲解了在解决复杂问题时所需...

    HDOJ.rar_HD_HDOJ

    【标题】"HDOJ.rar_HD_HDOJ" 是一个与HDU(杭州电子科技大学)在线判题系统HDOJ相关的压缩包文件,其中包含了大量编程题目的源代码。 【描述】提到,这个压缩包包含了几百道HDOJ题目的源代码,这意味着它是一个宝贵...

Global site tag (gtag.js) - Google Analytics