错排问题

Description

某人写了n封信和n个信封,如果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况。

Input

输入n（n <=20）

Output

输出情况总数

Sample Input

2

Sample Output

1

解题思路

使用加法原理的递推式： f ( n ) = ( n − 1 ) ∗ ( f ( n − 1 ) + f ( n − 2 ) ) ; f ( 1 ) = 0 ; f ( 2 ) = 1 ; f(n)=(n-1)*(f(n-1)+f(n-2));f(1)=0;f(2)=1; f(n)=(n−1)∗(f(n−1)+f(n−2));f(1)=0;f(2)=1;就可以解出

#include<iostream>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
long long m;  
long long cp(long long n)
{
   
	if(n==1) return 0;//判断0的情况
	if(n==2) return 1;//判断1的情况
	return (n-1)*(cp(n-1)+cp(n-2));//使用递推公式
}
int main()
{
   
	cin>>m;
	cout<<cp(m);
	return 0;
}