请给思路：取苹果c++

Question

柜子上有编号1~n的n个苹果，现在有个调皮的小孩把n个苹果从柜子上取下来，然后再放回去，当放回去时要求每个苹果都不能放在原来的位置上，求摆放总方法数；
输入样例：
5
输出样例：
44

Answer 1

当n=1时，只有1个苹果，不可能错排，故a(n)=0
当n=2时，1、2只能错排为2、1，故a(n)=1
考虑n时的错排情况，可从以下两种方法得到n的错排：
1）前n-1个数已错排，错排数a(n-1)，第n个数与前面n-1个数中任何一个数交换均形成错排，因此有(n-1)*a(n-1)种排法
2）前n-2个数已错排，错排数a(n-2)，第n-1和n个数交换，可形成错排，有a(n-2)中排法，交换后，将第n个数再与前面n-2个数中任何一个数交换仍是错排，有(n-2)*a(n-2)种排法，因此共有(n-1)*a(n-2)种排法。此处不能考虑交换后将第n-1个数与前面n-2个数交换，因其排法已包含在情况1）中。
综合1）、2）可知，当n>=3时，a(n)=(n-1)*a(n-1)+(n-1)*a(n-2)，根据这个思路就可以编写程序了。