首页 / 算法 / 扫雷与算法:如何随机化的布雷(一)
扫雷与算法:如何随机化的布雷(一)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了扫雷与算法:如何随机化的布雷(一),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3087字,纯文字阅读大概需要5分钟。
内容图文
![扫雷与算法:如何随机化的布雷(一)](/upload/InfoBanner/zyjiaocheng/813/6aa99ec0590f4c1683f3617f7512c4ed.jpg)
这是通过「扫雷与算法」小程序来讲解算法的第一章:如何随机化的进行布雷,主要介绍了三种不那么好的方法,希望通过这些不好的方法能让大家明白第二章要讲解的「洗牌算法」有多牛逼。
补充:「扫雷与算法」小程序会在写完后进行开源,发布在我的 GitHub 上面。
方法一
最想当然的方法就是随机的在二维区间寻找一个点布雷即可,代码如下:
for?(var?i?=?0;?i?<?mineNumber;?i++)?{
???????var?row?=?this.rangeRandom(0,?this.rowCount?-?1);
???????var?col?=?this.rangeRandom(0,?this.colCount?-?1);
???????//使用数字?9?表示该区域有雷
???????tmpMineMap[row][col]?=?9;
?}
这种实现逻辑的一个弊端就是会在已经布雷的位置再度布雷,进而导致整个区域的布雷数量与要求不符合。
如上图所示,需要布雷的个数为 5 ,但在最后一次的随机布雷过程中只埋了 4 颗雷。
方法二
方法二是对方法一的改善:既然会重复埋雷,那么只需要再埋雷的过程中判断一下该位置是否已经埋雷即可。
- 如果该位置是空的,那么则布雷,然后进行寻找新的位置布下下一颗雷
- 如果该位置已经被安置了雷,那么就需要重新生成一个位置来安置
代码如下:
???for?(var?i?=?0;?i?<?mineNumber;?i++)?{
??????//通过死循环来实现不停的寻找,直到安置好雷
??????while?(true)?{
????????var?row?=?this.rangeRandom(0,?this.rowCount?-?1);
????????var?col?=?this.rangeRandom(0,?this.colCount?-?1);
????????//用数字?9?表示该区域有雷,如果该位置没有布雷,那么则放置
????????if?(tmpMineMap[row][col]?!=?9)?{
???????????tmpMineMap[row][col]?=?9;
???????????//跳出循环
???????????break;
????????}
??????}
????}
使用效果如下:
效果貌似挺好的,但小伙伴们可能已经注意到了,上面的代码中有一段 死循环 代码,这就意味着如果棋盘很大,雷区很多,并且你的运气还不够好的话,那么就有可能一直在执行这段 死循环 代码,进而导致程序的卡死崩溃。
虽然没有卡死,但执行时间很久
方法三
第三种方法是先将雷布置在最前面,然后再不停的打乱。
实现代码如下:
//先按顺序排列
for?(var?i?=?0;?i?<?mineNumber;?i++)?{
????var?row?=?parseInt(i?/?this.colCount);
????var?col?=?i?%?this.colCount;
????//使用数字?9?表示该区域有雷
????tmpMineMap[row][col]?=?9;
}
//定义交换的次数,次数越多越混乱随机
var?swapTime?=?100;
for?(var?i?=?0;?i?<?swapTime;?i++)?{
????//随机位置1
????var?row1?=?this.rangeRandom(0,?this.rowCount?-?1);
????var?col1?=?this.rangeRandom(0,?this.colCount?-?1);
????//随机位置2
????var?row2?=?this.rangeRandom(0,?this.rowCount?-?1);
????var?col2?=?this.rangeRandom(0,?this.colCount?-?1);
????//交换两个位置
????var?temp?=?tmpMineMap[row1][col1];
????tmpMineMap[row1][col1]?=?tmpMineMap[row2][col2];
????tmpMineMap[row2][col2]?=?temp;
}
这种方法的一个弊端就是对于 swapTime 的依赖程度很高,如果设置的交互次数少了,大部分雷都还是按照一开始的顺序安置,都在最前面的位置,全部的雷并不是随机排放。
最重要的一点是:每个位置安置雷的概率并不是等可能的,也就意味着它不能做到随机化。
我尝试过在小程序上进行概率模拟,但每次都会卡死了,后续发现能优化继续模拟出概率来的话再补上。
总结
在大部分情况下,方法二 与 方法三 是可以满足我们随机化处理的过程的,但方法二有可能运行卡死崩溃,方法三中每个位置安置雷的概率并不是等可能的。
?? 看完三件事:
如果你觉得这篇内容对你挺有启发,我想邀请你帮我三个忙:
- 点赞,让更多的人也能看到这篇内容(收藏不点赞,都是耍流氓 -_-)
- 关注我和专栏,让我们成为长期关系
- 关注公众号「五分钟学算法」,第一时间阅读最新的算法文章,公众号后台回复 1024 送你 50 本 算法编程书籍。
内容总结
以上是互联网集市为您收集整理的扫雷与算法:如何随机化的布雷(一)全部内容,希望文章能够帮你解决扫雷与算法:如何随机化的布雷(一)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。