C++ 洗牌

大多數(shù)紙牌游戲都需要洗牌，也就是讓紙牌隨機(jī)排列。在第10.5節(jié)，我們看到了怎樣生成隨機(jī)數(shù)，但怎樣利用隨機(jī)數(shù)實(shí)現(xiàn)洗牌功能卻并非顯然意見的。

一種可行的方案是，模擬人洗牌的方法，將牌分為兩堆，然后通過在每個(gè)牌堆中輪流選擇的方式實(shí)現(xiàn)原牌堆的重新組織。因?yàn)橐话愣?，人并不能做到完美地洗牌，而程序?jīng)過大約7次迭代之后，牌堆中紙牌的順序已經(jīng)相當(dāng)隨機(jī)了。但是計(jì)算機(jī)程序每次在做完美洗牌的時(shí)候有一個(gè)令人討厭的屬性——它并非真正隨機(jī)的。實(shí)際上，經(jīng)過8次完美洗牌之后，你會(huì)發(fā)現(xiàn)牌堆又回到原來的排列了。關(guān)于這一結(jié)論的討論，請(qǐng)參考http://www.wiskit.com/marilyn/craig.html，或者以“perfect shuffle”為關(guān)鍵詞通過搜索引擎查詢相關(guān)信息。

還有一個(gè)更好的洗牌算法：遍歷牌堆，每次選擇一張紙牌，每次迭代時(shí)選擇兩張紙牌并交換其位置。

下面代碼是該算法工作原理的大體輪廓。為了大概說出程序的意思，我混用了C++語句和自然語言句子，這有時(shí)也稱為偽代碼：

for (int i=0; i<cards.length(); i++) {
// 在i和cards.length()之間選擇一個(gè)隨機(jī)數(shù)
// 將第i張牌和隨機(jī)選擇的紙牌交換
}

偽代碼的優(yōu)點(diǎn)是能清晰地表達(dá)出你需要的函數(shù)。在這個(gè)例子中，我們需要像randomInt這樣的函數(shù)用于在參數(shù)low和high之間選擇一個(gè)隨機(jī)數(shù)，也需要swapCards這樣的函數(shù)用于交換兩個(gè)索引值指定的位置的紙牌。

看一下第10.5節(jié)，你就應(yīng)該能想出怎么編寫randomInt函數(shù)了，盡管還是要小心處理生成的可能在區(qū)間之外的索引值。

你也可以自己想出swapCards函數(shù)。這些函數(shù)的剩余實(shí)現(xiàn)就作為作業(yè)留給讀者。