攻略｜演算法工程師的成長怎能少了腦筋急轉彎
老崔去某廠筆試時，遇到了經典的「狼、羊、白菜 過河問題」，由於經常看演算法方面的內容，這道對於他來說，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
>> 演算法應該怎麼玩？<<
參考來源：
封面圖：動漫《銀魂》
演算法經典書 | 演算法的樂趣
演算法經典書 | 圖解演算法
演算法經典書 | 演算法之美
分享決定技術高度
學習拉開技術差距
>>
GitChat<<
