简单错排问题

骑猪看日落 2023-10-06 16:49 12阅读 0赞

#### 目录 ####

*  1.定义
 *  2.错排公式
 *  3.公式推导
 *  4.问题应用

## 1.定义 ##

n个有序的元素有n!个不同的排列，如果一个排列使得所有的元素不在原来的位置上，则称这个排列为错排（也称重排）。例如，1 2的错排是唯一的，只有1个，即2 1。1 2 3的错排有2个，即3 1 2，2 3 1。

## 2.错排公式 ##

设i个有序元素的错排有Ai个，则n个有序的元素的错排个数为  
**An=(n-1)\*(An-1\+An-2)**

## 3.公式推导 ##

设共有n个有序元素  
（1）考虑第n个元素，如果将其放在某一个位置，一共有n-1种情况；  
（2）考虑第i(1≤i<n)个元素，这时有两种情况：  
① 如果将其放到位置n，那么对于除n以外的n-1个元素，由于第i个元素放到了位置n，所以剩下的n-2个元素进行错排即可，故有An-2种情况；  
② 如果第i个元素不放到位置n，这时对于这n-1个元素的错排，有An-1种放法。又根据乘法和加法法则，综上得到**An=(n-1)\*(An-1\+An-2)**。

## 4.问题应用 ##

题目[见杭电OJ2048][OJ2048]

#include <iostream>
    
    using namespace std;
    
    void LuckDraw(){
        
    	int C,n,i;
    	long draw[21]={
        0,0,1,2};
    	long sum;
    	for(i=4;i<=20;i++) {
        
    		draw[i]=(i-1)*(draw[i-1]+draw[i-2]);
    	}
    	cin>>C;
    	while(C--){
        
    		sum=1;
    		cin>>n;
    		if(n<=1 || n>20){
        
    			cout<<"参与抽奖人数的范围为(1,20]之间的整数！"<<endl;
    			continue;
    		}
    		//计算n! 
    		for(i=1;i<=n;i++){
        
    			sum*=i;
    		}
    		//控制小数位输出的位数为2
    		cout.precision(2);
    		//n个元素的错排总数/n!即表示抽奖活动没有一个人中奖的概率 
    		cout<<fixed<<(draw[n]*1.0/sum)*100<<endl;
    	}
    }

[OJ2048]: https://acm.hdu.edu.cn/showproblem.php?pid=2048

发表评论取消回复

表情：

评论列表（有 0 条评论，12人围观）

还没有评论，来说两句吧...

相关阅读

相关错排问题详解

错排问题（Derangement）概念释义[\][Link 1] 又叫错位排列、重排，即使一个排列所有的元素都不在原来的位置上。 > 错排问题是组合数学发展史上

约定不等于承诺〃/ 2024年03月16日 22:54/ 0 赞/ 30 阅读

相关【算法问题】错排问题

目录 1.概述 2.代码实现 2.1.获取错排情况总数 2.2.获取每种错排情况 3.应用 1.概述（1）`n` 个

超、凢脫俗/ 2024年02月18日 13:19/ 0 赞/ 30 阅读

相关简单错排问题

目录 1.定义 2.错排公式 3.公式推导 4.问题应用 1.定义 n个有序的元素有n!个不同的排列，如果一个排列使得所有的元素不在原来的

骑猪看日落/ 2023年10月06日 16:49/ 0 赞/ 13 阅读

相关如何理解错排问题

一、什么是错排问题举例：十本不同的书放在书架，现重新摆放，使得每本书都不在原来的位置上，有几种摆法？一个人给十个同学写信，但他把所有的信都装错了信封，问共有多

小灰灰/ 2023年07月24日 09:26/ 0 赞/ 6 阅读

相关错排问题错排公式 Hdu 1465 + 2048 +2049 + 2068 + 4535

也称伯努利-欧拉装错信封问题 n错排公式：F\[n\]=(n-1)\(F\[n-1\]+F\[n-2\]) 证明： 1.当前n-1个错排时：将其任意一封信与n对调,共(

小鱼儿/ 2022年08月25日 10:52/ 0 赞/ 151 阅读

相关错排公式

错排公式 M(n)=(n-1)\[M(n-2)+M(n-1)\] 递推的方法推导错排公式　　当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用M(n)

傷城~/ 2022年08月10日 14:52/ 0 赞/ 133 阅读

相关递推中的错排问题

本文大部分资料来自网络。。。。假设有n个数，元素编号与位置编号各不对应的方法数用D(n)表示，那么D(n-1)就表示n-1个编号元素放在n-1个编号位置，各不对应

逃离我推掉我的手/ 2022年07月12日 09:47/ 0 赞/ 273 阅读

相关错排模板

错排： d\[1\]=0; d\[2\]=1; d\[n\]=(n-1)\(d\[n-1\]+d\[n-2\]) 代码： include <bits/

柔光的暖阳◎/ 2022年05月31日 08:45/ 0 赞/ 110 阅读

相关错排问题的递推公式

问题描述考虑一个n个数字的排列，使所有的数字都不在自己所对应序号的位置上，这样的一个排列就称为原排列的一个错排，现在给定一个数字n，求解所有可能的错排的个数。分析

痛定思痛。/ 2022年05月16日 03:15/ 0 赞/ 219 阅读

相关错排问题

错排问题就是一种递推式，不过它比较著名且常用，所以要熟记！方法一： n各有序的元素应有n！种不同的排列。如若一个排列式的所有的元素都不在原来的位置上，则称

爱被打了一巴掌/ 2022年05月03日 15:58/ 0 赞/ 148 阅读