这个题是错排公式啊,一直不知道在那里推推推,怎么推都是错的。然后看错排公式,还不是一眼就懂什么意思。

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

特殊地,D(1) = 0, D(2) = 1.

我们可以设定n个信封进行排列。

1 2 3 4 5 6 7 8 9 10 ... n

拿一个出来,因为要排错,自己正确的位置不能选,所以有n-1种位置可以选。选完之后又分两种情况。

第一种(这种情况好理解),拿出来的这个数(假定为1),然后放到第k个位置,然后第k个位置的信封放到第一个来,这是第一种情况。

这种情况的话就是剩下的n-2个进行重排,也就是公式里面的

D(n-2) 

第二种(个人开始看这种情况没看懂,脑子里都开始递归了,可是回溯之后发现就是这么神奇,不废话继续。。。)拿出来的这个数不放在k的位置,那么它就放在q的位置好了。这时可以把k“看成”是第1个的位置,注意,是“看成”。这种情况有没有一点像是我们刚刚拿出1的时候那种情况呢。那么就是剩下的n-1个进行重排咯。所以就是

D(n-1)

继而可以得到错排公式。D(n) = (n-1) [D(n-2) + D(n-1)]


题目:飞机票直达(D - 计数,排列


代码:

Memory: 1728 KB
Time: 0 MS
Language: C++
Result: Accepted
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn=20;
long long num[maxn];
int n;
int main()
{
    num[0]=0;
    num[1]=1;
    for(int i=2;i<20;i++)num[i]=i*(num[i-1]+num[i-2]);//递推
    while(scanf("%d", &n)!=EOF)
    {
        printf("%lld\n", num[n-1]);
    }
    return 0;
}