1.题目描述

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

2.输入描述:

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

3.输出描述:

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

4.输入例子:

2
3

5.输出例子:

1
2

6.解题思路:

这是一个错排问题,有推导公式D[k]=(k-1) * (D[k-1]+D[k-2])

信箱:|A B C D|
信件:|a b c d|
以a为参照,分为三种情况:

一、a放进B,b放进A,我们得到
|C D| _相当于D(n-2) = |A B|
|c d|__相当于D(n-2) = |a b|

二、a放进B,b不放进A,我们得到
<mark>(b不能放进A,A也就是相当于B,等同于b不放进B)</mark>
|A C D| = |B C D|_ 相当于D(n-1) = | A B C|
|b c d|_ = |b c d| _ 相当于D(n-1) = | a b c|

三、同理,当a不放进B,而是放进C、D…,同一二推导
也就是说,共有k-1种推导一二的情况,而推导一二共有D[k-1]+D[k-2]种情况
我们可以得出最终公式D[k]=(k-1)*(D[k-1]+D[k-2])

7.源代码:

#include<stdio.h>
int main()
{
	int n,i;
	long long num[21];
	num[0]=0;
	num[1]=0;
	num[2]=1;
	for(i=3;i<21;i++)
		num[i]=(i-1)*(num[i-1]+num[i-2]);
	while(scanf("%d",&n)!=-1)
	{
		printf("%lld\n",num[n]);
	}
	return 0;
}