HDU1465.错排问题

本文主要是介绍HDU1465.错排问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题意】

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

【思路】

1、当N=1和2时，易得解，假设F(N-1)和F(N-2)已经得到，重点分析下面的情况：

2、当有N封信的时候，前面N-1封信可以有N-1或者N-2封错装

3、前者，对于每种错装，可从N-1封信中任意取一封和第N封错装，故=F(N-1)*(N-1)

4、后者简单，只能是没装错的那封和第N封交换信封，没装错的那封可以是前面N-1封中的任意一个，故= F(N-2) * (N-1)

递归式：d[n]= (n-1)*( d[n-1] + d[n-2])；其中d[1]=0，d[2]=1（错排公式）

#include<stdio.h>
int main()
{int n,i;__int64 a[10001];while(scanf("%d",&n)!=EOF){a[1]=0;a[2]=1;for(i=3;i<=n;i++){a[i]=(i-1)*(a[i-1]+a[i-2]);}printf("%I64d\n",a[n]);}return 0;
}

 

这篇关于HDU1465.错排问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---