歡迎光臨
每天分享高質量文章

別亂說,演演算法才不是腦筋急轉彎


老崔去某廠筆試時,遇到了經典的「狼、羊、白菜 過河問題」,由於經常看演演算法方面的內容,這道對於他來說,so easy。

題目大概是這樣:

題目1:

農夫需要把狼、羊、菜和自己運到河對岸去,只有農夫能夠划船,而且船比較小,除農夫之外每次只能運一種東西,還有一個棘手問題,就是如果沒有農夫看著,羊會偷吃菜,狼會吃羊。

請考慮一種方法,讓農夫能夠安全地安排這些東西和他自己過河。


老崔回家,自信滿滿的和女友說這道題時,女友反問到:“為啥程式員面試要考腦筋急轉彎呀!?”

老崔這時認真起來,用理科生的嚴肅態度反駁女友:“這不是什麼腦筋急轉彎,這是道演演算法題,腦筋急轉彎都是小聰明的歪理,別搞錯了好不好~

如果你不是程式員,又堅持說上道題是腦筋急轉彎,那你再來看看這道題:

  題目2:

請你把10根放在籃子裡的香蕉分給10只猴子,每隻猴要得到一根,最後籃子裡還要留下一根香蕉,你能做到嗎?

不好意思地說,這道題是小學二年級的一道數學競賽題,給你一些時間,思索一下,這道題是不是更有腦洞大開的味道。

作為程式員,去大廠筆試時都會遇到演演算法題,有些是正經的題,有些則看上去就是用來坑你的。

題目3:

你讓一個工人為你工作七天,用一根金條作為報酬。金條被分成7小塊,可以每天支付一塊。

但是,如果你只能將金條切割兩次,那麼你如何切割金條,能滿足每天支付一塊給工人呢?

這題很簡單,並不需要什麼演演算法,其實是在考量你的數學思維。如果你把精力只用在處理金條上,並不考慮實際場景,那你就把自己坑了。

坦率地講,上面那些題都像是來搞笑的。下麵認真給出一些演演算法題:

題目4:

你有不限量的水,還有兩個水桶,容積分別是5升和3升。如何精確地稱量出4升水?

如果你有答案,那麼看看這道題的升級版:

題目5:

現在有三個容積分別是3升、5升和8升的水桶,其中容積為8升的水桶中裝滿了水,容積為3升和容積為5升的水桶是空的。

三個水桶都沒有體積刻度,現在需要將大水桶中的8升水等分成兩份,每份都是4升水,(附加條件是隻能使用另外兩個空水桶)

這道題不止一個方案,一共有多少種方案,桶與桶之間倒水的次數哪種方案最少?這就是一個演演算法題了。

類似這種水桶倒水的問題,確實是各個大廠筆試的常見題目,也是篩除小白程式員和演演算法工程師的關鍵題。

這道題答對了,月薪要40K,答不對就要4K。

如果用人類的思維方式,那麼解決這個問題的關鍵是怎麼透過倒水湊出確定的1升水或能容納1升水的空間,三隻水桶的容積分別是3、5和8,用這三個數做加減運算,可以得到很多組答案。

但是計算機並不能理解這個「1」的重要性,很難按照人類的思維方式按部就班地推導答案,因此用計算機解決這個問題,通常會選擇使用「窮舉法」。為什麼使用「窮舉法」呢?

因為這不是一個典型意義上的求解最優解的問題,雖然可能暗含了求解倒水次數最少的方法的要求,但就本質而言,常用的求解最優解問題的高效方法都不適用於此問題。

如果能夠窮舉解空間的全部合法解,然後透過比較找到最優解也是一種求解最優解的方法。

求解這個問題的演演算法本質上就是對狀態的窮舉搜尋。這樣狀態變化搜尋的結果通常是得到一棵狀態搜尋樹,根節點是初始狀態,葉子節點可能是最終狀態,也可能是某個無法轉換到最終狀態的中間狀態。

這裡並不細說了,如果你想弄清楚詳細的演演算法解決過程【在這裡查詢】。

靠演演算法題篩選人才

下麵梳理了演演算法面試時篩選人才時類似的關鍵題目,有些簡單的,有複雜的。

大家不妨先收藏下來,抽空解答一下,秀一秀自己智商,再看看要不要找老闆談個加薪或者其他福利。

題目6:

現在有兩種磚,分別是1*1的磚和1*2的磚,用這兩種磚鋪 1*N 的地面。

問共有多少種鋪法?(輸入為N,請輸出相應的鋪法數,經典鋪磚問題)


題目7:

12個高矮不同的人,排成兩排,每排必須是從矮到高排列,且第二排比第一排對應的人高。

求排列方式有多少種? 

題目8:

從一副撲克中隨機抽取5張牌,判斷是不是順子(5張牌數字連續,大小王為任意數字)。

題目9:

輸入兩個整數 n 和 m,從數列 1,2,3…n 中隨機取幾個數,使其和等於m,要求將其中所有的可能組合列出來。 

題目10:

輸入一個正整數 n,輸出所有和為 n 的連續正整數序列。

最後再擺一道,燒腦題

傳說中的愛因斯坦提出的思考題,他宣稱世界上只有2%的人能解出這個題目,你肯定聽說過不下一次這道題,但也肯定你始終連題目都沒記清楚過。

題目如下:

據說有五個不同顏色的房間排成一排,每個房間裡分別住著一個不同國籍的人,每個人都喝一種特定品牌的飲料,抽一種特定品牌的煙,養一種寵物,沒有任意兩個人抽相同品牌的香煙,或喝相同品牌的飲料,或養相同的寵物。

問題是誰在養魚作為寵物?為了尋找答案,愛因斯坦給出了以下15條線索。

1. 英國人住在紅色的房子裡;

2. 瑞典人養狗作為寵物;

3. 丹麥人喝茶;

4. 綠房子緊挨著白房子,在白房子的左邊;

5. 綠房子的主人喝咖啡;

6. 抽 Pall Mall 牌香煙的人養鳥;

7. 黃色房子裡的人抽 Dunhill 牌香煙;

8. 住在中間那個房子裡的人喝牛奶;

9. 挪威人住在第一個房子裡面;

10. 抽 Blends 牌香煙的人和養貓的人相鄰;

11. 養馬的人和抽 Dunhill 牌香煙的人相鄰;

12. 抽 BlueMaster 牌香煙的人喝啤酒;

13. 德國人抽 Prince 牌香煙;

14. 挪威人和住在藍房子的人相鄰;

15. 抽 Blends 牌香煙的人和喝礦泉水的人相鄰。

留言活動:

不要搜尋:靠自己能力,留下你的答案

一般人很難記住這麼多線索,即使之前看過這道題,蒙對了答案,但讓你寫一下演演算法思路,照樣傻眼。 

如果你是真 · 演演算法工程師,那就不是一般人兒了,請再次秀出你的智商。

應試教育出來的我們,在上學學習期間缺少方法和指導。工作這些年也可能很少接觸要自己動手寫演演算法的任務。

但演演算法,一直都是體現程式員能力的基本要素,也是拉開收入差距的關鍵指標。

想學演演算法?


缺方法?

7大方面,從基礎到應用,趣味精講演演算法;

缺時間?

43天,1天1個演演算法知識,每天15分鐘;

缺練習?

35個經典演演算法相關案例分析;


原價:69.00

限時特價:49.00


贊(0)

分享創造快樂