前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >扫雷与算法:如何随机化的布雷(二)之洗牌算法

扫雷与算法:如何随机化的布雷(二)之洗牌算法

作者头像
五分钟学算法
发布2019-06-18 15:51:43
1.3K0
发布2019-06-18 15:51:43
举报
文章被收录于专栏:五分钟学算法

前言:扫雷与算法:如何随机化的布雷(一)

先来思考一个问题:有一个大小为 100 的数组,里面的元素是从 1 到 100 按顺序排列,怎样随机的从里面选择 1 个数?

最简单的方法是利用系统的方法 Math.random() * 100 ,这样就可以拿到一个 0 到 99 的随机数,然后去数组找对应的位置就即可。

接下来在思考一个问题: 有一个大小为100的数组,里面的元素是从 1 到 100 按顺序排列,怎样随机的从里面选择 50 个数?

注意数字不能重复!

注意数字不能重复!

注意数字不能重复!

如果根据上面的思路,你第一想法是:随机 50 次不就行了?

但是,这样做有个很明显的 bug :数字是会重复的。

修改一下?

弄一个数组,把每一次随机的数都放到数组里,下一次随机就看这个数组里面有没有这数,有的话就继续随机,直到这个数组里面有 50 个数字就停止。

这样是可以的!

但,还是有个小问题,考虑一下极端情况:有一个大小为100的数组,里面的元素是从 1 到 100 按顺序排列,怎样随机的从里面选择 99 个数

如果按照上面的方法操作,越往后选择的数字跟前面已经挑选的数字重复的概率越高,这就会造成如果数组很大,选择的数字数目也很大的话,重复次数在量级上会很大。

这个时候就需要换一个思路,如果先将数组里面的元素打乱,那么按顺序选择前 50 个不就可以了?

是的!

但我们得注意什么叫乱?

一副扑克有 54 张牌,有 54! 种排列方式。所谓的打乱指的是,你所执行的操作,应该能够 等概率地生成 这 54! 种结果中的一种。

洗牌算法就能做到这一点。

洗牌算法

Fisher–Yates shuffle 算法由 Ronald Fisher 和 Frank Yates 于 1938 年提出,在 1964 年由 Richard Durstenfeld 改编为适用于电脑编程的版本。

这个算法很牛逼却很好理解,通俗的解释就是:将最后一个数和前面任意 n-1 个数中的一个数进行交换,然后倒数第二个数和前面任意 n-2 个数中的一个数进行交换。。。

小程序实现代码

代码语言:javascript
复制
for (var i = this.rowCount * this.colCount - 1; i >= 0 ; i--){
  var iX = parseInt(i / this.colCount);
  var iY = i % this.colCount;

  var randNumber = this.rangeRandom(0, i + 1);

  var randX = parseInt(randNumber / this.colCount);
  var randY = randNumber % this.colCount;

 //交换两个位置
  var temp = tmpMineMap[iX][iY];
  tmpMineMap[iX][iY] = tmpMineMap[randX][randY];
  tmpMineMap[randX][randY] = temp;
}

小程序实现效果

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-06-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 五分钟学算法 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 洗牌算法
  • 小程序实现代码
  • 小程序实现效果
相关产品与服务
云开发 CloudBase
云开发(Tencent CloudBase,TCB)是腾讯云提供的云原生一体化开发环境和工具平台,为200万+企业和开发者提供高可用、自动弹性扩缩的后端云服务,可用于云端一体化开发多种端应用(小程序、公众号、Web 应用等),避免了应用开发过程中繁琐的服务器搭建及运维,开发者可以专注于业务逻辑的实现,开发门槛更低,效率更高。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档