一些簡單的編程練習題

英文原文： Simple Programming Problems

        每當成為入門 CS 課程（學生們學習編程語言的課程）的助教時，都困于提出好的練習題。Project Euler 和類似的問題通常對初學者來說來難了，尤其是對于那些沒有很強數學背景的同學。

        在這篇文章中，Adrian Neumann 收集了一些從初級到高級逐級困難的練習題，適合剛開始學習編程的初學者。當有新的練習題時，Adrian 會及時添加。除了一些 GUI 問題外，練習題一般都是算法題，無需學習任何庫就可以解決。課程練習題的困難程度有時候取決于你使用的編程語言。例如，關于列表 List 的練習題若用內部不支持 List 的C語言來解決的話會困難些。

        即使有一定編程經驗的人想要學習一門新語言的時候，雖然這對他們來說相對簡單，但我認為這還是有用的。

        初級

        1. 寫程序將” Hello World”打印到屏幕。

        2. 寫程序輸入用戶的姓名并用該姓名和他打招呼。

        3. 修改上一個程序，使得僅可以與 Alice 和 Bob 這兩個用戶用其姓名與之打招呼。

        4. 寫程序輸入一個數n并打印出從 1 到n的和。

        5. 修改上個程序，使得求和的數只包含 3 或 5 的倍數，例如n=17，則求和的數為：3, 5, 6, 9, 10, 12, 15。

        6. 寫個程序，要求用戶輸入一個數n，并概率性的選擇是計算 1 到n的和還是計算 1 到n的乘積。

        7. 寫程序打印出 12×12 乘法表。

        8. 寫程序打印所有的素數。（注意：如果你用的編程語言不支持任意大小的數，那么打印出所有你能表示的素數，包括最大數）

        9. 寫一個競猜游戲，用戶必須猜一個秘密的數字，在每次猜完后程序會告訴用戶他猜的數是太大了還是太小了，直到猜測正確，最后打印出猜測的次數。如果用戶連續猜測同一個數字則只算一次。

        10. 寫個程序打印出接下來的 20 個閏年。

        11. 寫程序計算：

        列表 list 和字符串

        1. 寫一個函數，返回列表中最大的數。

        2. 寫函數逆轉列表，最好是原地逆轉。

        3. 寫個函數檢查指定的元素是否出現在列表中。

        4. 寫個函數返回列表中奇數位置的所有元素。

        5. 寫個函數計算列表的運行花費總和（the running total）。

        6. 寫個函數測試一個字符串是否是回文。

        7. 寫三個函數來計算列表中數字的和：分別用 for 循環，while 循環和遞歸完成。

        8. 寫個函數 on_all 遍歷列表中的每個元素，打印出開始的 20 個完全平方數。

        9. 寫個函數連接兩個列表。

        10. 寫個函數交替合并兩個列表，例如：[a,b,c], [1,2,3] → [a,1,b,2,c,3]。

        11. 寫個函數合并兩個有序的列表。

        12. 寫個函數計算前 100 個 Fibonacci 數的列表。

        13. 寫個函數，返回指定數的各位數字的列表。

        14. 寫個函數對兩個數進行加減乘，使用各個位上的數字表示的列表實現并返回一個新的數字列表，如果你有信心可以實現 Karatsuba 乘法。嘗試不同的基數，如果你關心速度可以比較下哪個是最佳基數。

        15. 實現下面的排序算法：選擇排序，插入排序，歸并排序，快速排序，臭皮匠排序（Stooge Sort）。具體的描述見 Wikipedia。

        16. 實現二分查找。

        17. 寫個函數，給定一個字符串列表并按下面表示打印出來，一行一個打印在矩形框中。例如列表["Hello"， "World"， "in"， "a"， "frame"] 打印的結果是：

*********

* Hello *

* World *

* in    *

* a     *

* frame *

*********

        18. 寫函數將一段文本 text 翻譯為 Pig Latin 返回，英語翻譯為 Pig Latin 的規則是：取出每個單詞的首個字母，追加’ay’后再放到該單詞的末尾。例如“The quick brown fox” 翻譯后就變成了 “Hetay uickqay rownbay oxfay”。

        中級

        1. 寫程序在1,2,…,9（保持這個順序）之間可任意放+或-或都不放使其結果等于 100，輸出所有可能的放法。例如：1 + 2 + 3 – 4 + 5 + 6 + 78 + 9 = 100。

        2. 寫程序以一個假想行星的一年持續時間作為輸入，產生一個閏年規則，最大限度的減少與該行星的太陽年的差異。

        3. 實現數據結構圖，允許修改（插入，刪除），并能夠存儲邊和節點的值。可能使用（node, edgelist）字典對表示完成該功能最容易。

        4，寫個函數生成圖的 DOT 表示（譯者注：DOT 語言是一種文本圖形描述語言，它提供了一種簡單的描述圖形的方法，并且可以為人類和計算機程序所理解。）。

        5. 寫程序自動的給你生成文章：

        （1）使用一個樣例文本 sample 創建有向（多）圖，其中文本單詞作為節點，如果文本中u后面是v則u和v之間有一條有向邊，多次出現生成多條邊。

        （2）在該圖中做隨機遍歷：從一個隨機的節點開始選擇一個隨機的后繼節點，如果沒有后繼節點就隨機的選擇另一個節點。

        6. 寫程序自動的將英文文本轉換為摩爾斯電碼（譯者注： 摩斯碼（Morse Code）是一種時通時斷的信號代碼，通過不同的排列順序來表達不同的英文字母、數字和標點符號）或者相反。

        7. 寫程序找出給定字符串的最長回文子串，盡可能高效的實現。

        高級

        1. 給定兩個字符串，寫程序高效的找出最長的公共子串。

        2. 給定一個整數數組，寫程序高效的查詢：比位置i處的數稍大的最近鄰數，這里的距離是指數組下標的絕對差。例如數組[1,4,3,2,5,7]，比 4 大的最近的數是5。先用線性時間做預處理，然后用常數時間做查詢。

        3. 給定兩個字符串，使用字符插入和刪除將其中的一個字符串轉變成另一個，輸出最短的插入和刪除序列。

        4. 寫個函數實現兩個矩陣相乘。盡可能高效的實現并使用較好的線性代數庫（linear algebra library，具體可看這里）進行性能比較。你也許想讀一下Strassen’s algorithm 和 CPU 緩存的影響，嘗試不同的矩陣布局，看看發生了什么。

        5. 給定d維矩陣框集合，寫程序計算它們交集的體積，從 2 維開始逐步計算。

        GUI

• 寫一個展示彈跳球的程序。
• 寫一個內存游戲。
• 寫一個俄羅斯方塊工程 Tetris clone。

最后的開放性問題

1. 寫一個盡可能好玩的猜字游戲 Hangman。例如你可以使用這樣的大字典并選擇排除大部分單詞仍有解決方案的字母。盡可能高效的實現，比如不要每一輪都掃描整個詞典。
2. 寫個程序與人類玩石頭剪刀布（Rock, Paper, Scissors），嘗試證明人類非常不善于生成隨機數字。
3. 寫個程序與人類對手玩 Battle Ship（海戰棋，是雙人玩的猜謎游戲），輸入坐標并輸出是否擊中及此次射擊的坐標。

        其它收集

        當然我不是第一個提出要收集類似上面列表這種思想的人。

• John Dalbey 的收集
• 幾個小問題 編程實踐
• CPE 101 項目
• Code Kata
• 99 Lisp Problems, 99 Haskell Problems. 這里的大部分問題都可以用其它語言解決。
• Rosetta Code Programming Tasks. 這些問題提供了多語言解決方法！
• Code Golf Challenges. 這里的目標是用盡可能少的字符解決問題。
• SPOJ Problems. 這是一個超過 13000 個問題的列表！

        翻譯： 伯樂在線 - 敏敏     譯文鏈接： http://blog.jobbole.com/53039/