信息学之家

用户名：weixiaohao

访问量：2147

签　名：

非淡泊无以明志，非宁静无以致远。

等　　级
排　　名	22929
经　　验	598
参赛次数	0
文章发表	2
年　　龄	12
在职情况	学生
学　　校	青岛超银中学（镇江路校区）
专　　业	暂无

　　自我简介：

您好，欢迎参观我的题库：http://uoj.ac/

TA的其他文章

C语言训练-尼科彻斯定理-题解(C++代码)（By 信息学之家）
浏览：587

你可能喜欢

不容易系列2-题解(C++代码)【递归算法 & 错排公式秒杀】

　　作者: 信息学之家　　　　发表时间：2019-08-01 16:45:10 浏览：1281　|　评论：0　

原题链接：不容易系列2

#浅谈错排公式
## 错排公式定义
一段序列中一共有n个元素，那么可知这些元素一共有n!种排列方法。假如在进行排列时，原来所有的元素都不在原来的位置，那么称这个排列为错排。而错排数所指的就是在一段有n个元素的序列中，有多少种排列方式是错排。

关于错排公式的干货需要大家**牢记**：
1. *（常考点）* **递归关系：D(n)=(n-1)(D(n-1)+D(n-2))  特别地有D(1)=0,D(2)=1；**
2. 错排公式：D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!]，  特别地有0!=1   1!=1 。

------------

## 推导过程（大致了解即可）
### 公式一
当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.

------------
###公式二

下面通过这个递推关系推导通项公式：
为方便起见，设D(k) = k! N(k), k = 1, 2, …, n,
则N(1) = 0, N(2) = 1/2.
n ≥ 3时，n! N(n) = (n-1) (n-1)! N(n-1) + (n-1)! N(n-2)
即 nN(n) = (n-1) N(n-1) + N(n-2)
于是有N(n) - N(n-1) = - [N(n-1) - N(n-2)] / n = (-1/n) [-1/(n-1)] [-1/(n-2)]…(-1/3) [N(2) - N(1)] = (-1)^n / n!.
因此
N(n-1) - N(n-2) = (-1)^(n-1) / (n-1)!,
N(2) - N(1) = (-1)^2 / 2!.
相加，可得
N(n) = (-1)^2/2! + … + (-1)^(n-1) / (n-1)! + (-1)^n/n!
因此
**D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!]**.
此即错排公式。

------------

#问题 1181: 不容易系列2题解（C++）
```cpp
#include <iostream>
using namespace std;

long long f ( long long x )			   //递归 
{
	if ( x == 1 ) return 0;            //设置递归边界 
	if ( x == 2 ) return 1;
	
	return ( x - 1 ) * ( f ( x - 1 ) + f ( x - 2 ) );
									   //错排公式
}

int main ()
{
	long long n;
	while ( cin >> n )				   //含有多组数据
	{
		cout << f ( n ) << endl;
	}
	return 0;
}
```
作者weixiaohao，代码共参考，请多多点评指教！

0.0分

3 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

信息学之家

TA的其他文章

你可能喜欢

弟弟的作业（C语言代码）

C二级辅导-阶乘数列（C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C++代码）

C二级辅导-求偶数和（C++代码）

明明的随机数（C++代码）

不容易系列2-题解(C++代码)【递归算法 & 错排公式秒杀】

评论区

精彩推荐

【求帮助】C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C二级辅导-公约公倍（C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

简单的a+b （C语言代码）

C二级辅导-同因查找（C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

矩阵乘方（C语言代码）

信息学之家

TA的其他文章

你可能喜欢

弟弟的作业 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C++代码）

C二级辅导-求偶数和 （C++代码）

明明的随机数 （C++代码）

不容易系列2-题解(C++代码)【递归算法 & 错排公式秒杀】

评论区

精彩推荐

【求帮助】C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C二级辅导-公约公倍 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

简单的a+b （C语言代码）

C二级辅导-同因查找 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

矩阵乘方 （C语言代码）

弟弟的作业（C语言代码）

C二级辅导-阶乘数列（C语言代码）

C二级辅导-求偶数和（C++代码）

明明的随机数（C++代码）

　　评论区

C二级辅导-公约公倍（C语言代码）

C二级辅导-同因查找（C语言代码）

矩阵乘方（C语言代码）