【递推问题】发邮件

牛客链接：https://www.nowcoder.com/questionTerminal/95e35e7f6ad34821bc2958e37c08918b

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

---

输入描述:

输入包含多组数据，每组数据包含一个正整数n（2≤n≤20）。

---

输出描述:

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

---

输入

---

2
3

---

输出

---

1

2

这是一个非常经典的数学问题, 错排问题

组合学中有这样一个问题：

某人给五个朋友写信，邀请他们来家中聚会。请柬和信封交由助手去处理。粗心的助手却把请柬全装错了信封。请问：助手会有多少种装错的可能呢？

这个问题是是由当时有名的数学家约翰·伯努利(Johann Bernoulli，1667—1748)的儿子丹尼尔·伯努利(Danid Bernoulli，17OO一1782)提出来的。瑞士著名数学家欧拉按一般情况给出了一个递推公式：
用A、B、C……表示写着ｎ位友人名字的信封，a、b、c……表示ｎ份相应的写好的信纸。把错装的总数为记作D(n)。假设把ａ错装进Ｂ里了，包含着这个错误的一切错装法分两类：
(1)b装入Ａ里，这时每种错装的其余部分都与A、B、a、b无关，应有D(n－2)种错装法。　　　　
(2)ｂ装入A、B之外的一个信封，这时的装信工作实际是把（除a之外的）n－1份信纸ｂ、ｃ……装入（除B以外的）n－1个信封A、C……，显然这时装错的方法有D(n－1)种。
总之在ａ装入B的错误之下，共有错装法D(n－2)＋D(n－1)种。
a装入C，装入D……的n－2种错误之下，同样都有D(n－1)＋D(n－2)种错装法，因此D(n)＝(n－1)[D(n－1)＋D(n－2)]
　　这是递推公式，令ｎ＝1、2、3、4、5逐个推算就能解答蒙摩的问题。
    D(1)＝0，D(2)＝1，D(3)＝2，D(4)＝9，D(5)＝44
答案是44种。

// write your code here cpp

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define ll long long
ll arr[22] = { 0, 0, 1 };
ll fun[21] = { 0, 1, 2 };
int n;
void doit()
{
	for (int i = 3; i <= 20; i++)
		arr[i] = (i - 1) * (arr[i - 1] + arr[i - 2])
		,fun[i] = i * fun[i - 1];
}

int main()
{
	doit();
	while (cin >> n && n != 0)printf("%.2f%c\n", 1.0 * arr[n]/fun[n] * 100,'%');
	return 0;
}