hd acm 1465

时间:2024-08-25 15:35:02

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

思路:由这道题引入错排公式:f(n)=(n-1)*[f(n-1)+f(n-2)]。

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

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

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

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

    

代码:

#include <stdio.h>
#include <stdlib.h>
long long errorstage(int n);

int main()
{
  int n;
  while(scanf("%d",&n)!=EOF)
  {
  printf("%lld\n",errorstage(n));
  }
  return 0;
}
long long errorstage(int n)
{
  if(n==1) return 0;
    else if(n==2) return 1;
      else return (n-1)*(errorstage(n-1)+errorstage(n-2));
}