文档章节

错排问题

DataPig
 DataPig
发布于 2017/08/16 09:37
字数 470
阅读 2
收藏 0

错排问题

NowCoder每天要给很多人发邮件。有一天他发现发错了邮件,把发给A的邮件发给了B,把发给B的邮件发给了A。于是他就思考,要给n个人发邮件,在每个人仅收到1封邮件的情况下,有多少种情况是所有人都收到了错误的邮件?
即没有人收到属于自己的邮件。

输入描述:

输入包含多组数据,每组数据包含一个正整数n(2≤n≤20)。

输出描述:

对应每一组数据,输出一个正整数,表示无人收到自己邮件的种数。 示例1 输入

2 3 输出

1 2

解法:

https://www.nowcoder.com/questionTerminal/95e35e7f6ad34821bc2958e37c08918b
来源:牛客网
当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用D(n)表示,那么D(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.
第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;
第二步,放编号为k的元素,这时有两种情况:⑴把它放到位置n,那么,对于剩下的n-1个元素,由于第k个元素放到了位置n,剩下n-2个元素就有D(n-2)种方法;⑵第k个元素不把它放到位置n,这时,对于这n-1个元素,有D(n-1)种方法;
综上得到
D(n) = (n-1) [D(n-2) + D(n-1)]
特殊地,D(1) = 0, D(2) = 1.
有了递推公式,一切就迎刃而解了。

#include<stdio.h>
int main (void)
{
    long long der[ 21 ] = { 0, 0, 1 };
    int i;
    for ( i = 3; i < 21; i++ ){
        der[ i ] = ( i - 1 ) * ( der[ i - 2] + der[ i - 1 ] );
    }

    int n;
    while ( scanf( "%d", &n ) != EOF ){
        printf("%lld\n", der[ n ] );
    }
    return 0;
}

© 著作权归作者所有

DataPig
粉丝 1
博文 12
码字总数 8686
作品 0
济南
私信 提问
[P4921] 情侣?给我烧了!

回顾一下错排公式 错排问题: 设n位错排数为D[n]。考虑元素1的位置,设置为k(有n-1中 );在考虑元素k的位置, 若为1,则转换为n-2位的错排;否则,视元素k为元素1(不能放在位置1),转换为...

nosta
2018/12/26
0
0
Java跨进程锁定文件

Java跨进程锁定文件(即OS级别的锁定文件),需要使用排它的锁,需要使用FileOutputStream或者RandomAccessFile(这里指"rw"模式)。 再说类FileInputStream和模式为"r"的RandomAccessFile,...

shawnplaying
2016/07/04
132
0
hdu2048 神、上帝以及老天爷【错排问题】【容斥原理】

解题思路: 即是求错排数。 先是递推的做法 还有容斥的做法: 正整数1, 2, 3, ……, n的全排列有 n! 种,其中第k位是k的排列有 (n-1)! 种;当k分别取1, 2, 3, ……, n时,共有 种排列是至少放...

cdsszjj
2018/01/07
0
0
MFC如何调用JS代码

近排研究MFC调用JS代码,使用这个控件去调用(msscript.ocx),但是调用过程中,总是出出错。 MFC调用代码: JS代码: 提示如下错误: Unhandled exception at 0x75CF812F in QQGameActivat...

OSC首席过客
2014/04/04
1K
3
怎么实现 1对多通信

10个人 从1 开始 这时候 3退出 那么 就剩下 12 4-10 . 如果3退出又加入。 那么 他肯定是11 。 从新分给 他一个 11的号码。 难道这种排位法有错? 1对多通信 不管你多少人 都是N+1 你可以开1...

天池番薯
2014/09/07
235
4

没有更多内容

加载失败,请刷新页面

加载更多

Kafka 原理和实战

本文首发于 vivo互联网技术 微信公众号 https://mp.weixin.qq.com/s/bV8AhqAjQp4a_iXRfobkCQ 作者简介:郑志彬,毕业于华南理工大学计算机科学与技术(双语班)。先后从事过电子商务、开放平...

vivo互联网技术
10分钟前
4
0
java数据类型

基本类型: 整型:Byte,short,int,long 浮点型:float,double 字符型:char 布尔型:boolean 引用类型: 类类型: 接口类型: 数组类型: Byte 1字节 八位 -128 -------- 127 short 2字节...

audience_1
57分钟前
7
0
太全了|万字详解Docker架构原理、功能及使用

一、简介 1、了解Docker的前生LXC LXC为Linux Container的简写。可以提供轻量级的虚拟化,以便隔离进程和资源,而且不需要提供指令解释机制以及全虚拟化的其他复杂性。相当于C++中的NameSpa...

Java技术剑
57分钟前
11
0
Wifiphisher —— 非常非常非常流氓的 WIFI 网络钓鱼框架

编者注:这是一个非常流氓的 WIFI 网络钓鱼工具,甚至可能是非法的工具(取决于你的使用场景)。在没有事先获得许可的情况下使用 Wifiphisher 攻击基础网络设施将被视为非法活动。使用时请遵...

红薯
今天
53
1
MongoDB 4 on CentOS 7安装指南

本教程为CentOS x86_64 7.x操作系统下,MongoDB Community x86_64 4.2(GA)安装指南。 安装方式一:yum repo在线安装 [此方式较为简单,官方推荐] Step1:新建MongDB社区版Yum镜像源。 # vim ...

王焱君
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部