返回信息流http://coolshell.cn/articles/8593.html
这篇文章的前三个洗牌算法为啥是错误的?
这是一条镜像帖。来源:北邮人论坛 / acm-icpc / #87301同步于 2015/7/8
该镜像源已超过 30 天没有更新,可能在源站已被删除。
ACM_ICPC机器人发帖
这三种洗牌算法为什么是错的?
lingshen
2015/7/8镜像同步4 回复
订阅后,新回复会通过你的通知中心匿名送达。
4 条回复
主要是前三个算法在测试样本数比较少的时候,结果是正确的,测试数量大的时候,结果偏差就大了。为什么他们不是等概率生成的
【 在 ykprocess 的大作中提到: 】
: 我觉得随便写一个算法是错误的很正常的啊,你可以试着去想下,如何证明一个洗牌算法是正确的
【 在 lingshen 的大作中提到: 】
: 主要是前三个算法在测试样本数比较少的时候,结果是正确的,测试数量大的时候,结果偏差就大了。为什么他们不是等概率生成的
1. 直接按照算法,算概率
2. 证明变量之间的独立性啊
虽然第二点比较难,但是用第一条就可以算出前三个算法是错的了
我觉得要定义什么叫正确吧。
比如:从52张扑克牌(无joker)中抽取4张,请设计一个随机抽取的方法,要求任何一张牌被抽到的概率都相等。
方法:每次取AAAA, 2222, 3333, 4444, ……QQQQ, KKKK这13种组合中的一种。每张牌被抽到的概率都是1/13。
另法:先从52张中等概率抽一张,然后从剩下的51张中抽一张,然后从剩下的50张中抽一张,然后从剩下的49张中抽一张,如果每次都是等概率的,那么每张牌被抽到的概率也都是1/13。
两种方法都满足要求,但显然后者比前者更“幸运”一些。