wayne 发表于 2014-5-9 13:28:39

洗牌算法

一副扑克牌有54张牌，有两种洗牌算法：
for(int i=0;i<n;++i)
{
        swap(a,a);
}




for(int i=0;i<n;++i)
{
        swap(a,a);
}


大家分别讨论下 其 概率分布，貌似计算不是那么的显然呢。

mathe 发表于 2014-5-9 14:34:18

伪代码写的不对，但是能理解意思。第一种置换出$n^n$个结果，分给n!类，比例不能均匀。第二种显然每操作一轮，增加一个位置元素确定结果，其取值是均匀的，所以最终是均匀分布的

dianyancao 发表于 2014-5-13 05:17:51

第一个算法：swap(a,a);
对于每种牌面的概率似乎也是等可能的

因为当交换a和a时，a和a取每张牌的概率都为1/n
第i次交换a和a时，总是使a和a取每张牌的概率都为1/n
所以循环完毕，将使每个a取每张牌的概率都为1/n,
即各种扑克牌顺序出现的概率为等可能的

因此当试验次数m为n!的整数倍时，可以让各种扑克牌顺序等可能发生

dianyancao 发表于 2014-5-13 06:26:55

上面的算错了，第一个洗牌算法产生的扑克牌顺序依赖于未洗牌前的扑克牌顺序
第i次交换a和a时，只是是使a取每张牌的概率为1/n，a取每张牌的概率和未洗牌前的扑克牌顺序有关

第一个算法产生的每个置换是等可能的，所以按各种扑克牌顺序n!分类，不能使每个类别的概率相等
如果试验次数趋于无穷大，是否可以使得每个类别的概率差值趋于0呢？

yy31742 发表于 2014-5-14 16:59:02

受教了！！！！
页: [1]
查看完整版本: 洗牌算法