发邮件(PAT)

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;
}