2009/02/14

高中週記 No. 10

第十篇高中週記(仍然在一年級上學期),寫於 2002 年 11 月中:

這個星期五數學課教的是遞迴。之前看遞迴時,總覺得跟程設中的遞迴沒什麼關係。(JK 注:這就是不教 functional programming 的後果 XD。)但這個星期剛好把快速排序法的架構研究出來,對遞迴的應用有了較深的體驗。結果老師拿出「河內塔」並講解它的運作原理後,忽然任督二脈大通,數學和程設的遞迴出現了連結!之後回家後花了幾個小時把河內塔寫成程式,之中還有一次觀念大修正。隔天早上七點多,我將「當天」早上十二點多完成的 BETA 4 版輸入電腦編譯連結後(JK 注:竟然特地寫「編譯連結」XD),執行程式的畫面終於一步一步地出現三層河內塔的詳解,核心部份終於成功了!之後又逐步地加入檔案輸出等功能(JK 注:高中生很喜歡寫這些 systems programming 的東西?XD),加上註解及分段後,約一百五十行左右。(不過後來上網一看,原來早就有一堆人在寫了,而且還是標準遞迴題型、基本遞迴程設……。想想也對,這河內塔又不是什麼稀奇玩意,我想得到自然有更多人也想得到。而且,還是因為看老師的一番講解我才有靈感……。)

還有,老師曾在上課時提到氣泡排序及快速排序。(JK 注:是在什麼語境下會提到排序啊?XD)我在書上看到說有三個著名的排序法:快速、謝耳、夏克排序法。(JK 注:哪本怪書啊?XD)那後兩者的原理是什麼呢?

導師的話:一、欲知內容,多查查資料!二、非一言兩語可完!三、一般而言,快速較快! (11/18)

這篇模糊提及我對遞迴運算(in particular, tower of Hanoi)的了解是在半夜。用撲克牌搬了好一陣子的河內塔之後,我練習到能夠快速、毫無障礙地搬任意多層的河內塔,之後常用來唬同學 XD。根據記憶,我已經知道可以畫出某種 call tree 並對它做 traversal 而得到解答。

--
做自己的史料分析挺有趣的 XD。

Labels: