在場的所有人都將目光放在我身上。
真不習慣這樣被看著。
「首先,我們先將問題簡化,假設現在不是十人,而是只有兩人,那這兩人該在不知對方號碼的情況下比較號碼?」
遇到一些比較複雜的問題,最重要的是先從簡單的狀況開始,也就是所謂的分而治之(divide and conquer)。
當然,在場沒有人回答我的問題。
我一邊說一邊在紙上寫上10、20、30…一直寫到210。
「假設主辦方的編號是根據人數編排,那這樣寫到210就差不多了。現在假設有兩個人A和B,A的編號為55而B的編號為165,那A該怎樣跟B比較呢?答案就是箱子和鎖匙。」
在紙上寫完20個編號後,接著我在紙上也畫了20個O和20個X。
「如果A的編號為55的話,那他要做的就是在比這號碼小的編號放X,反之比這編號大的則放上O:
10 |
20 |
30 |
40 |
50 |
60 |
70 |
80 |
90 |
100 |
110 |
120 |
130 |
140 |
150 |
160 |
170 |
180 |
190 |
200 |
210 |
X |
X |
X |
X |
X |
O |
O |
O |
O |
O |
O |
O |
O |
O |
O |
O |
O |
O |
O |
O |
O |
要注意的是整個過程A要在沒人看到的情況下做,並且要將編號蓋上O和X,讓人只能看到編號看不到底下的內容。
當A完成了後,讓B獨自走到編號堆找出自己的號碼,由於B不應該看到號碼下面的內容,所以他的視覺應該只會是:
10 |
20 |
30 |
40 |
50 |
60 |
70 |
80 |
90 |
100 |
110 |
120 |
130 |
140 |
150 |
160 |
170 |
180 |
190 |
200 |
210 |
B在上面的例子是165,那他就只需要找出剛好比這個號碼小的,也就是160並且給大家看的時候需要翻起來,那這樣大家便看不到B的號碼,只看得到是O和X,根據定義如果是O的話就是比A大,可是如果是X的話便有兩種情況,一是真的比A小,二是有機會是處於同一個範圍,舉個例B如果是56號的話就會有這樣的情況。所以如果B第一次翻出來的是X,那他需要再翻一次剛好比他號碼大的,如果也是X就證明A的號碼是真的比B大,但如果是O的話也就證明A和B都處於同一個區間。當然真的發生這種事情後,我們也可以再做一次相同的測試,只是這次的測試編號會是50、51、52到60。」
在場的所有人看我說完後都反應不過來,只有琳是第一個舉手提問。
「如果B在找號碼時偷看其他號碼怎麼辦?」
「所以必須要有找號碼時的共識,像是選號碼時B必須要拍在桌上讓其他人知道他選好了,並與此同時除非B處於同範圍的情況,不然不能讓他再接觸其他號碼,依我看這裡的人想刻意申報其他人的應該比較少甚至沒有,大多數只是為了自保而已。」
「原、原來如此,可是這只是在說兩人的情況吧,如果是多人又怎麼辦?」
「關於這個,我們要先學會怎樣排序。」
接著我又在白紙上開始畫起來。
「首先,我假設現在有十個沒排好的數字,像是這樣:
10 |
8 |
7 |
1 |
2 |
4 |
5 |
3 |
9 |
6 |
如果是最簡單從大至少排列的方法,我們可以先從左至右每一對號碼比較,也就是說:
10 |
8 |
7 |
1 |
2 |
4 |
5 |
3 |
9 |
6 |
10和8比,10比較大當然就這樣不變。
10 |
8 |
7 |
1 |
2 |
4 |
5 |
3 |
9 |
6 |
8和7也一樣,所以也放著不動。
10 |
8 |
7 |
1 |
2 |
4 |
5 |
3 |
9 |
6 |
7和1同樣也是7比較大,所以不用管。
10 |
8 |
7 |
2 |
1 |
4 |
5 |
3 |
9 |
6 |
可是到這裡,由於2比1大,所以我們要將這對號碼調換。
10 |
8 |
7 |
2 |
1 |
4 |
5 |
3 |
9 |
6 |
現在1和4也需要調換,如此一直做下去。
10 |
8 |
7 |
2 |
4 |
5 |
1 |
3 |
9 |
6 |
10 |
8 |
7 |
2 |
4 |
5 |
3 |
1 |
9 |
6 |
10 |
8 |
7 |
2 |
4 |
5 |
3 |
9 |
1 |
6 |
10 |
8 |
7 |
2 |
4 |
5 |
3 |
9 |
6 |
1 |
如此一來,我們就完成第一輪,然後再重複一次這樣的過程,從第一輪的結果開始。
10 |
8 |
7 |
2 |
4 |
5 |
3 |
9 |
6 |
1 |
10 |
8 |
7 |
2 |
4 |
5 |
3 |
9 |
6 |
1 |
10 |
8 |
7 |
2 |
4 |
5 |
3 |
9 |
6 |
1 |
10 |
8 |
7 |
2 |
4 |
5 |
3 |
9 |
6 |
1 |
10 |
8 |
7 |
4 |
2 |
5 |
3 |
9 |
6 |
1 |
10 |
8 |
7 |
4 |
5 |
2 |
3 |
9 |
6 |
1 |
10 |
8 |
7 |
4 |
5 |
3 |
2 |
9 |
6 |
1 |
10 |
8 |
7 |
4 |
5 |
3 |
9 |
2 |
6 |
1 |
10 |
8 |
7 |
4 |
5 |
3 |
9 |
6 |
2 |
1 |
10 |
8 |
7 |
4 |
5 |
3 |
9 |
6 |
2 |
1 |
接著,我們再用第二輪的結果再做一遍。
10 |
8 |
7 |
4 |
5 |
3 |
9 |
6 |
2 |
1 |
10 |
8 |
7 |
4 |
5 |
3 |
9 |
6 |
2 |
1 |
10 |
8 |
7 |
4 |
5 |
3 |
9 |
6 |
2 |
1 |
10 |
8 |
7 |
5 |
4 |
3 |
9 |
6 |
2 |
1 |
10 |
8 |
7 |
5 |
4 |
3 |
9 |
6 |
2 |
1 |
10 |
8 |
7 |
5 |
4 |
9 |
3 |
6 |
2 |
1 |
10 |
8 |
7 |
5 |
4 |
9 |
6 |
3 |
2 |
1 |
10 |
8 |
7 |
5 |
4 |
9 |
6 |
3 |
2 |
1 |
10 |
8 |
7 |
5 |
4 |
9 |
6 |
3 |
2 |
1 |
再一次。
10 |
8 |
7 |
5 |
4 |
9 |
6 |
3 |
2 |
1 |
10 |
8 |
7 |
5 |
4 |
9 |
6 |
3 |
2 |
1 |
10 |
8 |
7 |
5 |
4 |
9 |
6 |
3 |
2 |
1 |
10 |
8 |
7 |
5 |
4 |
9 |
6 |
3 |
2 |
1 |
10 |
8 |
7 |
5 |
9 |
4 |
6 |
3 |
2 |
1 |
10 |
8 |
7 |
5 |
9 |
6 |
4 |
3 |
2 |
1 |
10 |
8 |
7 |
5 |
9 |
6 |
4 |
3 |
2 |
1 |
10 |
8 |
7 |
5 |
9 |
6 |
4 |
3 |
2 |
1 |
10 |
8 |
7 |
5 |
9 |
6 |
4 |
3 |
2 |
1 |
再一次。
10 |
8 |
7 |
5 |
9 |
6 |
4 |
3 |
2 |
1 |
10 |
8 |
7 |
5 |
9 |
6 |
4 |
3 |
2 |
1 |
10 |
8 |
7 |
5 |
9 |
6 |
4 |
3 |
2 |
1 |
10 |
8 |
7 |
9 |
5 |
6 |
4 |
3 |
2 |
1 |
10 |
8 |
7 |
9 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
8 |
7 |
9 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
8 |
7 |
9 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
8 |
7 |
9 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
8 |
7 |
9 |
6 |
5 |
4 |
3 |
2 |
1 |
再一次。
10 |
8 |
7 |
9 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
8 |
7 |
9 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
8 |
9 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
8 |
9 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
8 |
9 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
8 |
9 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
8 |
9 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
8 |
9 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
8 |
9 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
再一次。
10 |
8 |
9 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
我們只要一直做到不會有任何調動,那就可以確保我們的編號全部都是順序。
實際上這個方法我們不需要知道實際的數字,只需要知道兩個人的編號誰比較大誰比較小就可以。」
當然,這個方法也不是我創造的,這是所謂的泡沫排序(bubble sort)。
要問有沒有其他更好的排序方法,答案是肯定的,但現在不是授課時間,重點是讓他們容易理解並實際執行起來。
「誒,居然還可以這樣!」
看到我寫滿的白紙,琳露出驚訝的表情。
其他人也跟琳的反應差不多似懂非懂的樣子。
「不管你們有沒有理解這裡面的原理,但照著方法做總也可以吧?」
畢竟他們看到最後的結果確實有成功將次序排起來,自然也不會質疑我的說法,那麼接下來就是冗長又繁複的執行時間了。
……
……
***
作者後記:
貴安,MPL的說。要說泡沫排序的缺點,那答案當然是慢吧,舉個例如果一開始的順序是完全相反的,那最壞就需要排序N*N次了,希望不會太難懂。硬要補充的話,這個不知道對方的資訊卻能驗證對方的方法很多時候應用在KYC(know your customers)上,一個最簡單的例子就是銀行可能會想不知道你的確實資產的情況下而確認你的還款能力。最後,覺得不錯請給個GP、留言,還沒訂閱的就訂閱,這樣就能將我的好感度刷好刷滿。那麼,後會有期。