台大資工九十八學年度甄試入學，程式設計考題
這次參加台大資工的二階甄試，選擇了據說很難的程式設計。結果雖然大致上解出了每個問題，但似乎都有些粗心的小錯誤。不知道會得幾分呀？
我解完前三題時好像還剩下許多時間，然而第四題一直想不到好的解法。回頭看看前三題，抓出了一些小錯誤，想不到最後還是有沒發現的疏忽啊。然後雖然寫出了可能行的通的第四題解法，不過似乎會在某些情況下陷入無限迴圈呢。
註：其實我不太記得題目，以下乃參考他人分享而來，可能和原題目有出入，但意思上大致是不變的。如果對此種程式解題的形式不熟悉，可參考：〈練習程式解題〉。
一、吊死鬼遊戲
吊死鬼猜單字遊戲，給你答案字串(長度<=10)及玩家猜的字母，印出遊戲每個步驟所顯示的字串。
尚未被猜出的字以 * 表示，已猜出的則顯示字母。
輸入的第一行是要猜的單字，接下來的每一行會有一個字母，表示玩家每次猜的字母。
輸出的每一行為遊戲的狀態。
|
|
這題很簡單，我用最直接的寫法：把字串讀入一陣列，接著再依序讀入每個猜測字母，從 0 到字串尾逐字掃描，遇到相同的字母就把另一個預先設的***字串中同一位置以此字母取代。
當然理論上用 strchr 會比較快啦，不過測資那麼小，應該沒差。
二、分數計算
輸入是一行分數的運算式，其中分數最多 5 個，運算子只有 + 和 - ，請輸出運算結果。
分數格式為 X/Y (X,Y為小於100的正整數)，內無空格，分數和運算子間均有一空格隔開。
輸出需為最簡分數，有負號請加在分子。
|
|
這題如果答案出現整數的話不知道該如何輸出才好，雖然題目好像說答案是「分數」啦。另外就是，分母可能出現非常大的數字，可是我只有用 int 宣告變數，裝不下那麼大的數字，若真有此種測資，則就會輸出錯誤了。
三、排列
給你N(1<=N<=9)個相異的 4-byte 整數，請按大小順序輸出所有排列可能。
輸入的第一行為整數 N ，第二行則有N個相異整數。
按大小順序，一行一個，輸出所有排列可能。
|
|
重點在於， 4-byte 整數用 int 還是裝不下，至少要用 unsigned int 才行，可是我還是用了 int 啊啊啊！當時好像以為它是 4-bit 整數！？
因為測資很小，所以用了偷懶的 next_permutation ，沒五分鐘就寫完這題了。
四、找群
有編號1~N的N個人(1<=N<=22)，若其中一群人彼此都是朋友，則這群人就稱為一個群。
輸入的第一行為N，接下來每一行有兩個數字 a, b ，表示 a 和 b 是朋友。
輸出最大的群之人數。
|
|
整體而言，實在不知道考得好還是不好。唉唉唉。
相關文章
古都馬拉松小記
前陣子參加了台南古都馬拉松，10.4km。
想一想其實上了高中之後我已經很少跑步了，突然要跑個十公里還真是挺嚇人的，實際上我對十公里還真是沒有很好的概念。就剛好化學老師邀大家去跑古都馬拉松，我就報名了，想想還真是個勇敢的決定
真正跑起來倒還好，維持著緩慢的速度，其實並不怎麼喘。實際上，整段路程我都沒有讓自己變得太喘。真正的挑戰來自雙腿，隨著路程加長，酸痛的感覺不斷加強，果然是在向我抱怨突然加給他的龐大工作量吧。憑藉著一股意志力，我還是以同樣的跑步速度撐完全程。
沒有用走的大概也不是什麼值得驕傲的事吧，有些同學雖然常常走一段路休息，讓我可以超越他，但每次他一跑起來就又超越我了，最後也比我早到終點啊。
最後還是有在規定的 1 小時 30 分鐘內完成，也拿到了一張努力過的證明！
要離開前，很幸運的碰上了好久不見的朋友。我們一起聊聊天，也拍了幾些照片。不過最後我很笨的找不到自己的腳踏車，還讓她們等了我許久，真是對不起！
搶救國文非得增加文言文比例與上課時數嗎？
註1：對於一般人該不該學文言文，其實我並沒有定見。然而教學方法上，我無法認同我所經歷過的國文課。而增加文言文比例似乎會助長我所不認同的教學方法。
2009-04-06 註2：當然對於小學生而言，字詞的講解也許是必要的，但隨著心智成長，同樣的教法已無法提供足過的挑戰性，而枯燥是會毀了一堂課的。
最近聽說教育部打算增加高中文言文的比例並增加國文節數，雖說是以搶救莘莘學子為出發點，但我以為這樣並不會有太大的幫助。
為什麼這樣說呢？從一個學生的立場來看，國文課本身其實對國文能力的培養並不具有無可取代的益處，至少在我的觀察來說是如此。從文言文與白話文教學模式的不同就可以稍微理解一些事情，在台南一中，白話文通常老師是不教的，而是讓同學自行閱讀，文言文則占據了大半的時間。
可想而知，上課絕大多數的時間都是在解釋每個字詞與句子的意思。是呀，不是本來就該這樣嗎？但難道字詞的解釋我們不能自行看書學習嗎？是的，也許不能完全做到，也許有的人確實不能。但如此一來，國文課相對其他自然學科，就佔了非常不利的位置。數學課時，如果老師教的太慢，我還可以多算幾道題目。如果我的解法和老師不同，我可以提出我的想法，或自己選擇該怎麼算。而聽老師講解時，我不只是聽而已，我還可以自己演算一遍。但國文課呢？老師教的太慢，我可以自己往前看嗎？單純理解字句，並不是一種像解題般深入而複雜的思考，這意味著我將難以屏除老師講解的聲音。而聽老師講解時，我幾乎就只是聽而已，抄寫只會讓腦子更加空白，完全無法提供心智足夠的刺激。
我當然可以開始思考文章的意境乃至於和作者辯論與對話，但一但心中充滿了哲學與文學的對話之時，這節課通常也不用上了，特別是不能和大家討論之時──還那麼多字詞要解釋，怎有時間胡扯呢？──思考是好事，但以台灣的高中國文教育來說，似乎不可能把整堂課拿來思考與討論。
從某個角度看來，國文課向來不鼓勵人思考。所以當你以為某篇文章也許也可以這樣或那樣解釋時，你還是得接受前人所定的解釋。特別是當這種爭議成為考題之時，心中的無奈真是無可言喻。
於是我發現，那隠晦的語感或國文能力，只能從大量閱讀中求得。就像想寫好作文一定得不斷練習一樣，一定得自己在文學之海奮力航行一段時間才能有所進步。
不禁開始遐想，也許減少上課節數並把多出的時間拿來閱讀搞不好反而能增進國文能力呢。
至於文言文是否與生活脫節這事，我就不多加著墨了。
關於教育的一些想法
前陣子國文老師在教「病梅館記」課說到，我們現在順應教育部來決定要讀什麼書，其實就有點像是病梅一樣，被殘害本性。那麼，我們能有什麼方法跳出這個框框，拯救病梅呢？
我首先提出了，或許我們可以離開學校，靠自己的方法創業，然後大賺其錢。
做為回應，老師說起了在工廠工作的經驗有多辛苦，學歷不同的起薪可以差多少等小故事來解釋學歷的必要。當然我是有點想反駁，畢竟我說的是創業，怎會扯到工廠還是起薪呢？當然，創業很難，或者說，在體制外想找到自己的路並不斷堅持很難。也許有人因為不滿學校而整天無所事事、苟且度日，但我說的不是這樣啊。
覺得唸書考試沒有意義，就做點有意義的事吧。也許是培養專業能力、也許你還是在讀書，只是讀的不是學校的書。要用上革命家那樣即使會喪失生命仍要堅持己見的意志與決心去貫徹自己的路。
但我沒有真的反駁老師，只是又給了另一個答案：我們可以努力用功讀書，將來有天當上教育部長，不就可以改革教育了嗎？
這次老師便表示贊同，認為這是一個可行之法。
只是我的心中卻有另一種聲音：就算做了什麼改革，是不是只會造就另一批「病梅」，只會使莘莘學子成為改革的受害者呢？
也許我們的教育需要的不是一兩位激進的改革者，而是一群可以自已選擇方向的學生。
將來要考大學的我們，對於自己想讀的學校了解有多深呢？究竟那些學校才適合自己呢？究竟該讀什麼樣的科系呢？也許從旁人的口中，得知了一些所謂的第一志願是哪些學校，但其實我們能找到的資訊是相當貧乏的。每個學校的特色在哪？風氣如何？我們甚至不會知道在自己的學校裡，哪個老師才是真正適合自己。
而當我們想學一些東西的時候，又能找到多少資料呢？從網路、圖書館以及其他的進修管道，確實能找到不少資訊，但究竟有多少人能好好利用呢？
當然一些真正有想法的人會自己透過各種管道取得想知道的事，而不管遇到什麼樣的困難，他也會試著一一克服。但，其他人呢？即使是平凡人，也該擁有決定自己未來的機會。
我相信降低門檻是件很重要的事。就好像數年前，雖然我們可以找到免費空間架設自己的網站，但使用的人數一直不是很多。而網誌一出現，讓每個人能以更容易的方式發表文章。於是，原本不做網頁的人，也開始在網路上發表自己的意見了。
我所期待的，是一個更加開放的教育體系，一個資訊開放的未來。當人們能更加容易取得知識，甚至了解社會真正的樣貌，而不是封閉在教室裡的時候，也許學生們會漸漸自覺，進而以社群的力量，達成另一種形式的教改（或說是學改？）。
當然，也許現在的思想、甚至硬體條件都還未成熟。但也許慢慢的，所有的一切將漸漸成形，雖然我甚至不知道那樣的未來會是怎麼樣子。
凡事總有個出發點，我想我會先從支持開放式教育資源運動 (Open Educational Resources Movement) 開始做起吧。
前方的道路
從國三就一直想表達的故事，一路刪刪改改，卻一直沒有正式動工，總以為會有時間去做。如今，時間剩不到一年，進度卻嚴重落後。我到底該怎麼辦呢？早知道高一就該好好用心去做的，如今時間更加緊湊，真是給自己找罪受啊。
無論如何，這個心願怎麼樣都要達成，一定要加油再加油！
學測將近，現在也開始複習起高一的課程，為了有效利用時間，不得不放棄一些事情。~~而這個網誌可能也會有段時間不再更新了。~~囧，發現自己還是忍不住偶爾寫一下文章，啊啊，我的時間啊！
等我呀！等我考完學測，還有很多事要做呢！
目前的重點計劃是要把英文、國文作文練好，把化學重新學過。其他部分，在暑假來臨前，先簡單看過一遍。
程式設計的部分，忍痛暫時放棄寫 ACM，每週只花一點時間讀 《Algorithm Design》，來個「紙上談兵」。
等考完學測，再讀一下 C++ STL 的部分，然後繼續研究 SCIM 和新酷音的程式碼。為了使我能在 Ubuntu 下快樂的使用行列輸入法，正式動工製作屬於我的行列！主要想做的是完整支援 dvorak 鍵盤、實作詞彙輸入及智慧選字、改進符號輸入等等。這計劃自我初學 C++ 便一直放在心中，總有一天實現它！
然後大概還想學 Python, Django or RoR，看一些書，重新學起好久沒碰的網頁設計，為我的神祕專案作準備。
總之，加油，加油，加油！
The Donation
這是我在南一中生活科技課交的期末作業。
做的有點兒雜亂，像是囈語般，只是沒有條理的說些無意義的話。
用到了自由軟體、樂透等事物作為元素只是偶然，其實真正想探討的是一種態度，即使無法確定自己的方向是否正確，仍要在對的起自己的情況下向前邁進。
人生如夢，似乎也沒什麼目的。但這當中的意義該是自己去體會，自己可以決定、可以感受的到的。那種感覺，正是能讓自己無悔的珍貴。
記得好像和友人提過捐款之類的話題，這也是促成此作品的原因之一。
在實驗的性質下，使用了 Rosegarden 創作了兩段旋律作為背景音樂，總覺得以後還能再做些更有趣的應用。
比完 2007 NPSC 的感想
這次的網際網路程式設計全國大賽恰好跟全國高級中學資訊學科能力競賽撞期，所以我的兩個隊友都無法出席。當然，許多高手也因此無法參賽。但自己並沒有想說有可能拿到多好的名次，所以這次十分反常的沒有特別緊張。最後的結果是第八名，離有「豐富」獎品的前六還差了一小段距離，不過倒是拿到了入圍決賽就有的 Microsoft Office 2007 標準教育版。
話說這可是生平第一次拿到正版的 MS Office 啊（別亂想，現在我用的是「正版」 OpenOffice.org 呢），內容完全一樣的非教育版好像標價 NT$14,390，而教育版只要 NT$2,990。不過國內似乎即使是一般人士也很容易買到教育版？就像隨機版也可以單獨買是一樣的情形。
這次上台北，最主要的目的該是吸取經驗吧，而且不只是比賽的經驗而已。
另外就是，Dev-C++ 的縮排超爛的呀，而且沒有 GVim 可用還真不習慣。忍不住會想，要是最後沒有把程式碼搞的亂七八糟的話，搞不好搞不好來得及解出數字拼盤呢！（雖說解出來名次也沒多大影響 XD）
前一晚，在台大的鹿鳴雅舍住的時候，因為和我同房的學弟們很晚才睡的關係，所以我也一直到半夜1、2點才睡著，嗯，雖說這是出外，比較不一樣。但我又想起了之前看過的幾篇文章：〈大學生，你是被煮熟的青蛙嗎？〉、〈 想救大學生？關鍵在於「睡眠品質」〉
我開始擔心起我的大學生涯，因為有些事，跟室友溝通恐怕是沒有用的。特別是，像我這種，每天都大概十點到十點半就會上床睡覺的人。到時候也許可以調整睡眠時間，晚一點起床，但若要達到相同的睡眠時數，除非早上都沒課呀。所以，所以，真的很糟糕。
雖說可能大學會一直趕作業，以至於不得不熬夜。但也許我可以應付吧？至少我知道高中就已經有很多人說他們會熬夜讀書。而我，即使不熬夜，也能在南一中保持在組排十幾名上下。所以也許我可以應付吧？
所以，所以，不免會考慮，我是不是該放棄交大、台大。留在台南、留在家裡？
我只是想，活久一點。我只是想，保持在一個穩定的狀態、一個不斷學習前進同時能終身奉行的狀態。如果去了台灣大學，卻犧牲了睡眠，那真的會是我想要的生活？
還是要租房子，犧牲了金錢？呵呵，真可惜我沒有這種選項。
智慧鐵人，南區初賽
2007年7月14日，終於要出發前去崑山科技大學參加第五屆智慧鐵人創意競賽的南區初賽。早晨，下起了大雨。集合的時候經過許多小波折，幸好最後橘色香菇的成員們還是到齊了。
就這樣，抱著緊張的心情，我步入會場。即使到了這裡，我還是有點搞不清楚情況。等了數十分鐘，比賽終於正式開始。
第一關是要用一堆材料設計一個裝置讓雞蛋落下，卻不會破。嗯，我們的設計是用筷子築成一個支架，把蛋放在上面，然後整個支架用線綁著，繞過滑輪，利用吸管製作一種可以增加線的摩擦力的裝置，讓整個支架緩緩降下。不過一開始考慮不周，就埋頭開始做，結果遇到了不少問題：像是支架無法平衡以及支架旋轉無法使蛋落至指定地點等等。
最後是有點狼狽，時間到了，卻連測試都沒測過，急急忙忙的，又犯了一些小錯誤。
評審啟動裝置後，整個支架先是緩緩降了一點，然後所有的蛋突然都掉了出來，滑落地面。據我姊姊的形容是：
評審嚇了一跳，低頭看看腳邊。
三顆蛋都破了，不過有一顆蛋的裂口被夾鍊袋擋住（所有的蛋都是放在夾鍊袋裡的），所以蛋汁沒有流出來。回想起比賽規則：「蛋破掉的定義是蛋汁流出」，她對評審說：「沒有流出來耶、可是它沒有流出來耶」。
那評審轉頭和另一位評審交會了眼神，考慮了許久，最後終於決定讓我們過關。
總之，我們幸運的拿到了一顆蛋的分數，從初始高度算起來，大概有 20 分左右吧（滿分是 100 分）。
這下子，只好寄望第二關了？
休息的時候，看到一組竟然利用規則說明的紙建構出雞蛋滑行軌道，而且測試數次，雞蛋都沒有破呢，感覺真的好厲害。只可惜他們似乎沒有在時間內做完，真是為他們感到惋惜。
第二關是改錯字，一共有四題，剛開始看到題目的時候完全搞不清楚情況：這真的是古文嗎？怎麼完全看不懂？著急的和隊友交換了題目，更是驚恐，四題都讓人摸不著頭緒啊！
就在此時，終於有人發現其中的奧秘，原來，不只是框起來要我們改的部份，而是整篇文章都是錯字！所以不能從字，而要從音來理解，這真是折磨人！記得當時我一直想不起「甬道」的「甬」字怎麼寫，我明知這字是以前準備基測時我在參考書上學到的，想不到卻忘得這麼快呀。經過一番努力，最終還是只有陶淵明的桃花源記被完全解讀（畢竟有教過嘛）。
事後最令人驚訝的是，原來其中一篇竟是金庸寫的倚天屠龍記！原文如下：
他手執火把先爬了進去，招呼小昭入來。那甬道仍是一路盤旋向下，他這次學得乖了，左手挺著長矛，提防圓真再加暗算，約莫走了四、五十丈，到了一處石門。他將長矛和火把交給小昭，運勁推開石門，裡邊又是一間石室。
這間石室極大，頂上垂下鐘乳，顯是天然的石洞。他接過火把走了幾步，突見地下倒著兩具骷髏。骷髏身上衣服尚未爛盡，看得出是一男一女。
小昭和圓真都是要改錯的字，真是欺負人！小昭那句好像寫成「朝忽曉朝辱萊」之類的，當初我花了不少時間在解讀這句。
總之，接下來就是等宣佈進入複賽的名單了。好像因為某會場的作業緩慢的緣故（據說是工商展覽館），結果左等右等，竟然比預期還慢了一小時左右才公佈名單。
然後，我們橘色香菇隊……沒有在名單上呀……
所以，只好含淚退場。
最後，南區複賽的結果是，高中組的第一名為台南一中的「為什麼丁丁是嘴砲?你說說看啊你說說看!!」，裡頭好像有我認識的學長？然後接下來則是雄女和雄中的隊伍。
雖然最後我們沒能挺進決賽，但我還是很高興能參加，總之，這確實是一次很有趣的經驗。
Dvorak: 另一種鍵盤排列
很久很久以前，當我還處於必須看著鍵盤才能打字的時期。不知從何處得知了行列輸入法，決定試著學學看。後來，又找到了 Jedi 所寫的「Dvorak 與行列輸入法」發現了 Dvorak Simplified Keyboard ，於是便開始學起了這兩個非常特別的打字方式。
剛開始我每天下課回家都會很有熱忱的打開我在官方網站上找到的教學 CAI 練習行列，後來大概練到每分鐘 30 幾個字左右吧，突然發現其實我並不常輸入大量的中文字（那時不像現在常常打網誌），再加上行列的符號輸入很麻煩，而且又不符合 Dvorak，所以我便又重新回到注音輸入法了。有趣的是，在我練過行列及 Dvorak 之後，即使是注音，我也已經不需看著鍵盤打字了。
行列是如此，但 Dvorak 卻已成了我的標準輸入方式了。在談它之前，非得先說一下 QWERTY 鍵盤配置，低頭看看你的鍵盤，你應該看到第一行的前六個字母是 Q、W、E、R、T、Y，這正是它之所得到此名的理由。
只是你可能不知道， QWERTY 鍵盤配置一開始其實可能是為了降低打字速度才被發明的。為什麼？因為那時用的是打字機，打的太快會提高故障發生率。而既然現在的鍵盤已無打字機的問題，為什麼不改成一個能打的比較快的設計呢？Dvorak 正是在這樣的情形下發展出來的。
Dvorak 鍵盤配置在 1932 年由 August Dvorak 所創造 ，他又在 1936 年出版了一本長達五百多頁的書(Typewriting Behavior)敘述他對打字的研究 。Dvorak 把最常用的字母都放到了 home row（中間那行），並仔細考慮過手指的移動，以達到加快打字速度的目標（我能找到的最高速度是由 Barbara Blackburn 創下的每分鐘 212 個單字），並減少手指的疲倦，同時，更明顯的，它比起 QWERTY 來的易學。
The Dvorak Simplified Keyboard layout
在 Windows XP 上要使用 Dvorak 很簡單，在語言列上按右鍵，選擇「設定值」，再按下「新增」，在「鍵盤配置/輸入法」選最上面的那個「United States-Dvorak 國際」就是了。
要把登入畫面預設使用 Dvorak 的話則必須到「開始/執行」，輸入 regedit 後按下「確定」，接著找到 HKEY_USERS.DEFAULT\Keyboard Layout\Preload\1 這個鍵，把它的值改成代表 Dvorak 的 00010409。
Windows 7 之後的版本就不必這麼複雜，直接新增「United States-Dvorak 國際」就可以在登入畫面中使用了。
至於中文輸入的問題，如果你跟我一樣是用注音輸入法的話，有一個非常好的選擇：新酷音輸入法。如果是 Windows XP，安裝完了之後同樣利用 regedit.exe 來修改登錄檔，先找到 HKEY_LOCAL_MACHINE/SYSTEM/CurrentControlSet/Control/Keyboard Layouts，接著按下 Ctrl+F 搜尋「新酷音」，你應該會發現有一個名為 Layout File 的字串，它的值是「KBDUS.DLL」，把它改成「kbddv.dll」，重新開機之後，打開新酷音輸入法，到「新酷音輸入法設定/設定新酷音輸入法」，在鍵盤對應的地方選擇「Dvorak」，然後試著打字看看，此時符號和英文字的對應應該都變成和 Dvorak 一樣了。
至於打字教學軟體，當初我選的是 KP Typing Tutor，簡單易用，同時支援 QWERTY 及 Dvorak。如果你願意花錢的話，也可以考慮另一套專業的軟體：TypingMaster Pro，它會詳細分析你的進度，而且介面也十分順眼。
| KP Typing Tutor | TypingMaster Pro |
|---|---|
 |
 |
使用 Dvorak，偶爾會遇到麻煩的地方，尤其是要用公用電腦的時候，所以我一直想稍微加強一下我用 QWERTY 打字的能力（至少要能不看著鍵盤啊），不過一直沒實行，也許人就是懶惰吧，這也是使用 QWERTY 的人不想試試 Dvorak 的原因之一。至於 Dvorak 是否真的比 QWERTY 快？有人堅信，也有人懷疑，我還是再多做點研究再來判斷好了。