错排问题(全错排)

62 阅读 0 评论 41 点赞

我是靠谱客的博主机智时光，最近开发中收集的这篇文章主要介绍错排问题(全错排)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

错排问题(全错位排列问题 Derangement)

概念：
考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n)。研究一个排列错排个数的问题，叫做错排问题或称为更列问题。

典型例子：
1. 一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，都装错信封的装法有多少种（历史有名的“装错信封问题”）；
2. 将一排书重新摆放，要求每本书都不摆在原来的位置，一共有几种不同的摆法；
3. [SDUT 2058] 小厮将每一封信都投错了烽火台（一个烽火台一封），一共有多少种可能的情况;
4. 几个人各写一张贺年卡互相赠送，共有多少种赠送方法（因为不能送自己）。

错排公式

组合数学上的错排公式：
D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!]
简化版本：
D(n) = [n!/e+0.5] ，其中e是自然对数的底，[x]为x的整数部分

这个公式放这里目前就用来涨涨自己的见识。它可以通过容斥原理来推导，也可以通过递推推导，而递推公式即我们的重点。

递推推导过程

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

第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法；
第二步，放编号为k的元素，这时有两种情况：
⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有D(n-2)种方法；
⑵第k个元素不把它放到位置n，这时，对于这n-1个元素，有D(n-1)种方法；
综上得到
D(n) = (n-1) [D(n-2) + D(n-1)]
特殊地，D(1) = 0, D(2) = 1

int D(int n)
{
    if (n == 0 || n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
        return (n-1) * (D(n-2) + D(n-1));
}

三国佚事——巴蜀之危

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic Discuss

Problem Description

话说天下大势，分久必合，合久必分。。。却道那魏蜀吴三国鼎力之时，多少英雄豪杰以热血谱写那千古之绝唱。古人诚不我欺，确是应了那句“一将功成万骨枯”。
是夜，明月高悬。诸葛丞相轻摇羽扇，一脸愁苦。原来是日前蜀国战事吃紧，丞相彻夜未眠，奋笔急书，于每个烽火台写下安排书信。可想，这战事多变，丞相运筹帷幄，给诸多烽火台定下不同计策，却也实属不易。
谁成想这送信小厮竟投靠曹操，给诸葛丞相暗中使坏。这小厮将每封书信都投错了烽火台，居然没有一封是对的。不多时小厮便被抓住，前后之事却也明朗。这可急坏了诸葛丞相，这书信传错，势必会让蜀军自乱阵脚，不攻自破啊! 诸葛丞相现在想知道被这小厮一乱，这书信传错共有多少种情况。

Input

题目有多组数据，处理到文件结尾，丞相共写了n（1 <= n <= 20）封书信，输入一个正数n。

Output

输出书信传错的情况数。

Sample Input

1
3
6

Sample Output

0
2
265

#include <stdio.h>
typedef long long LL;
LL f[50] ;

int main()
{
	f[0] = 0 ;
	f[1] = 0 ;
	f[2] = 1 ;
	int n ;

	for(int i = 3 ;i<= 20 ; i++)
	{
		f[i] = (i-1)*(f[i-1]+f[i-2]) ;
	}
	while(~scanf("%d",&n))
	{
		printf("%lldn",f[n]);
	}
	
	return 0 ;
}