糊涂人寄信——递推
思路分析：当有n封信，n个信封时。第k封信没有装在第k个信封里（k从1~n），就算所有的信封都装错了。我们可以得知的是，当有1封信,时，装错类别数为0。当有两封信时，装错类别为1。
当有三封信时，我们可以先拆解问题，假设第一封信装错了位置（有两种可能），那么就还剩下2封信要装错位置，而两封信要装错的类别我们也已经求解得知了，所以这里3封信要装错位置的类别数就为 第一封信装错位置的可选择数+剩下的信的装错总类别。也就是2*1=1。
要装错一共分为两个大类。（0<x<n,0<y<n）
1：当第x封信装进了第y个信封时（y有n-1个选择），第y封信也恰好装进了第x个信封。此时还有n-2封信需要装错。（n-1）*x[n-2]
2：当第x封信装进了第y个信封时（y有n-1个选择），第y封信没有恰好装进了第x个信封。此时还有n-1封信需要装错。(n-1)*x[n-1]
总加起来就是 sum=（n-1）*x[n-2]+（n-1）*x[n-1]；
代码实现：
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#define MAX 100
using namespace std;
long long int n, arr[MAX];/*数组用来存数字*/
long long int f(int x)
{
if(x==1) return 0 ;
if (x == 2) return 1;
else return (x - 1) * f(x - 1) + (x - 1) * f(x - 2);
}
int main()
{
cin >> n;
f(n);
cout << f(n) << endl;
return 0;
}