怎样洗牌?
初学编程,有道题目需要洗牌
具体要求应该就是每张牌出现在每个位置概率是一样的吧
这都涉及到什么知识?有什么经典思路么?
[解决办法]
"每张牌出现在每个位置概率是一样的 "
这个条件是不充分的
给个经典算法
RANDOMIZE-IN-PLACE(A)
n=A.length
for i=1 to n
swap(A[i],A[RANDOM(i,n)])
[解决办法]
你的算法在“排除rand()实现中的伪随机性质”情况下是随机的。
实际上,yaunx(杨)给你的伪码已经是很好的算法了,你的算法本质上和他给的是一样的。
你的算法为了避免已洗的牌不再重复出现,用了while循环判断。而yaunx(杨)给的伪码通过
随机交换区间[1:n]间的元素,保证了不会出现两张相同的牌。
所以,你的算法本质上是拉斯维加斯算法,运行时间无保障,而yaunx(杨)的算法本质是蒙特卡罗算法,运行时间有保障。
[解决办法]
生成一个n项序列的随机排列(假定随机函数r(n)不是伪随机的):
先将第n项与第r(n)项交换,1 <= r(n) <= n
再将第n - 1项与第r(n - 1)项交换,1 <= r(n - 1) <= n - 1
.
.
将第i项与第r(n - i + 1)项交换,1 <= r(n - i + 1) <= n - i + 1.
当i = 1时算法终止.
用这种方法生成的序列出现的概率刚好是1/n!,这就保证了每次洗牌的均匀性.
[解决办法]
void shuffle(Card *wDeck)
{
Card temp;
int i,j;
for(i=0;i <52;i++)
{
j=rand()%52;
temp=wDeck[i];
wDeck[i]=wDeck[j];
wDeck[j]=temp;
}
}
[解决办法]
定义一个数组
int a[54];
对数组初始化,让数组的每一个元素代表一张牌.
初始化随机函数的种子:srand(time(0));
用rand()函数在a[0]--a[54]之间随机先一张牌,将它和a[0]交换.
再在剩下的53张牌中随机选一张,并和a[1]交换.
...
循环53次,最后就得到一张洗好的牌
如果你想知道rand()函数的实现,可以看看 三卷本的 <计算机程序设计艺术>