李振夏

摘要 上個(gè)世紀(jì)，大科學(xué)家愛(ài)因斯坦提出了一道非常經(jīng)典的邏輯題“誰(shuí)在養(yǎng)魚”？這是一道很非常經(jīng)典的智力題，據(jù)愛(ài)因斯坦說(shuō)，全世界只有大約2%的聰明人，能夠推得出這個(gè)問(wèn)題的答案。在沒(méi)有計(jì)算機(jī)的年代，相信普通人看到這個(gè)問(wèn)題無(wú)從下手，聰明者基本都是以表格的方式來(lái)推導(dǎo)。計(jì)算機(jī)出現(xiàn)后很多依靠人腦無(wú)法完成的事情可以變得順利成章了。本文要介紹的方法就是這樣：以窮舉法來(lái)破解這道題。

【關(guān)鍵詞】愛(ài)因斯坦 窮舉法 Java編程 排列組合 長(zhǎng)郡中學(xué)

1 問(wèn)題描述

上個(gè)世紀(jì)，大科學(xué)家愛(ài)因斯坦提出了一道非常經(jīng)典的邏輯題，題目的內(nèi)容是這樣的：在一條街上有五個(gè)不同顏色的房間排成一排，每個(gè)房間里分別住著一個(gè)不同國(guó)籍的人，每個(gè)人都喝一種特定品牌的飲料，抽一種特定品牌的煙，養(yǎng)一種寵物，沒(méi)有任意兩個(gè)人抽相同品牌的香煙，或喝相同品牌的飲料，或養(yǎng)相同的寵物，又知：

（1）英國(guó)人住在紅房子里。

（2）瑞典人養(yǎng)狗。

（3）丹麥人喝茶。

（4）綠房子緊挨著白房子，在白房子的左邊。

（5）綠房子的主人喝咖啡。

（6）抽PALL MALL牌香煙的人養(yǎng)鳥。

（7）黃房子里的人抽DUNHILL牌的煙。

（8）住中間房子的人喝牛奶。

（9）挪威人住在第一個(gè)房子里（最左邊）。

（10）抽BLENDS香煙的人和養(yǎng)貓的人相鄰。

（11）養(yǎng)馬的人和抽DUNHILL牌香煙的人相鄰。

（12）抽BLUEMASTER牌香煙的人喝啤酒。

（13）德國(guó)人抽PRINCE牌香煙。

（14）挪威人和住藍(lán)房子的人相鄰。

（15）抽BLENDS牌香煙和喝礦泉水的人相鄰。

問(wèn)題：誰(shuí)在養(yǎng)魚？

2 解題思路

就這道題來(lái)說(shuō)，窮舉法是最直接也是容易讓人理解的方法。所謂窮舉法的基本思想是根據(jù)題目的部分條件確定答案的大致范圍，并在此范圍內(nèi)對(duì)所有可能的情況逐一驗(yàn)證，直到全部情況驗(yàn)證完畢。若某個(gè)情況驗(yàn)證符合題目的全部條件，則為本問(wèn)題的一個(gè)解;若全部情況驗(yàn)證后都不符合題目的全部條件，則本題無(wú)解。就本道題而言肯定就只有一個(gè)答案。

在正式計(jì)算之前，需要先來(lái)討論一下答案的形式和范圍。就這套題而言，有五個(gè)房子（在面向?qū)ο蟮某绦蛑蟹Q為實(shí)體），每個(gè)房子從左到右依次排列，每個(gè)房子有個(gè)序號(hào)分別從O到4（在這里就按照程序的思維來(lái)進(jìn)行，從O開始進(jìn)行編號(hào)），每個(gè)房子分別有五個(gè)屬性：房屋的顏色（以下簡(jiǎn)稱顏色）、居住者的國(guó)籍（以下簡(jiǎn)稱國(guó)籍）、居住者的喜愛(ài)的飲料（以下簡(jiǎn)稱飲料）、居住者喜歡的香煙（以下簡(jiǎn)稱香煙）、居住者養(yǎng)的寵物（以下簡(jiǎn)稱寵物）。這五個(gè)屬性每種屬性有5個(gè)值，那么一共有多少個(gè)可能的解呢？為了弄清這個(gè)問(wèn)題，讓我們先從一個(gè)屬性來(lái)分析，假設(shè)單單就顏色來(lái)說(shuō)，總共5中顏色，分給5套房子，有多少中可能性呢？在學(xué)了數(shù)學(xué)的排列定理后，我們知道這里其實(shí)就是一個(gè)排列組合問(wèn)題：

就顏色的來(lái)說(shuō)，實(shí)際上就是5的全排列。可能的組合數(shù)為：5*4*3*2*1=120種排列方式。知道了就一種屬性來(lái)說(shuō)有120種可能性，那么就5個(gè)屬性來(lái)說(shuō)，他們的可能組合數(shù)為120*120*120*120*120= 24883200000個(gè)可能的解（這么龐大的數(shù)字，如果不做優(yōu)化就人來(lái)說(shuō)幾乎就是不可能完成的）。

了解了解題思路后，接下來(lái)要做的就是分別對(duì)顏色、國(guó)籍、飲料、香煙和寵物計(jì)算出每個(gè)屬性的所有可能的排列組合并將這些組合放到5個(gè)數(shù)組里面，然后再用多層循環(huán)的方式，從每個(gè)數(shù)組中取出一個(gè)組合進(jìn)行校驗(yàn)：其實(shí)簡(jiǎn)單，具體如何校驗(yàn)?zāi)?？題中的15調(diào)線索，每條就是一個(gè)校驗(yàn)規(guī)則。

3 解題算法

3.1 數(shù)據(jù)初始化

聲明5各列表，每個(gè)列表中依次放入相關(guān)的選項(xiàng)

private static List nationalities;

private static List houseColors;

private static List drinks;

private sratic List smokings;

private sratic List pets;

static{

//初始化數(shù)據(jù)

nationalities= Arrays.asList（“英國(guó)”，“瑞典”，“丹麥”，“挪威”，“德國(guó)”）;

houseColors= Arrays.asList（“紅”，“綠”，“白”，“黃”，“藍(lán)”）;

drinks= Arrays.asList（“茶”，“咖啡”，“牛奶”，“啤酒”，“礦泉水”）;

smokings= Arrays.asList（"PALLMALL"， "DUNHILL"， "BLENDS"，”BLUEMASTER"， "PRINCE"）;

pets= Arrays.asList（“狗”，“鳥”，“馬”，“貓”，“魚”）;

）

3.2 排列組合的計(jì)算

就本題而言，一個(gè)最為核心和重要的就是如何算出一組數(shù)據(jù)的排列組合。設(shè)a、b、c、d、e五個(gè)數(shù)為一組，如何算出這5個(gè)組的所有排列組合的形式。根據(jù)假設(shè)對(duì)一個(gè)有n位的數(shù)組來(lái)說(shuō)，第一位有n種選擇，第2位有n.1種選擇，第一位和第二位的組合有n*（n-l）各，他們與3位的組合有n*（n-1）*（n-2）個(gè)。依次進(jìn)行遞歸前面n-l位與最后一位的組合只剩下一種形式，依次得出算法如下：

/{{

*求list中元素的所有排列組合

* @param list列表中的元素

* @return

*/

public static List list）{

List

List line=newArrayList（）;

permutarion（line， lisr， result）;

return result，

）

/**

*計(jì)算所有的排列組合

* @param line前面元素的組合

* @param remains剩余還沒(méi)有組合的元素

* @param result保存最終的計(jì)算結(jié)果，里面的每個(gè)list是一種組合形式

*/

private static void permutation（Listline， List remains， List

line= cloneList（line）;

remains= cloneList（remains）;

int size= remains.size（），

if （size==1）{∥如果只有一個(gè)元素，那么就只有直接用前面的組合跟這個(gè)元素進(jìn)行拼合

line.add（remains.get（0》;

result.add（line）;

return，

）

for （inti=0;i

String one= remains.get（i）;//取出某一個(gè)元素

Lisr remains2=without（remains， one）;//剔除該元素的列表

permutation（one， cloneList（line），remains2， result）;

）

）

*計(jì)算出某一個(gè)元素與前面組合的拼合結(jié)果

* @param one某個(gè)元素（下一個(gè)加入的元素）

* @param line需要加入的隊(duì)列（某個(gè)組合）

* @param remains2剩余的元素

* @param result存儲(chǔ)最終的結(jié)果

*/，

private static void permutation（Stringone， List Iine， List remains2，List

line= cloneList（line）;

line.add（one）;

permutation（line， remains2， result）;

）

3.3 規(guī)則檢驗(yàn)

有了上一小節(jié)的排列算法，我們可以每次先對(duì)房屋（或房屋主人的）國(guó)籍、顏色、飲料、香煙、寵物算出所有的排列組合，然后循環(huán)這些組合，每次針對(duì)這五個(gè)屬性各拿出一個(gè)組合進(jìn)行校驗(yàn)。題中的15條線索就是15個(gè)校驗(yàn)規(guī)則，我們需要針對(duì)每個(gè)規(guī)則完成一個(gè)檢查方法，某一組合符合所有的規(guī)則，那么就是正解。以第一個(gè)規(guī)則為例方法如下：

*檢查條件：英國(guó)人住在紅房子里。

* @param nationList國(guó)籍列表

* @param colorList房屋顏色

* @retum檢查通過(guò)返回true，否則返回false

private static boolean checkEnglishInRedHouse（List nationList， ListcolorList）{

int index= nationList.indexOf（“英國(guó)”）;∥獲得英國(guó)人做在的房屋序號(hào)

String color= colorList.get（index）;//獲得同一序號(hào)的房屋顏色

retum紅”equals（color）;

）

3.4 窮舉算法

在以上的算法的基礎(chǔ)，最終的窮舉算法如下：

public static void main（String[] args）{

List

List

List

List

List

index=O：

long beginTime=System.currentTimeMillis（）;

int size= nationPermutations.size（）;//

//以下針對(duì)每個(gè)屬性循環(huán)，檢驗(yàn)每個(gè)解

for （intn=O;n

List nationList=nationPermutations.get（n）;

for （int c=O;c

List colorLisr=colorPermutations.get（c）;

for （int d=O;d

List drinkList=drinkPermutations.get（d）;

for （inr s=O;s

List smokeList=smokePermutations.get（s）;

for （intp=0;p

Lisr petList=petPermutations.get（p）;

index++;

if （checkPass（narionLisr，colorList， drinkList， smokeList， petList》{

//檢驗(yàn)通過(guò)

System.out.println（"計(jì)算用時(shí)：”+ （System.currentTimeMillis（） -beginTime）+“毫秒”）;

printResult（nationList，colorList， drinkList， smokeList， petList）;

retum，

） else{

//System.outprintln（"error at”+index）;

）

}

}

）

）

）

System.out.println（”程序運(yùn)行結(jié)束！”）;

）

3.5 算法優(yōu)化

在上一小節(jié)中，依次用了5層循環(huán)來(lái)對(duì)檢驗(yàn)每個(gè)解，前面說(shuō)過(guò)這樣的解一共有24883200000個(gè)。這樣的數(shù)量對(duì)于計(jì)算機(jī)來(lái)說(shuō)運(yùn)算次數(shù)也還是非常大的。為了最大幅度的減少運(yùn)算次數(shù)，可以在外層循環(huán)中就逐步加入一些校驗(yàn)規(guī)則，篩選掉一些無(wú)用的解。大致如下：

for （intn=0;n

List nationLisr=nationPermutations.get（n）;

if（！ checkFirstHouseIsNorwegian（nationList》{//檢查第一間房是否是挪威人，這個(gè)只跟nationList有關(guān)系

continue，

}

for （int c=0;c

Lisr colorList=colorPermutations.get（c）;

if （！checkGreenLeftOfWhite（colorList》{∥檢查綠色房子是否在白色房子的左邊

contmue，

}

if（ ！checkEnglishInRedHouse（nationList， colorList》{//檢查英國(guó)人是否住紅色房子

contmue，

}

if（！ checkNearbyNorwegianWirhBlueHouse（nationList， colorList》{∥挪威人和住藍(lán)房子的人相鄰

contmue，

）

for （int d = 0;d

）

）

）

提前加入校驗(yàn)的原則就是，在某一層循環(huán)加入的校驗(yàn)算法只與前面幾層的屬性相關(guān)，這樣校驗(yàn)方法才能正常執(zhí)行。

3.6 計(jì)算結(jié)果

4 總結(jié)

采用窮舉法來(lái)解題的最直接的優(yōu)點(diǎn)就是直觀、便于理解。從缺點(diǎn)方面來(lái)說(shuō)，窮舉法最大的缺點(diǎn)就是通常計(jì)算量都很大，但本處解題由于對(duì)程序進(jìn)行了優(yōu)化，提早加入校驗(yàn)方法，已經(jīng)讓計(jì)算量大幅的降低，運(yùn)算效率大大提高。（程序查看和下載地址：https：//giteecom/lizhenxia/einstein）.

參考文獻(xiàn)

[1]張傳鵬.高考數(shù)學(xué)進(jìn)階特訓(xùn)[M]。浙江：浙江大學(xué)出版社，2016.

[2]白喜琇（韓）.狄利克雷教你學(xué)選擇和排列[M].安徽：黃山書社出版，2016.

[3]明日科技.Java從入門到精通（第4版）[M].北京：清華大學(xué)出版社，2016.

[4]宋娟.Java常用算法手冊(cè)（第3版）[M].北京：中國(guó)鐵道出版社，2016.

[5] Robert Sedgewick（美），KevlnWayne（美）著;謝路云譯，算法第4版Algorithms Fourth Edition[M].北京：人民郵電出版社，2012.