一道关于递归算法的问题，请各位高手指教，谢谢！

Question

n个人编号，n个座位也编号，如果每个人坐的座位编号与自己的编号不同，问有多少种方法？

Answer 1

我们取座位i进行分析，此时可以有n-1个人可以选，假设所选人编号为j(i!=j)
下面分两种情况
1） 编号为i的人选座位j，剩下n-2个人，也是要求每个人坐的座位编号与自己的编号不同，所以问题规模便缩小到了n-2
2） 编号为i的人不选座位j，此时就相当于剩下了n-1个人，要求每个人坐的座位编号与自己的编号不同
综上可得：f[ n ] = ( n - 1 ) * ( f[ n-2 ] + f[ n-1 ] ) ;
临界条件是 f[ 1 ] = 0 , f[ 2 ] = 1

Answer 2

我个人意见
1. n个人编号，n个座位也编号 是一个递归问题，可以这样解
if (n == 1)
return 1;
return n * Posit(n-1);

2. "如果每个人坐的座位编号与自己的编号不同"的反面，就是有不少于一个相同的座号。 这是一个组合问题。也可以由递归解
if (n == 0)
return 1;
return 2 * Person(n-1);

那么显然解法就是
Num = Posit(n) - [Person(n) - 1];
// - 1 是因为Person(n)中包含一个全为零项

3. 这两个问题合起来，用一个递归，实在想不出来。这里抛砖引玉，期待精彩回复。

Answer 3

我觉得要分情况讨论：
如过是有顺序的坐就是(n-1)*(n-2)*……*2*1 种，也就是第一个坐了，第二个才能坐

如果没有顺序的坐就是（n-1)的n次方