错排公式 hdu1465

递推的方法推导错排公式

　　当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用M(n)表示,那么M(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.

　　第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;

　　第二步,放编号为k的元素,这时有两种情况.1,把它放到位置n,那么,对于剩下的n-2个元素,就有M(n-2)种方法;2,不把它放到位置n,这时,对于这n-2个元素,有M(n-1)种方法;

　　综上得到

　　M(n)=(n-1)[M(n-2)+M(n-1)]

　　特殊地，M(1)=0,M(2)=1

题目地址：

思路：

传说中的“错排公式”=。=

当有n封信时，前n-1封或前n-2封可能错。

如果前n-1封错，则可以把第n封与前面任意n-1封交换而使n封全错。有f(n-1)*(n-1)

如果前n-2封错，则可以把对的那封与第n封交换，而对的那封可以是n-1封内任意一封。所以有f(n-2)*(n-1)

所以 f(n) = (f(n-1)+f(n-2)) * (n-1)

 

 

代码：

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

// Author: Tanky Woo // HDOJ 1465    #include  using namespace std;   __int64 f[22]; int main() {   f[1] = 0; f[2] = 1; f[3] = 2; for(int i = 4; i <= 20; ++i) f[i] = (i-1)*(f[i-2]+f[i-1]); int num; while(scanf("%d", &num) != EOF) //是说用__int64没效果，原来输出时忘了加%I64d printf("%I64d\n", f[num]); return 0; }