- 相關(guān)推薦
一道面試題及其推廣過橋問題
一、問題
在漆黑的夜里，四位旅行者來到了一座狹窄而且沒有護(hù)欄的橋邊。如果不借助手電筒的話，大家是無論如何也不敢過橋去的。不幸的是，四個(gè)人一共只帶了一只手電筒，而橋窄得只夠讓兩個(gè)人同時(shí)過。如果各自單獨(dú)過橋的話，四人所需要的時(shí)間分別是1、2、5、8分鐘;而如果兩人同時(shí)過橋，所需要的時(shí)間就是走得比較慢的那個(gè)人單獨(dú)行動時(shí)所需的時(shí)間。問題是，如何設(shè)計(jì)一個(gè)方案，讓這四人盡快過橋。
假設(shè)這四人分別為A、B、C、D。很明顯，開始兩人拿著手電筒過橋后，手電筒就在橋的另一邊了，此時(shí)需要已經(jīng)過橋的那兩人中的一個(gè)再把手電筒送回橋這邊。送手電筒回來過橋也要化時(shí)間，所以要選一個(gè)跑得比較快的。一個(gè)很自然的想法就是，每次讓跑得最快的A陪著另一個(gè)過橋，然后A快速地跑回來，再陪下一位過去，最后所有人就都可以過橋了。
讓我們來算一下這要多長時(shí)間。為了方便起見，我們把旅行者出發(fā)的橋的這一邊稱為“此岸”，而把旅行者想要到達(dá)的那邊叫“彼岸”。在表達(dá)一個(gè)過橋方案時(shí)，我們用“←”來表示從彼岸到此岸的移動，用“→”表示從此岸到彼岸的移動。前面“A護(hù)送大家過河”的方案就可以寫成：(右邊數(shù)字為完成此步驟所需時(shí)間)
A B → 2
A ← 1
A C → 5
A ← 1
A D → 8
一共就是2+1+5+1+8=17分鐘。
但其實(shí)有更快的辦法：
A B → 2
A ← 1
C D → 8
B ← 2
A B → 2
一共是2+1+8+2+2=15分鐘。這個(gè)辦法的聰明之處在于讓兩個(gè)走得最慢的人同時(shí)過橋，這樣花去的時(shí)間只是走得最慢的那個(gè)人花的時(shí)間，而走得次慢的那位就不用另花時(shí)間過橋了�？梢园阉锌赡艿姆桨付剂信e一遍，就會發(fā)現(xiàn)這是最快的方案了。
現(xiàn)在我們把這個(gè)問題推廣到N(N≥4)個(gè)人過橋的情況：如果有N個(gè)旅行者，假設(shè)他們有各自所需的過橋時(shí)間(正實(shí)數(shù))。在只有一只手電筒的情況下，要過上述的一條橋，怎樣才能找到最快的過橋方案?
假設(shè)最快地把N個(gè)旅行者從此岸移動到彼岸需要f分鐘時(shí)間，那么我們把所有在f分鐘時(shí)間內(nèi)把N個(gè)旅行者從此岸移動到彼岸的方案稱為“最佳方案”。最佳方案很有可能不止一個(gè)，我們的目的是要找到一個(gè)最佳方案，但是并不需要把所有的最佳方案全都找出來。
二、一個(gè)合理的假設(shè)
為了討論的方便起見，這一節(jié)我們要說明的是，事實(shí)上我們可以假設(shè)每個(gè)旅行者的速度都是不一樣的。這樣當(dāng)我們說一些人中“最快的那個(gè)”，“次慢的那一個(gè)”時(shí)，都不會有歧義了，因?yàn)槊總�(gè)人的速度都是獨(dú)一無二的。這個(gè)假設(shè)在討論中并非必要，只是為了在證明的敘述過程中避免不斷地嗦類似“我們讓兩人中最快的那個(gè)過橋，如果兩人一樣快，那就隨便選一人”、“我們選在彼岸最快的那個(gè)人回來，如果上一步剛從此岸到彼岸的人中，其中有一個(gè)是現(xiàn)在彼岸走得最快的之一，我們就特別選擇讓他回來”之類的話。
為什么我們可以假設(shè)每個(gè)旅行者的速度都是不一樣的?原理就在于，我們可以把原來過橋時(shí)間相同的旅行者的過橋時(shí)間分別加上一個(gè)不同的但是非常非常小的量，這樣就能保證旅行者的速度是不一樣的了。但是因?yàn)榧由先サ牧慷挤浅Ｐ�，所以對最終總的過橋時(shí)間的影響也非常小。所以這樣改動過后得到的最佳方案在原來的條件下實(shí)施的話，也該是原來?xiàng)l件下的最佳方案。
如果你對上面的說明滿意了，就完全可以跳過這一節(jié)直接看第三節(jié)。這一節(jié)后面哩叭嗦的都是為了向一些對嚴(yán)格性要求比較高的朋友解釋上面所說的方法的確可行。
首先對于任何一組N個(gè)旅行者，假定他們過橋所需的時(shí)間分別為a1、a2、……、aN，它們都是大于零的實(shí)數(shù)。假設(shè)這個(gè)序列已經(jīng)從小到大排列了(當(dāng)然不排除其中有數(shù)相等)。每次都由第一個(gè)旅行者陪同一個(gè)人過橋，然后第一個(gè)旅行者回來，這樣一個(gè)方案所需要的時(shí)間是：
S = (N-2)*a1+a2+……+an
(第一個(gè)旅行者要返回N-2次)。所以最佳方案所需要的時(shí)間一定不會比S大。
我們把一個(gè)過橋方案中讓一個(gè)或者兩個(gè)人拿著手電筒從橋的一邊走到另一邊的一次移動叫做這個(gè)方案中的一次移動或者“一步”，就是前面解四個(gè)人的題中使用“→”或“←”來表示的一個(gè)步驟。因?yàn)橐淮我苿铀枰淖钌俚臅r(shí)間是a1分鐘，所以最佳方案中所需的移動步數(shù)一定不會多于K=[S/a1]步，這里"[]"是取整運(yùn)算。
讓我們考慮一下所有在K步以內(nèi)完成的方案。上面的例子表明這樣的方案至少有一個(gè)，而且這樣的方案顯然只有有限多個(gè)，假設(shè)一共有M個(gè)。我們又設(shè)這些方案執(zhí)行時(shí)要花的時(shí)間是
t1、t2、……、tM
我們還可以假設(shè)上面這些時(shí)間已經(jīng)從小到大排列了，t1就是最佳方案所需要的時(shí)間。
現(xiàn)在是關(guān)鍵的步驟。我們要選取一個(gè)很小的正實(shí)數(shù)ε>0。它有多小呢?它必須滿足下面的條件：
1) 對于任何兩個(gè)過橋時(shí)間不同的旅行者(假設(shè)他們的過橋時(shí)間是a和b分鐘)，必須滿足ε<|a-b|/N。換句話說，Nε要小于不同的旅行者過橋時(shí)間之間的差別。
2) 對于任何兩個(gè)所需的完成時(shí)間不同的K步以內(nèi)的方案(假設(shè)它們的所需時(shí)間是t和s分鐘)，必須滿足ε<|t-s|/K。換句話說，Kε要小于不同的方案完成時(shí)間之間的差別。
因?yàn)槁眯姓叩臄?shù)目和方案的數(shù)目都是有限的，所以我們必然可以選取這樣一個(gè)ε。至于這兩個(gè)條件有什么用，我們馬上就可以看到。
假設(shè)若干個(gè)旅行者過橋的時(shí)間都是一樣的a分鐘，我們就把題目改一下，使得他們的過橋時(shí)間分別為
a、a+ε/N、a+2ε/N、a+3ε/N……
如果有其他的旅行者過橋時(shí)間相互一樣，也按照同樣方式修改題目。這時(shí)在修改后的題目中，如果原來兩個(gè)旅行者所需的過橋時(shí)間相同，那么現(xiàn)在就變得不同，差一個(gè)非常小的量(不會超過ε);如果原來兩個(gè)旅行者所需的過橋時(shí)間不同，那么根據(jù)上面的條件1)，現(xiàn)在還是不同，而且原來誰比較快，現(xiàn)在仍舊是他比較快。
我們看看這個(gè)修改后的題目的最佳方案和原來的題目的最佳方案有什么聯(lián)系。
假設(shè)我們已經(jīng)有一個(gè)關(guān)于修改后的題目的最佳方案，那么它所需要的時(shí)間必定是這個(gè)模樣的：
a + bε
我們知道bε部分是修改時(shí)把旅行者過橋時(shí)間“微調(diào)”了以后造成的，而且每走一步這部分的改變不會超過ε，所以我們有0
如果我們把這個(gè)最佳移動方案照搬到原來的題目中去，所需要的時(shí)間就是a分鐘。這個(gè)方案應(yīng)該同樣是原來題目中的最佳方案。否則的話，假設(shè)我們有另一個(gè)方案，所需時(shí)間為a，而且a
a < a + Kε
把這個(gè)耗時(shí)a的方案搬到改動過的題目里去的話，所需的時(shí)間就會是
a + bε
其中0
a + bε < a + bε
這就和a+bε是改動后題目的最佳方案所需的時(shí)間矛盾了。
所以只要找到一個(gè)修改過的題目中的最佳方案，我們就得到了原來題目中的一個(gè)最佳方案，于是我們只要考慮所有旅行者的速度都不同的題目就可以了。
三、一個(gè)“很顯然”的結(jié)論
編個(gè)計(jì)算機(jī)程序，把所有步數(shù)少于上一節(jié)中所計(jì)算的K=[S/a1]的可能的過橋方案都列舉一遍，然后找出最快的，當(dāng)然是一種方法，這理論上也是可行的，因?yàn)樯儆贙步的方案只有有限多個(gè)，計(jì)算機(jī)程序必定能夠?qū)⑺鼈內(nèi)苛信e出來。只是當(dāng)人數(shù)N增大時(shí)，過橋方案數(shù)會增加得很快。事實(shí)上，如果我們只考慮“每次過去兩個(gè)人，然后這兩個(gè)人中其中一個(gè)人回來”這類方案的數(shù)目的數(shù)量就已經(jīng)遠(yuǎn)遠(yuǎn)超過N!個(gè)了，想像一下如果N=1000的話所需要的計(jì)算量!況且還有更多數(shù)量的其他類型方案。特別是，我們是在做智力題，不是在學(xué)編程。當(dāng)然你還可以說，如果人多的話，所需要的時(shí)間超過了12小時(shí)，那時(shí)天已經(jīng)亮了，不再需要手電筒，大家可以直接過橋唉!我們是在做智力題，不是在做抬杠式的腦筋急轉(zhuǎn)彎我們可以假設(shè)是在有漫長極夜的極地嘛，要不然，這橋是在一個(gè)黑暗山洞里，就象電影《指環(huán)王》中的那樣……
但是如果不用列舉法的話，我們有一個(gè)重要的任務(wù)要做，就是不僅要說明如何找到一個(gè)我們自以為最快的方案，而且還要證明這樣的方法的確給出了一個(gè)最佳方案。
在我們的直覺當(dāng)中，最快的方案必然有這樣一個(gè)特征：每次過橋去彼岸的一定是兩個(gè)人，然后一定只有一個(gè)人把手電筒送回此岸(當(dāng)然要除去最后一次過橋的情況，那時(shí)就不需有人把手電筒送回來了)。但是為什么一定是這樣的呢?為什么不可能有一個(gè)意想不到的巧妙方案，在那里有某一步居然需要一個(gè)人單獨(dú)過到彼岸去，或者需要有兩個(gè)人把手電筒送回此岸來?這是個(gè)看起來很顯而易見但是我們不能支吾不回答的問題。
在討論中我們經(jīng)常需要說明，在某一時(shí)刻，橋的兩邊分別有哪些人，手電筒又在哪一邊。這樣的說明稱為一個(gè)“局面”。當(dāng)然，一個(gè)局面必須是合理的。比如說，不能夠所有人都在橋的一邊，而手電筒卻在橋的另一邊;一個(gè)人必須處在橋的某一邊，而且只能處在橋的某一邊。
比如說，在四個(gè)旅行者的問題里，如果某一個(gè)時(shí)刻A、B和C在此岸，而D在彼岸，手電筒也在彼岸，這就給出了一個(gè)局面(這個(gè)局面看起來有點(diǎn)奇怪，大概是D拿著手電筒一個(gè)人跑過橋去了，接下去除了他再拿著手電筒回來別無它法)。所有人和手電筒都在此岸，就是一個(gè)特殊的局面，叫作初始局面;而所有人和手電筒都在彼岸，也是一個(gè)特殊的局面，叫完結(jié)局面;所有其他的局面我們稱為中間局面。
想像一下現(xiàn)在有兩種局面。在兩種局面中，手電筒都在橋的同一邊(都在此岸或都在彼岸);而且在第一種局面里所有在彼岸的旅行者，在第二種局面里也都在彼岸，而且有這樣的旅行者，在第一種局面中他在此岸，而第二種局面中他在彼岸。那么我們就說第二種局面“優(yōu)于”第一種局面。
比如說，在四個(gè)旅行者的問題里，第一種局面是A、B和C在此岸，而D在彼岸，手電筒也在彼岸;第二種局面是A和B在此岸，C和D在彼岸，手電筒也在彼岸。那么第二種局面就優(yōu)于第一種局面。很顯然，除了初始
[一道面試題及其推廣過橋問題]相關(guān)文章：
2.關(guān)于java基本數(shù)據(jù)類型的五道面試題
【一道面試題及其推廣過橋問題】相關(guān)文章：
一道騰訊的面試題07-09
一道經(jīng)典的面試題分享07-13
JAVA面試題（問題）07-13
一道前端JS面試題，求解？07-13
一道Java面試題，題目如下07-11
一道面試問題07-11
《求職必知》一道經(jīng)理面試題07-13
java面試題:文件讀取問題.07-13