加载中...

13.6 洗牌


大多数纸牌游戏都需要洗牌,也就是让纸牌随机排列。在第10.5节,我们看到了怎样生成随机数,但怎样利用随机数实现洗牌功能却并非显然意见的。

一种可行的方案是,模拟人洗牌的方法,将牌分为两堆,然后通过在每个牌堆中轮流选择的方式实现原牌堆的重新组织。因为一般而言,人并不能做到完美地洗牌,而程序经过大约7次迭代之后,牌堆中纸牌的顺序已经相当随机了。但是计算机程序每次在做完美洗牌的时候有一个令人讨厌的属性——它并非真正随机的。实际上,经过8次完美洗牌之后,你会发现牌堆又回到原来的排列了。关于这一结论的讨论,请参考http://www.wiskit.com/marilyn/craig.html,或者以“perfect shuffle”为关键词通过搜索引擎查询相关信息。

还有一个更好的洗牌算法:遍历牌堆,每次选择一张纸牌,每次迭代时选择两张纸牌并交换其位置。

下面代码是该算法工作原理的大体轮廓。为了大概说出程序的意思,我混用了C++语句和自然语言句子,这有时也称为伪代码

for (int i=0; i<cards.length(); i++) {
// 在i和cards.length()之间选择一个随机数
// 将第i张牌和随机选择的纸牌交换
}

伪代码的优点是能清晰地表达出你需要的函数。在这个例子中,我们需要像randomInt这样的函数用于在参数low和high之间选择一个随机数,也需要swapCards这样的函数用于交换两个索引值指定的位置的纸牌。

看一下第10.5节,你就应该能想出怎么编写randomInt函数了,尽管还是要小心处理生成的可能在区间之外的索引值。

你也可以自己想出swapCards函数。这些函数的剩余实现就作为作业留给读者。


还没有评论.