即使燈泡的初始狀態(tài)不定，當(dāng) n=2 時，兩個人也能保證都知道對方進(jìn)過房間。假設(shè)雙方手中各有兩個球，囚犯 A 總是試圖把自己的小球放進(jìn)盒子，囚犯 B 總是試圖把小球取走。如果 B 拿到了 4 個小球，他就知道了 A 一定來過房間；而只要 A 放好的小球被拿走了， A 也知道 B 進(jìn)過了房間。

但是，當(dāng) n>2 時，不存在這樣的協(xié)議，使得有兩個人都能獲知所有人都已進(jìn)過房間。 Peter Winkler 的 Mathematical Puzzles: A Connoisseur’s Collection 一書中給出了這個結(jié)論的一個大致證明思路。

讓我們考慮其中任何一個囚犯。我們假設(shè)他的策略是確定性的，他的下一步行動完全取決于之前看到的狀態(tài)序列。假設(shè)在某一步，他看到的狀態(tài)和上次離開房間時的狀態(tài)相同，但他選擇了改變狀態(tài)。這時，你可以質(zhì)問他，那你為啥不在上次就把狀態(tài)改過來，偏偏要這次才去扳開關(guān)呢？看守完全有可能連續(xù)兩次都是叫你進(jìn)的房間，這樣你不就浪費了一次進(jìn)房間的機會了嗎？因此，我們可以假設(shè)，當(dāng)他進(jìn)入房間時看見的狀態(tài)和上次走的時候一樣，他是不會去扳動開關(guān)的。

接下來，讓我們假設(shè)在某一步，這個囚犯的策略是“不動開關(guān)，保留原狀態(tài)”。那么，我們可以認(rèn)為他以后就再也不會動那個開關(guān)了！因為在最壞情況下，他根本沒有改變燈泡狀態(tài)的機會！具體地說，若無視掉這個囚犯以后的行動，今后的房間狀態(tài)序列里必然有一種狀態(tài)將出現(xiàn)無窮多次，比方說狀態(tài)“開”出現(xiàn)了無窮多次吧。那么在最壞的情況下，這個囚犯從此開始總是在開燈的時候進(jìn)屋。而他在這一步?jīng)]有變動開關(guān)，并且以后的每一步里他所看到的狀態(tài)都將和上次看到的一樣，因此以后他都不會變動開關(guān)了。

因此，這名囚犯首次進(jìn)入房間時的策略絕不可能是“不動開關(guān)”，因為這樣他以后可能都沒機會動開關(guān)了，沒人會知道他來過房間。如果他的策略是“如果燈開著，就把它關(guān)掉”，那么由第一個引理，今后他看見關(guān)燈狀態(tài)都不會去改變狀態(tài)了，直到下次見到燈亮?xí)r才會有所行動。每次見到燈亮?xí)r，他有兩種選擇，把燈關(guān)掉，或者讓它接著亮。如果選擇關(guān)燈，他又要等到下次燈亮才會行動；如果不關(guān)燈的話，相當(dāng)于他這次沒做任何操作，今后就再也沒法行動了。也就是說，他的整個策略無非是“關(guān)過多少多少次燈之后就不管了”。類似地，如果他首次進(jìn)入房間時的策略是“如果燈關(guān)著，就把它打開”，同理可知他今后的策略限制在了“再開幾次燈就不開了”。當(dāng)然，首次進(jìn)入房間的策略還可能是“無論狀態(tài)如何，總是扳動開關(guān)”，不過實際情況一揭曉，他的策略也就立即歸為了上述兩種情況中的一種。

換句話說，每個人的策略都無外乎兩種：只負(fù)責(zé)開 x 次燈，或者只負(fù)責(zé)關(guān) x 次燈。當(dāng)然，如果所有人都只開燈不關(guān)燈(或者只關(guān)燈不開燈)，肯定是一點用處都沒有。因此，無妨假設(shè)囚犯 A 負(fù)責(zé)開燈，囚犯 B 負(fù)責(zé)關(guān)燈。如果囚犯 C 也只負(fù)責(zé)開燈， A 永遠(yuǎn)不能分辨出 B 、 C 究竟是都完成了協(xié)議，還是都差最后一步；如果囚犯 C 只負(fù)責(zé)關(guān)燈， B 就成了那個被蒙在鼓里的人了。

也就是說，整個問題的唯一解法就是，其中一個人只負(fù)責(zé)關(guān)燈，另外所有人只負(fù)責(zé)開燈；或者其中一個人只負(fù)責(zé)開燈，另外所有人都只關(guān)燈。換句話說，我們的“統(tǒng)計者協(xié)議”其實是唯一的解法。

在 Mathematical Puzzles: A Connoisseur’s Collection 一書中，我們有幸看到了這個問題的另一個更加有趣的變種，讓囚犯們的難題繼續(xù)活躍著人們的大腦。

還是 100 個囚犯，還是一個空房間，還是要求所有囚犯事先構(gòu)造一個協(xié)議，能保證有人可以斷定出所有人都來過房間。不過，這次不同的是，房間里有兩個燈泡，分別由兩個開關(guān)來控制(不妨假設(shè)初始時他們都是不亮的)。大家估計要說了，一個燈泡都能解決的事兒，用兩個燈泡還不容易？嘿嘿，這次有一個附加的要求：所有人都必須遵循同一套策略。

這些智力游戲不僅僅是思維的體操，它竟然有不少讓人意想不到的實際應(yīng)用。遠(yuǎn)在這個智力題誕生之前，就有一個幾乎等價的分布式計算難題困擾著人們：假如一個程序有 n 個進(jìn)程，它們操作的是同一段(不太寬裕的)公共內(nèi)存。但在程序運行中，有些進(jìn)程可能會崩潰掉。我們希望程序能報告出當(dāng)前還有多少個進(jìn)程在工作，但使用的空間越少越好。一個簡單的解決方案就是，預(yù)先指定一個進(jìn)程作為統(tǒng)計者，照搬囚犯們的策略，只消一個 bit 即可統(tǒng)計出活動進(jìn)程的大致數(shù)量。但問題是——這個統(tǒng)計進(jìn)程崩潰了咋辦？因此，為了避免有關(guān)鍵進(jìn)程崩潰，這些進(jìn)程的行為必須得一致才行。 1990 年， Michael J. Fischer 、 Shlomo Moran 、 Steven Rudich 、 Gadi Taubenfeld 四位牛人共同發(fā)表了一篇叫做 The Wakeup Problem 的論文，提出了著名的蹺蹺板協(xié)議 (see-saw protocol) ，成功解決了這一難題。

我們還是把其中一個開關(guān)想象成一個盒子，它里面只能放一個小球。再把另一個開關(guān)想像成一個蹺蹺板，它也只有兩種狀態(tài)：左低右高、左高右低。要想改變蹺蹺板的傾斜方向，只能扳動它的開關(guān)。初始時，每個囚犯手中都有一個(假想的)小球。每個囚犯第一次進(jìn)入房間后，他都幻想自己坐到蹺蹺板低的那一邊上，然后把自己這一側(cè)扳高。以后每次回到這個房間時，他都看看自己所在的那一側(cè)是高還是低：如果是低的話，他就取走盒子里的小球(如果有的話)，于是手中就多了一個小球；如果是高的話，他就在盒子里放一個小球(如果盒子是空的)，此時手中的小球就少了一個。注意，如果他把手中的最后一個小球放進(jìn)盒子了(此時他手中沒有小球了)，他就必須從蹺蹺板上下來，把自己所在的那一側(cè)扳低，之后就再也不進(jìn)行任何操作了。如果有某個囚犯收集到了 100 個小球，顯然他就知道所有人都來過房間了。問題的關(guān)鍵就是：為什么最終總會有一個人能集齊所有的小球？

其實，協(xié)議中的很多復(fù)雜的細(xì)節(jié)都是為了保證下面這個引理成立：每一個人離開房間之后，房間里都只可能有兩種情況：

A. 蹺蹺板兩側(cè)的人一樣多

B. 高的那邊多一個人

這是因為，如果有囚犯第一次進(jìn)入房間，他將坐上低的那一側(cè)，并把那一側(cè)扳高，于是原本是情況 A 現(xiàn)在就會變成情況 B ，而情況 B 則會變成情況 A ；另外，如果有囚犯下了蹺蹺板，高的那一側(cè)將少一人，同時該側(cè)將被扳低，同樣有情況 A 將變情況 B ，情況 B 將變情況 A 。

現(xiàn)在，讓我們假設(shè)所有人都進(jìn)過房間了，并且有 k 個人正在蹺蹺板上(其余的人都已經(jīng)離開蹺蹺板了)。由于蹺蹺板兩側(cè)最多差一人，因此當(dāng) k 大于 1 時，蹺蹺板兩側(cè)都是有人的。而由于每個人都進(jìn)過房間了，因此不會有新的人坐上蹺蹺板了。此時，位于高處的人將不斷拿出自己的球，并被位于低處的人取走。直到某個時刻高處有人拿不出小球了，他將走下蹺蹺板，此時蹺蹺板的狀態(tài)才會發(fā)生變化，蹺蹺板上的總?cè)藬?shù)將變成 k-1 。最后蹺蹺板上只剩一個人時，顯然他就擁有了所有人的小球，此時他就知道所有人都來過了。

容易想到，如果初始時房間的狀態(tài)不定，人手兩個球的改進(jìn)方法同樣能解決問題。當(dāng)然，對問題的探索是永無止境的，我們相信囚犯與燈泡的問題還會有更多漂亮的變種和擴展，不斷啟發(fā)著人們的思維。即使這些問題沒有任何使用價值，思考過程本身也是有益而有趣的。讓我們感謝最初設(shè)計這個智力趣題的無名氏，他給我們帶來了無盡的思維樂趣。

總結(jié)

以上是生活随笔為你收集整理的程序设计囚犯与灯泡 C语言代码,100个囚犯和灯泡的那些事儿（下）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。