本文主要是介绍洗牌算法具体指什么？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
什么是洗牌算法?
洗牌算法是我们常见的随机问题，在玩游戏、随机排序时经常会碰到。本质是让一个数组内的元素随机排列，即数组乱序。
如何证明数组乱序的随机性能？
对于任意数组,数组中元素个数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必有一个且仅有一个发生。
这篇关于洗牌算法具体指什么？的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
