版權申明：本文為部落客窗戶(Colin Cai)原創，歡迎轉帖。如要轉貼，必須注明原文網址
http://www.cnblogs.com/Colin-Cai/p/11073938.html
作者：窗戶
QQ/微信：6679072
E-mail：[email protected] 每當學習一門計算機語言，我們也要做一些練習以便逐漸熟悉。随着我們對這種程式設計語言本身支援的抽象手段了解的過程，以下這些問題，基本可以在幾乎每門程式設計語言學習的過程中完成，這些語言可以包含但不限于C、C++、Shell、awk、Python、JavaScript、Java、Scala、Ruby、Lisp(Common Lisp、Scheme、Clojure)、Prolog、Haskell等。
漢諾塔(Hanoi Tower)
漢諾塔有三個柱子，最開始在第一根柱子上按從小到大的順序放了n個盤，每次可以移動一個盤，并且隻能小盤放在大盤的上面。問如何才能把這些盤從第一根柱子移到第二根柱子。
這個基本上是學習所有語言時候學習遞歸必然要接觸的例子，實作了這個，也基本上對所學習語言的遞歸有了初步的了解。
我們可以把問題看成是Hanoi(1->2, 3, n),符号解讀為把n個盤從1号柱移動到2号柱，剩餘一個柱子是3号柱。
很容易把這個大問題拆成三個小問題：
Hanoi(1->2, 3, n) => Hanoi(1->3, 2, n-1), Hanoi(1->2, 3, 1), Hanoi(3->2,1, n-1)
也就是先把最上面n-1個盤從1号柱移動到3号柱，再把最大的盤從1号柱移動到2号柱，最後把最3号柱的n-1個盤移動到2号柱，
于是就達到了遞歸的效果。
因數分解/整系數多項式因式分解(factorization)
因數分解，是将輸入的正整數分解為各個質數的乘積，比如：
$300 = 2^{2}\times{3}\times{5^{2}}$
因數分解普通情況下的算法并不複雜，隻需要一個簡單的初等數論證明即可。
而整系數多項式因式分解可能比上述還要複雜很多，比如：
$2x^{6}+7x^{5}+13x^{4}+15x^{3}+11x^{2}+5x+1 = (x^{2}+x+1)^{2}\times(2x^{2}+3x+1)$
這個無論是面向過程還是面向對象還是函數式程式設計等都值得好好做一做，如果可以，也可以嘗試嘗試Galois域的多項式環内的分解。
質數表(prime number list)
質數表也是一個合适的程式，可以使用好幾種方法。
最簡單的，我們可以依次從2開始判斷每個數，對于每個數N判斷2~N-1是否是其約數，如果其中沒有它的約數，則為質數。
當然，上述可以提高效率，我們知道對于任何一個正整數，如果是合數，則一定存在一個整數約數小于自身的平方根。于是我們的判斷從2~N-1縮到$2~\sqrt{N}$。
再往上進一步，我們尋找$1~N$中的質數可以歸結于尋找$1~\sqrt(N)$的質數。于是，我們這就可以引入一個遞歸。
另外，還有各類篩法不再細講，可以自行google。
進而以上可以從各個角度來熟悉你所學習的程式設計語言。
排列/組合(permutation and combination)
組合數學的相關知識應該在中學就已經學過，我們通過加法原理和乘法原理(實際上乘法原理也是由加法原理推出)推出了排列/組合的世界。
這裡，我們可以嘗試着去寫一個集合的所有排列/組合。
比如${1,2,3}$的所有排列有${1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}$，所有兩個元素的組合有${1,2},{1,3},{2,3}$。
有很多方法實作輸出一個集合的所有排列組合：
首先，很多語言都有相關的庫支援排列組合，比如Python的itertools庫，很多時候正式寫程式還是直接用庫的。
比如${1,...n-1}$的所有排列到${1,...n}$的所有排列存在一個遞歸，組合也類似。
再者，我們可以用字典排列依次輸出所需要的排列/組合，隻是如何找到下一個稍微大一點的排列/組合需要一點點技巧。
然後，我們還可以用數與每個排列/組合一一對應，理論上有各種對應方法。
甚至，我們可以基于交換來依次輸出所有的排列/組合，當然這裡需要一些抽象代數知識。
總之，我們有各種實作排列/組合。
生命遊戲(Conway's game of life)
生命遊戲是1970年Conway的發明。
MxN的圖裡，所有的格子都帶有一個狀态，為生/死。
每一次整張圖都有一個狀态轉換，每一個格子都要看周圍8個格子生/死的個數。
下一代所有格子狀态由以下規則确定：
1.如果周圍有生命格子的數目小于2，則下一代這個格子狀态為無生命(解釋為太孤單)。
2.如果周圍有生命格子的數目大于3，則下一代這個格子為無生命(解釋為周圍生命太多，資源消耗厲害)。
3.如果周圍有生命格子的數目等于2，則下一代這個格子的狀态繼續保持目前的狀态。
4.如果周圍有生命格子的數目等于3，則下一代這個格子的狀态為有生命。
24點(Count 24 points)
我們小的時候基本都玩過24點，就是4張牌使用加減乘除計算出24。
這個用程式實作是有點挑戰的，我們考慮如何周遊所有的可能，然後依次算出來，看是否等于24，另外，我們可能還要考慮分數，比如下面經典題目5、5、5、1，計算方法是(5-1/5)*5。
再者，我們要按照平常的使用習慣，考慮把多餘的括号去掉，比如((a*b)-c)/d其實應該是(a*b-c)/d。
另外，我們要考慮是否有結構等價，比如a*b+c*d和d*c+b*a，我們如何判斷并隻保留一種。
以上面的為例，可以有很多答案，比如2*8+3*3, 3*3+(8*2), 3*8*(3-2), (3-2)*(8*3), (3*8)/(3-2),(2+3/3)*8, (3/3+2)*8...但我們隻考慮計算結構的唯一以及去掉多餘括号，合理的隻剩下四個答案：2*8+3*3, 3*8*(3-2), 3*8/(3-2), (2+3/3)*8。
當然，我們還要考慮更多的牌，更多的運算來計算任意數字。總之，24點這個問題或許不是那麼容易，在某些語言下的實作尤其有技巧性。
自輸出程式(Quine)
解釋一下，所謂自輸出程式(Quine)，就是程式的輸出和程式的代碼一模一樣，直接用哲學家Quine命名。
這樣的程式也需要寫？怎麼感覺是在學習寫病毒呢？
病毒的确可能需要自輸出這樣的技術，但是技術這個東西本身就是雙刃劍，手術刀是用來救人的，但它依然可以拿來當兇器。
每一種程式設計語言隻要是圖靈等價的(當然，其實這個條件很基本)，就可以通過不動點存在定理推出Quine是一定存在。記載中，上世紀60年代誕生了第一個Quine，用Atlas Autocode編寫。
對于Scheme,可能的最短的Quine如下：
((lambda (x) `(,x ',x)) '(lambda (x) `(,x ',x)))
标準庫的部分實作
思考所學語言的一些标準庫的實作，也是提高的重要手段。比如C++的STL，我們在學習C++的時候可以去思考STL可能是如何實作的，這樣很有助于對C++面向對象、泛型(通過模闆實作)的了解。
并且，很多時候庫的實作一樣的語義有多種實作方式，我們可以考慮各種實作方式的不同。比如Scheme這樣一種資料、過程完全混在一起的語言，很多基本函數有非常誇張的完全不同的實作。
如果Scheme、Common Lisp、Clojure這幾種Lisp先後學習，也可以結合在一起，對比着學，想想另外一種是如何實作的。幾種Lisp畢竟還是兄弟關系，有很大的相似，這種相似甚至可以擴充到同一程式設計範式的不同語言之間，它們依然有很多可以相通的地方，這些都可以對比關聯。比如兩種從設計一開始就沖着多範式支援而去的JavaScript、Python，就可以和很多其他語言産生共鳴，我們在實作某些庫的時候也會去想想别的語言是如何實作的。
結束語
計算機語言的學習總是循序漸進的，總之本着多思考、多對比，永遠不要讓新學到的知識形成知識孤島，而要讓所有的知識彼此緊密聯系在一起，這樣才會不斷進步，并更有創造的靈感。