证明洗牌算法是随机的

❶ VBA洗牌法原理谁能文字阐释一下

我找了此资料，一起共享

下面直接介绍【经典数组洗牌法】的算法原理：

假如你有一个布袋或者抽屉，里面有m=10个不同号码的球，

你要随机抽取，并保证不重复……

那么正确的做法是：

1.每次从布袋中随机抽取一个球；注意到rnd()函数的正确抽取目数应该是=m

2.抽取出来的这一个球要另外放置开；

【如果不另外放置，而只是记下号码后再把球返回布袋，接下来就无法保证这个已经被抽到过的球又被重复抽到。】

而这个，就是1楼代码中没有考虑到而产生的重大bug

3.继续从布袋中随机抽取另一个球；

注意到此时布袋中剩余球的数量少了一个是m-1了，因此rnd()函数的正确抽取目数应该是=m-1

4.抽取出来的这第2个球和已经抽取出来的第1个球放置在一齐，并且按新的序列排放。

5.重复以上随机抽取过程，注意到关键是：

a.每次抽取的母数即剩余球数要递减1个

b.每次抽取出来的新球要分开放置，不能放回布袋！

c.新抽取出来的球，要和前面已经取出的球按新的序列整齐排放。

d.剩下最最重要一点，但是看到这里好多人都可能不会意识到的一个问题：

布袋中剩余球如何放置？

即，假定布袋中球也是像放置在抽屉中那样，有序地排放着的，

那么每次抽走一个球，必然留下一个空格……【这就很麻烦了！】

因为大家知道，实际上数组中用rnd()函数只能是返回一个一定区间内的值及数组位置，

而如果留有空位的话，随机性就无法保证高效……万一抽到空格怎么办？难道重新再抽一次？

如果抽到只剩最后一个求时，则原先的布袋/抽屉中，将留下9个空格，则每次随机函数的计算结果，将有90%的概率仍旧抽到空格……

这就完蛋了。

【经典数组洗牌法】的真正原理是：

1.从m个值中【随机确定一个位置r】（利用Rnd()随机函数计算，具体算法是【以剩余数m为母数】区间进行随机值计算并取整返回位置）

2.把这个位置即要被抽取的元素(球)先取出拿在手中【存入临时变量t】，【腾出一个空位】。

3.把数组的【第1位置】（Lbound）元素拿出来，【放入刚才腾出的r空位】。并随即【腾出】了数组第一位置作为【新的空位】

（也可以以数组的最末位置（UBound）作为开始位置进行处理，具体算法代码就不太一样了）

4.把上述第2步骤取出的、存入了临时变量t的元素(球)，准确地放入【新的空位】，即数组第一位置。

这个数组第一位置中的【新元素】，就是已经被有效抽取的第1个不重复值。

然后，继续

1.抽第2个数时，以剩余母数m-1作为随机计算区间而返回一个随机值并计算取整返回第2个不重复的随机位置r

2.把这个位置r即要被抽取的第2个元素(球)先取出拿在手中【存入临时变量t】，【腾出一个空位】。

3.把数组的【第2位置】元素拿出来，【放入刚才腾出的r空位】。并随即【腾出】了数组第2位置作为【新的空位】

（也可以以数组的最末倒数第2位置进行处理，具体算法代码就不太一样了）

4.把上述第2步骤取出的、存入了临时变量t的元素(球)，准确地放入【新的空位】，即数组第2位置。

这个数组第2位置中的【新元素】，就是已经被有效抽取的第2个不重复值。

以上述方式反复进行，抽取、置换，存放，直到最后一个，也不会产生重复抽取了。

下面是【经典数组洗牌法】实际代码中最简单的代码例子：

对于一个下标1开始的一维数组，从中随机抽取n个元素返回。

SubGetRnd(arr,n)
Randomize
Fori=1Ton'正序洗牌1ton简化代码
r=Int(Rnd()*(n-i+1))+i
t=arr(r):arr(r)=arr(i):arr(i)=t'下标1开始一维代码
Next
EndSub

'正序洗牌1ton简化代码详解：

SubGetRnd(arr,n)

Randomize'随机种子初始化，保证每次代码运行或打开文件时出现的随机序列是和上次文件保存/运行时不同的序列。

Fori=1Ton'遍历1ton

r=Int(Rnd()*(n-i+1))+i、

'按每次剩余母数(n-i+1)作为随机计算区间，计算Rnd()*(n-i+1)然后用int()函数去整，得到剩余数中的随机位置。

'紧接着，这个随机位置后面【+i】处理，转化成从新的起点i开始的随机位置r。即不再包括已经抽取出的结果，避免重复。

t=arr(r)'把这个随机位置r中的元素取出，存入临时变量t

arr(r)=arr(i)'把【第i个】位置中的元素【放入刚才腾出的r空位】（实际数据操作时并没有腾出，而只是用新的值直接覆盖掉。）

arr(i)=t'把上面刚刚【腾出的i空位】放入刚才存放在临时变量t中的当前最新抽取元素，完成一次抽取过程。

Next'循环抽取、置换、存贮抽取结果

EndSub

❷ 几种扑克牌洗牌算法

洗牌的

几种话先设定好洗牌方式几种比方对分上下交l以及交织洗牌然扑克牌后用随机数生成函数确定单步洗牌作牌的数量多反复几遍即可。

1. 的一个合理的定义就是算法

2. 一副扑克张牌有种陈列方式。

这样做的好处：

给出的洗牌算算法应该可以等概率地生成这种结果中的一种

❸ 随机洗牌：哪一种算法是正确的

几乎所有的程序员都写过类似于“洗牌”的算法，也就是将一个数组随机打乱后输出，虽然很简单，但是深入研究起来，这个小小的算法也是大有讲究。我在面试程序员的时候，就会经常让他们当场写一个洗牌的函数，从中可以观察到他们对于这个问题的理解和写程序的基本功。 在深入讨论之前，必须先定义出一个基本概念：究竟洗牌算法的本质是什么？也就是说，什么样的洗牌结果是“正确”的？ 云风曾经有一篇博文，专门讨论了这个问题，他也给出了一个比较确切的定义，在经过洗牌函数后，如果能够保证每一个数据出现在所有位置的概率是相等的，那么这种算法是符合要求的。在这个前提下，尽量降低时间复杂度和空间复杂度就能得到好的算法。 第一个洗牌算法：随机抽出一张牌，检查这张牌是否被抽取过，如果已经被抽取过，则重新抽取，直到找到没被抽出过的牌，然后把这张牌放入洗好的队列中，重复该过程，直到所有的牌被抽出。 大概是比较符合大脑对于洗牌的直观思维，这个算法经常出现在我遇到的面试结果中，虽然它符合我们对于洗牌算法的基本要求，但这个算法并不好，首先它的复杂度为O(N2)，而且需要额外的内存空间保存已经被抽出的牌的索引。所以当数据量比较大时，会极大降低效率。

❹ 网易云音乐随机播放经常重复

因为随机播放采用的是洗牌算法。
是因为洗牌算法中生成的序列是随机的，在用户播放完一个随机播放的歌单后，系统会再次将虽有歌曲进行随机排序，重新生成另一个随机播放歌单，那么这两个歌单之间必然会有歌曲重复出现。
我们可以通过降低已听过的歌曲被选中的几率，或者在选中同一首歌曲的时候重新进行洗牌排序来降低此类问题出现的频率。

❺ c++编程，扑克牌洗牌，将一副扑克牌随机洗好，顺序输出54张扑克牌，求完整代码注：用C++写

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <time.h>
using namespace std;

// 输出辅助
const string strtype[6] = {"方块", "梅花", "红心", "黑桃", "小王", "大王"};
const string strnum[14] = {"", "A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"};

struct Card
{
// type是花色，0~3分别表示不同的花色,4是小王，5是大王
// num是牌上的数字
int type, num;
}dat[54];

int main()
{
// 时间随机函数
srand((unsigned)time(NULL));

int cnt = 0;
for (int i = 0; i < 4; i ++)
for (int j = 1; j <= 13; j ++)
{
dat[cnt].type = i;
dat[cnt ++].num = j;
}

dat[cnt ++].type = 4;
dat[cnt ++].type = 5;

for (int i = 1; i < 54; i ++)
// 交换函数，可以证明这样交换出来的数列是随机的
// 这里就不展开了
swap(dat[i], dat[rand() % i]);

// 输出
for (int i = 0; i < 54; i ++)
{
cout << strtype[dat[i].type];
if (dat[i].type < 4) cout << strnum[dat[i].num];
cout << ' ';
}

cout << endl;

system("pause");
}

我测试过啦，运行的一次结果如下（当然是随机的）：

方块10 黑桃6 梅花9 红心6 方块J 黑桃A 方块4 梅花3 黑桃K 梅花4 方块K 方块5 方块2
黑桃Q 方块A 红心K 梅花K 黑桃10 红心10 红心3 黑桃2 红心2 黑桃8 小王 方块Q 红心J
梅花6 梅花Q 红心9 方块7 梅花7 方块9 梅花J 红心A 红心4 大王 红心Q 红心8 方块6 黑
桃J 方块8 梅花A 方块3 红心7 黑桃7 梅花10 梅花2 黑桃5 红心5 黑桃3 黑桃9 黑桃4 梅
花5 梅花8
请按任意键继续. . .

希望能够帮到你！

❻ 什么是“随机”教你分清“伪随机”和“真随机”

​很久以前流传着这样一则笑话：一个身患重病的人决定去动手术。在手术之前，他问医生：“这起手术的成功率是多少？”医生回答他：“只有1%。”他很惊慌，但是医生说：“没事的，在你之前我已经治死过99个人了。”

这是一则嘲笑那些不懂“概率”的人的笑话，却讲出了“真随机”和“伪随机”之间的区别。

在四月末的时候，我曾写过一篇 《你打 游戏 靠的是技术，还是运气？》 ，其中就提及了“伪随机”这个概念。当时受限于篇幅，没有详细展开解释“伪随机”的概念。前不久，在因国际邀请赛而备受关注的Dota2在最近一次的更新中，有这么一条更新内容： “落空的负面效果和下坡攻击的落空效果现在都采用伪随机触发” 。

那么到底什么是 “伪随机” 呢？以及和“伪随机”对应的 “真随机” 又是什么概念？

赝随机数算法（Pseudo-Random Number Generator，简称PRNG） 是计算机的一个术语——当然，它也可以被叫做“伪随机数算法”，只是为了方便与 游戏 中的“伪随机数”进行区分，本文中统一称作“赝随机数算法”。

众所周知，计算机程序是由无数“0”和“1”两种状态构成的，如果一个状态不是“0”，那就必定是“1”，颇有种非黑即白的味道。

因此，在计算机程序中，不存在“不确定”的数字，只有确定的“1”和“0”。基于这种特性，计算机无法生成“真正的（不确定的）随机数”。

那么在计算机中，需要生成或是使用到随机数的时候怎么办呢？ 通常是利用计算机抓取一些数值，然后将这些数值输入至一个复杂算法 （常用的算法是同余法和梅森旋转算法，有兴趣的读者可以自行查询，这里就不展开讲了） 当中，通过一系列运算得出一个数字，这就是平常说的赝随机数了。

只要最初输入的数值（初值）不变，那么输出的值都会是同一个值，这就证明了这个数并不随机，只是看起来随机而已。

换句话说，只要这个随机数是由确定算法生成的，那就是赝随机数。

所以下一次在和朋友聊天时提到真随机数、伪随机数时，如果有人插嘴：“计算机只能生成伪随机数，所以根本没有什么真随机”，那你就可以霸气侧漏地说他是 “云玩家” 了。

我们通常说的 真随机 又名 “纯随机”（True Random Distribution） ，就是我们平常一直说的那种、一般意义上的“随机”。

在真随机中， 每一个事件都是相互独立、服从真随机分布的，不受其他事件的发生而改变 。比方说某款 游戏 为了吸引用户，拥有这么一个随机抽卡系统：每次抽卡时，都有1%的几率抽出SSR卡片，这个概率服从真随机分布。

回到我们最开始说的那个“治死99个”的笑话：我们一眼就能看出这个笑话的不合理性。但在抽卡 游戏 中，我们的大脑瞬间失去理智。有相当一部分玩家认为： 我连抽100次，总能抽到这张卡吧！

实际上，连抽100次却抽不出1%的SSR卡的几率是为(1-0.01)^100=36.6%，甚至还稍稍超过了1/3。将连抽数字上升至300，也仍有4.9%的几率。

换句话说，假设有10000个玩家连抽100次，就有约3660个玩家抽不出这张SSR；10000个玩家连抽300次，也仍有约490个玩家抽不出这张SSR ——这对玩家的 游戏 体验来说可以说是毁灭性的打击。

尽管纯随机在数学上是无罪的，在代码中更是明明白白、清清楚楚，但玩家抽不出卡可不会回想到初高中的数学课本， 而是首先怀疑几率是否被策划运营篡改、这背后又是否有肮脏的PY交易……

当然不仅仅是在抽卡系统当中如此。在一些竞技性比较强的 游戏 中（比如War3、Dota2之中——英雄联盟几乎完全摘除了随机系统，不在此列），连续数次的“走运”极大影响 游戏 的竞技性和观赏性。

比方说Dota中最着名的概率英雄虚空假面的技能“回到过去”： 使虚空假面有25%几率完全躲避一次伤害。 受限于War3引擎，这个技能采用的是真随机概率，在某个极端情况下（通常见于精彩集锦中），虚空假面能够保持很低的血量承受多次伤害却不死、最终反杀对手。这种带给敌方极差 游戏 体验的系统，因此也进入了计师们“整治范围”之中。

为了避免极差的 游戏 体验带来的玩家数量流失，设计者们提出了“伪随机”的概念： 在不确定性的随机事件当中，通过一系列算法使随机事件均匀分布在多次事件当中，尽可能减少或消除极端情况的发生，以提高玩家的 游戏 体验。

在设计师们的努力下，“伪随机”应运而生，这里的伪随机就和上文的赝随机数算法（PRNG）意义不同了。

制造“伪随机”的方法有很多，在War3、Dota2这类 游戏 当中普遍使用的是 “伪随机分布”（Pseudo Random Distribution，简称PRD） 处理概率。

就拿Dota2中最强大的暴击技能“恩赐解脱”来举例： 幻影刺客有15%的几率造成200%/325%/450%致命一击伤害 。在PRD机制下，幻影刺客的攻击实际上 并不是 每一刀都有15%的暴击率。

根据PRD机制的公式P(N)=N*C可得出15%几率的C值为3.22%，即幻影刺客的第一次攻击暴击概率为3.22%；如果第一刀没有暴击，则第二刀的暴击率提升至2倍，即6.44%；如果仍旧没有暴击，则提升至3倍的9.66%，以此类推。

如果继续推算，可得在第32刀时暴击几率会达到100%，最可能触发暴击的次数是第6刀，平均触发刀数是6.67刀等等……

同样，在连续触发暴击时，下一刀的暴击几率会减少。RPD机制使竞技 游戏 中连续触发或不触发技能的几率降低，避免了运气成分过度干扰战斗结果，大幅提升了玩家的 游戏 体验，但不影响这些随机事件的正反馈：TI6决赛的“打我五下晕三下”，可是令全球人民集体沸腾了呢！

除了伪随机分布RPD之外，还有两种常见的伪随机： 洗牌算法 和 组合随机 。

洗牌算法 最常见的用法，是在各大音乐播放器中的“随机播放”之中。在随机播放时，如果采用真随机，会导致一首歌无论如何都播放不出，或是同一首歌连续播放数次（有兴趣的读者可以计算一下这些概率）。为了解决这个问题，播放器采用的解决方案即是洗牌算法：将一个包含所有歌曲的数组像洗牌一样打乱，然后依次播放这个乱序数组。

至于 组合随机 ，这是一种广泛应用于各个 游戏 的做法：在抽奖的时候进行两次、或是更多次的判断，一次不随机，而剩下的判断则是真随机。比如说，你会在第X次抽卡时抽到SSR是确定的，但抽中的SSR具体是哪张卡，则是随机的——这就是广大手游中的“低保”系统了。

在一堆数据之中想要分清“真随机”和“伪随机”似乎并不是那么容易。那么接下来为大家介绍两个例子，有助于更好理解什么是“真随机”和“伪随机”：

真随机 ：有一天，小明在的班级上举办了一次抽奖活动。这个班级有40个学生，所以为了公平起见，保证每个学生都有1/40的几率中奖，老师准备了40个相同的纸盒，每个纸盒中都有40张纸条，有1张纸条是中奖纸条。这样一来，每个学生都有1/40的几率中奖，但每个学生是否中奖并不受其他学生的影响。在极端情况下，这个班上可能40个学生都能中奖。这就是真随机。

伪随机 ：小明班上举办了抽奖活动。为了公平起见，老师准备了1个纸盒，纸盒中有40张纸条，只有1张纸条是中奖纸条。这样一来，每个学生都有1/40的几率中奖——但是显而易见，这个班上有且仅有一名学生能够中奖。一名学生在中奖后，余下的所有学生中奖几率都会减少至0。这就是伪随机。

❼ 为什么直播时音乐随意在变换

摘要 您好，我认为，1)播放当前歌曲时才随机生成下一首，即完全随机(称为Random算法)：为了避免某些歌曲经常重复播放或很难被播放到，并非是盲目的完全随机下一首，而是需要分析用户的播放历史，需要比较好的算法进行支撑，最终始于随机却超脱随机。

❽ 关于牌类游戏洗牌算法一问：怎样才算把牌洗

1. 嵌入式洗牌法
把部分的塔罗牌拿在手中，使牌面朝下，将剩下的牌随意插入手里的牌，再自手中拿出一些牌，再插进去。重复这个步骤直到你觉得牌洗干净了为止。不过这种洗牌方式非常容易折损牌的边缘，要小心喔（有时还会刮伤手…）
2. 推摆洗牌法
将塔罗牌牌面朝下，在桌面上弄混，之后用左手的拇指将最上方的一叠牌推回左手，再用右手拇指推下方的一叠牌到右手，持续重复这个动作，直到所有的牌都被分开，之后重叠再一起并重复这些动作，直到你觉得已经洗干净为止。不过这个方法不是很容易，你必须常常练习才不会打到手（嘿嘿嘿…）
3. 一般正常洗牌法
将塔罗牌牌面朝下，双手以顺时针或逆时针方向将牌均匀混和即可。以上介绍的三种方式均为一般常见的洗牌方法（尤其是第三项，一般市面上的中文塔罗书籍均是以此法为主，故简略带过），在洗牌时一般是建议受占者心中专心默念要问的问题，而占卜师择是专心洗牌。至于是否要由受占者洗牌则是见仁见智。不过殿主向来是由自己洗牌，有时总会遇到‘朋友’想帮‘他的朋友’占卜，而‘他的朋友’并不在现场的情况，若是非当事者洗牌不可，大概这牌也就不需要算了…
至于是否一定要使用这几种方法来洗牌，答案是不一定。只要能将牌充分混和均匀，也不致伤到牌面就好了。
此外，在使用第三种洗牌方式时，殿主提供一些经验分享给大家：
1.转动时要利用指腹与手腕的力量
2.像写书法一样，手腕抬高
3.尽量轻柔地转动每一张牌
4.每一张牌建议尽量转三圈半以上（要公转也要自转喔）
5.注意上层的牌要与下层的牌混合均匀

❾ 用C++编写一个洗牌发牌的函数，玩家可能有两个、三个和四个

几乎所有的程序员都写过类似于“洗牌”的算法，也就是将一个数组随机打乱后输出，虽然很简单，但是深入研究起来，这个小小的算法也是大有讲究。我在面试程序员的时候，就会经常让他们当场写一个洗牌的函数，从中可以观察到他们对于这个问题的理解和写程序的基本功。

在深入讨论之前，必须先定义出一个基本概念：究竟洗牌算法的本质是什么？也就是说，什么样的洗牌结果是“正确”的？

云风曾经有一篇博文，专门讨论了这个问题，他也给出了一个比较确切的定义，在经过洗牌函数后，如果能够保证每一个数据出现在所有位置的概率是相等的，那么这种算法是符合要求的。在这个前提下，尽量降低时间复杂度和空间复杂度就能得到好的算法。

第一个洗牌算法：

随机抽出一张牌，检查这张牌是否被抽取过，如果已经被抽取过，则重新抽取，直到找到没被抽出过的牌，然后把这张牌放入洗好的队列中，重复该过程，直到所有的牌被抽出。

大概是比较符合大脑对于洗牌的直观思维，这个算法经常出现在我遇到的面试结果中，虽然它符合我们对于洗牌算法的基本要求，但这个算法并不好，首先它的复杂度为O(N2)，而且需要额外的内存空间保存已经被抽出的牌的索引。所以当数据量比较大时，会极大降低效率。

第二个算法：

设牌的张数为n，首先准备n个不容易碰撞的随机数，然后进行排序，通过排序可以得到一个打乱次序的序列，按照这个序列将牌打乱。

这也是一个符合要求的算法，但是同样需要额外的存储空间，在复杂度上也会取决于所采用的排序算法，所以仍然不是一个好的算法。

第三个算法：

每次随机抽出两张牌交换，重复交换一定次数次后结束

void shuffle(int* data, int length)

{

for(int i=0; i<SWAP_COUNTS; i++)

{

//Rand(min, max)返回[min, max)区间内的随机数

int index1 = Rand(0, length);

int index2 = Rand(0, length);

std::swap(data[index1], data[index2]);

}

}

这又是一个常见的洗牌方法，比较有意思的问题是其中的“交换次数”，我们该如何确定一个合适的交换次数？简单的计算，交换m次后，具体某张牌始终没有被抽到的概率为((n-2)/n)^m，如果我们要求这个概率小于1/1000,那么 m>-3*ln(10)/ln(1-2/n),对于52张牌，这个数大约是176次，需要注意的是，这是满足“具体某张牌”始终没有被抽到的概率，如果需要满足“任意一张牌”没被抽到的概率小于1/1000，需要的次数还要大一些，但这个概率计算起来比较复杂，有兴趣的朋友可以试一下。

Update: 这个概率是，推算过程可以参考这里，根据这个概率，需要交换280次才能符合要求

第四个算法：

从第一张牌开始，将每张牌和随机的一张牌进行交换

void shuffle(int* data, int length)

{

for(int i=0; i<length; i++)

{

int index = Rand(0, length);

std::swap(data[i], data[index]);

}

}

很明显，这个算法是符合我们先前的要求的，时间复杂度为O(N)，而且也不需要额外的临时空间，似乎我们找到了最优的算法，然而事实并非如此，看下一个算法。

第五个算法：

void shuffle(int* data, int length)

{

for(int i=1; i<length; i++)

{

int index = Rand(0, i);

std::swap(data[i], data[index]);

}

}

一个有意思的情况出现了，这个算法和第三种算法非常相似，从直觉来说，似乎使数据“杂乱”的能力还要弱于第三种，但事实上，这种算法要强于第三种。要想严格的证明这一点并不容易，需要一些数学功底，有兴趣的朋友可以参照一下这篇论文，或者matrix67大牛的博文，也可以这样简单理解一下，对于n张牌的数据，实际排列的可能情况为n! 种，但第四种算法能够产生n^n种排列，远远大于实际的排列情况，而且n^n不能被n!整除，所以经过算法四所定义的牌与牌之间的交换程序，很可能一张牌被换来换去又被换回到原来的位置，所以这个算法不是最优的。而算法五输出的可能组合恰好是n!种，所以这个算法才是完美的。

事情并没有结束，如果真的要找一个最优的算法，还是请出最终的冠军吧！

第六个算法：

void shuffle(int* data, int length)

{

std::random_shuffle(data, data+length);

}

没错，用c++的标准库函数才是最优方案，事实上，std::random_shuffle在实现上也是采取了第四种方法，看来还是那句话，“不要重复制造轮子”

不想写 - -

❿ 怎么证明这个洗牌算法是随机的

有一副牌假设有N张，请设计一个随机洗牌算法。
解决方案：
这里只给出一个可以使用数学证明每张牌出现在任何位置概率为1/N的算法。
Poker[N]
for (i = 0; i < N; ++i)
{
k = rand() % ( i + 1)
if (i != k)
{
switch(Poker[k], Poker[i]);
}