《像程式員一樣思考》是一本訓練程式員程式設計思想的指導書。本書以向個經典難題開篇,提出一些程式設計中常用的思想方法,如重述、類比、劃分、消減等。同時也提供一些具體的技巧,如利用數組、指針動态記憶體、類解決問題。着重提出了大遞歸的思想,以及善假于外物的思路。本書注重程式員自信心的培養,提倡利用現有方法解決未知問題的同時,也鼓勵探索式自主學習新技術。
狐狸、鵝和玉米過河問題:用重形式化的方式重述問題,更好地洞察問題。以程式化方式列出所有的操作,進而發現“被隐藏的”的可能操作,将這些方法操作進行自由組合得到目标結果。認識到思考問題很可能與思考解決方案具有相同的工作效率,甚至更勝一籌。
瓷磚滑塊移動問題:無法規劃完整的解決方案并不意味着就無法采取政策或技巧系統性地解決問題。可以将問題進行細分,劃分成細小部分,對其簡單版問題進行研究發現一種常用技巧(“串列”),解決簡單版後依次增加難度還原問題步步解決。
數獨填詞問題:“最大限制變量”。尋找問題限制性最強的部分,雖然限制條件往往使問題難以着手,但它們也可以消除很多選擇、簡化思路。如數獨填詞中搜尋那些可能出現的值最少的空格。如果問題的某個部分具有很強的限制條件,很可能應該從這一部分開始着手,就不用擔心把時間花在将來可能會返工的任務上了。
制訂計劃:事先必須制訂計劃,而不是直接進行漫無方向的嘗試。
重述問題:用不同的方式或術語闡述,重新審視問題,發現新思路。
劃分問題(分治法):找到一種方式把一個問題的解決方案劃分為幾個步驟或幾個階段,可以使問題更容易解決。
從自己所知的開始:在程式設計在解決問題時,盡量從自己知道的部分開始着手。當用自己所掌握的技巧對一個問題進行研究時,可以更好地了解這個問題本身以及它的最終目标。
消減問題:當面臨一個無法解決問題時,通過消減可以消減問題的範圍。可以添加或取消限制條件,産生一個自己知道如何解決的問題。消減後的問題與原問題仍有相當多的共性,會使我們向最終的解決方案更進一步。消減問題允許我們準确地了解剩餘的難點位于何處。
尋找類比:類比就是一個目前問題和一個已經解決的問題之間的相似性。其前提是已經擁有大量的解決方案可供參考。
試驗:試驗是一種可控的過程。我們假設當某些代碼執行時将會發生什麼,然後對它進行實驗,觀察自己的假設是否正确,根據這些觀察,可以獲得一些資訊,幫助自己解決原先的問題。另一種形式的試驗與調試相似。
避免陷入挫折感:挫折感會不斷惡化,很可能一開始輕度焦慮變成最終難以遏制的煩躁。方法:首先制訂計劃;其次,可以休息一會兒。
什麼時候使用數組:一維數組還是多元數組;數組最大長度是否确定;是否需要多次處理資料;是否有大量的随機通路。
什麼時候使用指針:具有如下優點,運作時确定長度的資料結構,可改變長度的資料結構,記憶體共享。當需要利用指針一個或多個優點的時候才應該使用它。
類:封裝、代碼利用、問題細分、資訊隐藏、可讀性、表達能力。
大遞歸思路:如果在編寫代碼時采用某種約定,可以假裝并沒有發生遞歸。最好應用于難以用疊代解決方案的場合,如回溯。編寫排程器就遵循兩個規則,(1)排程器必須完整地處理最簡單的情況,而無需再調用疊代函數;(2)當排程器調用疊代函數時,必須向它傳遞問題的更簡單版本。
對樹和圖這樣的分支結構的周遊在本質上是遞歸的,處理像數組和連結清單這樣的線性資料結構則通常不需要使用遞歸,但是也有例外。
過多的參數:程式員常常陷入到尾遞歸模式上。關遞歸技巧可以減少遞歸調用所傳遞的資料量,而尾遞歸可能導緻向遞歸調用傳遞額外的資料。
全局變量:在遞歸函數中,隻要有可能,應該盡量避免使用全局變量。全局變量會使代碼不容易了解和不容易維護。
遞歸常常應用于像連結清單、樹和圖這樣的動态資料結構。資料結構越複雜,遞歸解決方案在簡化代碼方面所發揮的的作用也就越大。處理複雜的資料結構常常類似于在迷宮中尋找一條正确的出路。
單連結清單的遞歸處理通用計劃如下,假設有一個連結清單L和一個問題Q:
如果L是最小情況,就直接設定一個預設值。否則……
使用一個遞歸調用為連結清單L的“剩餘部分”(從L的第2個節點開始)産生Q的答案。
檢查L的第1個節點的值。
使用前兩個步驟的結果為整體的L産生Q的答案。
二叉樹的遞歸處理通用計劃如下,假設有一個樹T和一個問題Q:
如果樹T為最小規模,直接設定一個預設值。否則……
執行一個遞歸調用,為T的左子樹回答問題Q。
執行一個遞歸調用,為T的右子樹回答問題Q。
檢查T的根節點的值。
使用上面的3個步驟的結果,為整體的T回答問題Q。