Introduction to Programming

From ITRS
Jump to: navigation, search

程式設計入門: C 語言

工研六題

  • 從 2000 ~ 2006 年使用的『傳統』程式設計入門教材
  • 強調『如何寫出正確迴圈』口訣:初始條件、恆等式(在運算過程中必須維護,使其恆真)、結束條件。
  1. 費氏數列(指定運算與迴圈)
  2. 有趣數列問題
  3. 多項式求值 (解答)
  4. GCD(最大公因數) (解答)
  5. 篩法求質數
  6. GCD 線性組合

程式設計比賽存活指南

上學期開學沒多久,高中校內與台北市的程式設計比賽就開始了,在 10 月?11月? 鼓勵學弟參與程式設計比賽,所以比賽需用到但 C 語言初學常不會的如:

  1. 利用 scanf return value 判斷輸入是否結束
  2. 用 freopen 將指定檔案當作 stdin, stdout
  3. 『由下而上』實作:從輸入處理寫起,寫一段就測一段
  4. 程式 segfault 後由 gdb 得到 stack trace
  5. 除錯時『逆向思考』,放棄成見,從觀察程式實際行為開始推理
  6. 知道 C standard library 中有數學函式如 sqrt 並知道可以用 (make_tutorial 中有範例)
  7. randrange 產生亂數 (教材撰寫過程
    1. srand: 設定 pseudo-random integer sequence 的 seed

See also:

  1. 高中競賽與科展心得: 強烈建欲參加科展與程式設計比賽者議詳讀
  2. Ptt BBS Programming 板 (問題) 高中程式設計大賽

狀態空間搜尋、遞迴與動態規劃

Python 與數學

Scott Tsai 程式設計教學心得

常有程式設計初學者抱怨入門前幾個月的範例、習題都是『文字處理』、『數學問題』、『基本資料結構』,而想寫他們每天用得到,或是有圖形、動畫、機械控制效果的程式 -- 關鍵在於『學習第一個程式語言』過程並不有趣。 範例比較好,習題比較難的課本如 The C Programming Language (習題解答) 也只能讓『學好第一個系統層次語言與基礎計算機組織』的過程變得較有挑戰性與成就感。 選擇功能比較少,課本比較薄的程式語言則讓『學會程式語言』的時間不要拖太久。

學完第一個程式語言後,學員馬上面臨『我還是寫不出有用程式』的困境。 此時如 USACO 等程式設計比賽訓練教材,至少讓學員從解決一個個習題中訓練用電腦解決問題的能力與(高中比賽喜歡考的)演算法;並從獨立思考、解題中得到成就感。 易言之,一個高中生花一個學期解 USACO 後,還是寫不出多『有用』的程式,但過程中有事做而且鍛鍊了有用的基礎能力。 除了程式設計比賽解題,我經驗中高中生會喜歡的程式設計活動:

  1. 用 pygame 寫遊戲 有很多有趣的 game 可以改。在用 javascript + HTML5 canvas 或 Flash 寫小遊戲想必也一樣很有趣。
  2. vpython 畫物理模擬動畫與 3D 碎形
  3. Turtle graphics
  4. 將 microcontroller (8051, AVR) 接上光、聲音、溫度感測器與步進、伺服馬達
    1. 洛奇機器人DIY科學魔法車
    2. Designing embedded hardware By John Catsoulis
    3. Microcontroller projects using the Basic Stamp By Al Williams

對於想要寫有趣程式的高中生而言,學習系統程式語言,二補數、浮點數的性質與遞迴思考是對『預備知識』是不得不做的投資,不是目標;但要想出『有趣而且高中生做 得出來』的主題也頗耗心思。柏崴以前的 『自動飛靶』科展主題, 我高中時就做不出來。

程式設計比賽導向的演算法教學

Scott Tsai: "主題選擇上演算法入門最有用的是:『狀態空間搜尋』即以深度優先、廣度優先等方法解 "8 queen", "9 puzzle" 等排列組合題目。之後適合討論的主題包括:『遞迴與動態規劃』。 以上那兩個主題『夠難但又學得會』剛好都是高中程式設計比賽喜歡考的。 考慮一下從以下書單中選一本來講:

  1. 算法艺术与信息学竞赛 (中國程式競賽教材)刘汝佳、黄亮 清华大学出版社
  2. Programming Challenges Steven S. Skiena and Miguel Revilla. Springer
  3. Art of Programming Contest Ahmed Shamsul Arefin Gyankosh Prokashoni

見: http://www.csie.ntnu.edu.tw/~u91029/book.html

另外一個『實務上常用到,但比賽不常考』的主題是『連結串列』、『雜湊表』等基礎資料結構,如: The Practice of Programming 一書的第二章:

Chapter 2: Algorithms and Data Structures 
      2.1 Searching 
      2.2 Sorting 
      2.3 Libraries 
      2.4 A Java Quicksort 
      2.5 O-Notation 
      2.6 Growing Arrays 
      2.7 Lists 
      2.8 Trees 
      2.9 Hash Tables 

Chia Hao Lo: "教過 DFS, BFS, Dijkstra 後, 不妨將這些方法做個連結, 點出 best-first search 的概念: http://en.wikipedia.org/wiki/Best-first_search 讓大家了解這三者其實骨架相同, 差別在於評估展開節點的函式: DFS 用 max(depth), BFS 用 min(depth), Dijkstra 用 greedy function 之後還有興趣的人, 可以再點出 A*, 有 A* 後就可以講很多有趣的例子, 像是解智慧拼盤 (應該是 Scott 提的 9-puzzle), 魔術方塊等 有 A* 前也是可以講不少有趣的例子 (如 Scott 提的 n-queen), 讓大家體會到電腦異於人類的「作事」方式 btw, 我個人比較喜歡舉例歸納的作法, 這樣符合實際學習的模式, 可能也類似當初發展這些演算法的思路, 有些教材 (特別是數學類的) 會先講最後歸納的結果, 再開始舉例, 好像一切渾然天成似的, 這樣不易吸收, 抓不到背後的思路。"

kunghua:"講完 DFS / BFS 後可以順便講 ID (Iterative Deepening) . 只要多一個參數就可以限制深度而讓DFS 達到和 BFS 一樣的效果 (但是要比較速度和記憶體的用量). 對不想寫 BFS 的 Queue 的人來說 ID 可是一種偷吃步的方法.... 8-puzzle 可以用編碼的方式 (9! 種 state) 用 BFS 來實作 15-puzzle 就要用 IDA* (Iterative Deepening A*) <= 不過在高中的比賽是用不到的....可以先跳過 最後一定要教 DFS Branch and Bound....在高中比賽很好用的,可以出在時間內算出大部份的解來拿部份分數 (總比 0 分 好)."

See Also

Comments

blog comments powered by Disqus