第三題是約瑟夫(Joseph)環(huán)問(wèn)題，一看很高興啊。以前在Poj上做過(guò)，而且在Baidu比賽還做過(guò)變種的約瑟夫問(wèn)題。很順利的寫了出來(lái)，給出遞歸和循環(huán)兩種解決方法。第四題給出一個(gè)PI/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 ……的公式要求寫一個(gè)求PI的程序精確到小數(shù)點(diǎn)后500位。按這個(gè)要求應(yīng)該是讓自己寫個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)高精度。在我看來(lái)在考試期間完成是 mission impossible。 第五題是挖石油的放棄了。

今天去斯倫貝謝BGC參加筆試，感覺(jué)BGC并不太考技術(shù)細(xì)節(jié)，側(cè)重考察思維能力和英語(yǔ)表達(dá)能力。一道設(shè)計(jì)題，一道名詞解釋題，一道算法題，一道智力題，一道跟石油相關(guān)的半開(kāi)放問(wèn)題，好壞不知。

筆試在9點(diǎn)半。試題比較有意思，最后一題讓設(shè)計(jì)一個(gè)海底甲烷水合物開(kāi)采方案，我想到用循環(huán)熱水管道，在海底把固體礦物質(zhì)加熱使甲烷逸出，甲烷再隨著水循環(huán)上升到海面上。對(duì)于這個(gè)創(chuàng)意我自己還比較得意，但估計(jì)人家看了就覺(jué)得可笑了。

斯倫貝謝軟件筆試題

每個(gè)公司的軟件題目應(yīng)該都是其在實(shí)際工作當(dāng)中會(huì)遇到的問(wèn)題，這道斯倫貝謝的算法題我猜測(cè)應(yīng)該也是如此。題目是09屆畢業(yè)生招聘時(shí)出的，如下：

現(xiàn)在一個(gè)廣場(chǎng)上有一些木樁，可以知道這些木樁的坐標(biāo)。給你一根很長(zhǎng)的繩子，繞成一圈，將所有木樁都繞在里面。之后收緊繩子，直到其緊繃。此時(shí)有木樁與繩子接觸，另外一些木樁則是在繩子繞成的圈的內(nèi)部。 我們將與繩子接觸的木樁稱作頂點(diǎn)，請(qǐng)編寫程序，求出這些木樁中的頂點(diǎn)。

這道題目其實(shí)不難，諸位讀者可以思考一下，再看我給的解決方案。另外提醒一下，木樁的坐標(biāo)是人定的，我們可以將木樁的坐標(biāo)統(tǒng)一定在第一象限。

以下是這個(gè)問(wèn)題的解答，我只給出算法大體流程，但不給出具體代碼。

我們的輸入是一個(gè)數(shù)組，這個(gè)數(shù)組中包含所有木樁的坐標(biāo)，即一個(gè)POINT。

第一步，找出這些點(diǎn)中，位于最下方，即Y坐標(biāo)值最小的點(diǎn)，我們稱之為木樁A

我們以A點(diǎn)作為基準(zhǔn)點(diǎn)進(jìn)行下一步分析。找出逆時(shí)針?lè)较虻南乱粋�(gè)頂點(diǎn)。這個(gè)頂點(diǎn)的尋找方向，必然是先找右上方，如果右上方?jīng)]有點(diǎn)，則找左上方。

在右上方，下一個(gè)頂點(diǎn)必然是與A相連，斜率最小的點(diǎn)。如果右上方?jīng)]有點(diǎn)，那么我們需要從左上方查找斜率也是最小的一個(gè)點(diǎn)。這一點(diǎn)讀者可以在紙上畫圖查證。

按照這種方法，我們很容易找到逆時(shí)針的下一個(gè)點(diǎn)，我們稱之為B點(diǎn)，現(xiàn)在從B點(diǎn)查找B點(diǎn)的逆時(shí)針下一個(gè)頂點(diǎn)。對(duì)于B點(diǎn)來(lái)說(shuō)，我們也需要先查找右上方，如果右上方?jīng)]有木樁，則查找左上方，左上方?jīng)]有，則需要查找左下方，如果左下方?jīng)]有，那就需要查找右下方。按照此次序依次查找。

對(duì)于右上方有木樁的情形，我們需要找到與B點(diǎn)相連斜率最小的木樁。

右上方無(wú)木樁，左上方有木樁的情形，我們需要查找左上方中，與B相連斜率最小的木樁。

對(duì)于左下方的情形，我們需要查找與B相連斜率最小的木樁。

對(duì)于右下方的情形，我們需要查找與B相連斜率最小的木樁。

雖然都是查找斜率最小，但我們需要依次比較四種情況，而不能混在一起查找。

按照這種方法，我們可以找到C點(diǎn)。

重復(fù)由B找到C的步驟，我們可以找到C的逆時(shí)針下一個(gè)頂點(diǎn)，依次查找，則可以找出所有頂點(diǎn)。這里還需要注意一點(diǎn)，我們需要保存上一次的斜率，本次查找時(shí)的斜率必須比上一次查找時(shí)的斜率大，或者本次查找的下一個(gè)頂點(diǎn)的位置，位于四個(gè)方位中的下一個(gè)方位。

這個(gè)方法很簡(jiǎn)單，但效率很低，每次查找，都需要計(jì)算出當(dāng)前頂點(diǎn)與其他所有點(diǎn)的斜率，并進(jìn)行分類排序比較。