洗牌算法具体指什么?

2024-04-06 07:48
文章标签 算法 具体 洗牌

本文主要是介绍洗牌算法具体指什么?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

什么是洗牌算法?

洗牌算法是我们常见的随机问题,在玩游戏、随机排序时经常会碰到。本质是让一个数组内的元素随机排列,即数组乱序。

如何证明数组乱序的随机性能?

对于任意数组,数组中元素个数n >= 2,n为自然数。如果可以证明经过这个算法将数组乱序,数组中每个元素出现在 n 个位置任意一个位置的概率都是 1/n,即可以说明随机性良好。

常见的概率计算?

定理:设A、B是互不相容事件(AB=φ),则:P(A∪B)=P(A)+P(B)

条件概率:已知事件B出现的条件下A出现的概率,称为条件概率,记作:P(A|B)

                条件概率计算公式:

                当P(A)>0,P(B|A)=P(AB)/P(A)

                当P(B)>0,P(A|B)=P(AB)/P(B) 

乘法公式 P(AB)=P(A)×P(B|A)=P(B)×P(A|B)

相互独立事件

 相互独立事件: 事件A(或B)是否发生对事件B(A)发生的概率没有影响,这样的两个事件叫做相互独立事件。相互独立事件同时发生的概率P(A*B) =P(A) *P(B)

 

互斥事件

互斥事件:指的是不可能同时发生的两个事件。

 例如:事件A和B的交集为空,A与B就是互斥事件,也叫互不相容事件。也可叙述为:不可能同时发生的事件。如A∩B为不可能事件(A∩B=Φ),那么称事件A与事件B互斥,其含义是:事件A与事件B在任何一次试验中不会同时发生。

 

如何使用数学归纳法证明数组乱序的随机性?

证明:数组中元素个数n >= 2,n为自然数,经过该算法将数组乱序,数组中每个元素出现在 n 个位置任意一个位置的概率都是 1/n.

 

1.当n=2时,根据算法,显然有 1/2 的概率两个数交换,有 1/2 的概率两个数不交换,因此对 n = 2 的情况,元素出现在每个位置的概率都是 1/2,满足随机性要求。

2、假设n=m时,算法的随机性符合要求。

事件C:当数组中有m个元素时,元素出现的每个位置。P(C)=1/m

事件A:元素出现在末尾位置。 P(A)=1/(m+1)

事件B:元素出现在非末尾位置。A、B为相互对立事件,P(B)=1-P(A)=m/(m+1)

在元素出现在非末尾位置的条件下,元素出现在其他m个位置的概率。P(BC)

根据概率计算的乘法法则P(AB)=P(A)×P(B|A)=P(B)×P(A|B)

P(BC)==P(B)×P(C|B)=P(C)×P(B|C)

事件B和事件C为相互独立事件

P(C|B)=P(C),P(B|C)=P(B)

综上所述,P(BC)=P(B)×P(C)=[m/(m+1)]×[1/m]=1/(m+1)

即可证明n=m+1

结论:对于任意大于等于2的自然数n,算法随机性均符合要求。

 

问题讨论:

1.数学归纳法的适用范围?

最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。证明分下面两步:
证明当n = 1时命题成立。

证明如果在n = m时命题成立,那么可以推导出在n = m+1时命题也成立。(m代表任意自然数)

2.数学归纳法的原理?

 

这种方法的原理在于:首先证明在某个起点值时命题成立,然后证明从一个值到下一个值的过程有效。当这两点都已经证明,那么任意值都可以通过反复使用这个方法推导出来。把这个方法想成多米诺效应也许更容易理解一些。例如:你有一列很长的直立着的多米诺骨牌,如果你可以:

证明第一张骨牌会倒。
证明只要任意一张骨牌倒了,那么与其相邻的下一张骨牌也会倒。
那么便可以下结论:所有的骨牌都会倒下。

3.互不相容事件和相互对立事件的关系?

相互对立事件是互不相容事件的一个特例。

若A交B为不可能事件,A并B为必然事件,那么称A事件与事件B互为对立事件,其含义是:事件A和事件B必有一个且仅有一个发生。

 

这篇关于洗牌算法具体指什么?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/879396

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

MySQL分区表的具体使用

《MySQL分区表的具体使用》MySQL分区表通过规则将数据分至不同物理存储,提升管理与查询效率,本文主要介绍了MySQL分区表的具体使用,具有一定的参考价值,感兴趣的可以了解一下... 目录一、分区的类型1. Range partition(范围分区)2. List partition(列表分区)3. H

Java Multimap实现类与操作的具体示例

《JavaMultimap实现类与操作的具体示例》Multimap出现在Google的Guava库中,它为Java提供了更加灵活的集合操作,:本文主要介绍JavaMultimap实现类与操作的... 目录一、Multimap 概述Multimap 主要特点:二、Multimap 实现类1. ListMult

golang中slice扩容的具体实现

《golang中slice扩容的具体实现》Go语言中的切片扩容机制是Go运行时的一个关键部分,它确保切片在动态增加元素时能够高效地管理内存,本文主要介绍了golang中slice扩容的具体实现,感兴趣... 目录1. 切片扩容的触发append 函数的实现2. runtime.growslice 函数gro

Golang interface{}的具体使用

《Golanginterface{}的具体使用》interface{}是Go中可以表示任意类型的空接口,本文主要介绍了Golanginterface{}的具体使用,具有一定的参考价值,感兴趣的可以了... 目录一、什么是 interface{}?定义形China编程式:二、interface{} 有什么特别的?✅

Qt之QMessageBox的具体使用

《Qt之QMessageBox的具体使用》本文介绍Qt中QMessageBox类的使用,用于弹出提示、警告、错误等模态对话框,具有一定的参考价值,感兴趣的可以了解一下... 目录1.引言2.简单介绍3.常见函数4.按钮类型(QMessage::StandardButton)5.分步骤实现弹窗6.总结1.引言

PyQt5 QDate类的具体使用

《PyQt5QDate类的具体使用》QDate是PyQt5中处理日期的核心类,本文主要介绍了PyQt5QDate类的具体使用,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录核心功能常用方法及代码示例​1. 创建日期对象​2. 获取日期信息​3. 日期计算与比较​4. 日

SQL Server中的PIVOT与UNPIVOT用法具体示例详解

《SQLServer中的PIVOT与UNPIVOT用法具体示例详解》这篇文章主要给大家介绍了关于SQLServer中的PIVOT与UNPIVOT用法的具体示例,SQLServer中PIVOT和U... 目录引言一、PIVOT:将行转换为列核心作用语法结构实战示例二、UNPIVOT:将列编程转换为行核心作用语

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ