2010年12月24日 星期五

讀書心得: 史岱爾莊謀殺案

More about 史岱爾莊謀殺案
本書是克莉絲蒂的出道之作,25歲,我讀完後驚訝極了,文筆爽朗輕快,完完全全就是典型克莉絲蒂風格,絲毫不見一點新手的生澀。能夠一出手就如此夠水準,一方面是佩服,另一方面是懷疑克嬸嬸您一開始就這麼厲害,怎麼進步阿?

看完史岱爾莊謀殺案後,我真的忍不住要說白羅跟海斯汀這偵探與助手的天生搭檔,兩位真是絕配,一個是精明的過份,另一個是蠢的過份。偵探白羅這傢伙老是神秘兮兮的講些怪話,故意不說明白,一邊把讀者弄的身在五里霧中,一邊又不時的奚落他那位搞不清狀況的海斯汀老弟,我說白羅你阿,根本是指桑罵槐,一邊罵海斯汀一邊把讀者罵了個夠吧!難怪吳念真的序文裡出現『我想把那個矮羅壓到馬桶吃屎』的話。另外一邊則是海思汀那個蠢蛋,正直老實沒心機,但是每次看到漂亮美眉就心蕩神馳,冒冒失失的跟人求婚,每當我看到類似橋段我都一直笑。

而經過好幾本推理小說的考驗之後,我的腦袋也有終於稍微有一點進化了,一開始我就精明的發現跟老太婆吵架的對象其實是另有其人,所以我可以說漂亮的繞過了劇情中的第一個陷阱,不過我得意了沒多久,就老老實實的掉進了第二道陷阱裡,最後的謎底真的很難猜阿,哎呀,哈哈。

讀書心得: 高爾夫球場命案

More about 高爾夫球場命案


如果說「東方快車謀殺案」是經典的內斂風格,那麼「高爾夫球場命案」就是完全相反的典型了。「高爾夫案」集合各種暢銷小說要素於一身:名偵探及死對頭、身世成謎的死者、衝突糾葛的人際關係、峰迴路轉的劇情,結尾前的千鈞一髮的高潮橋段,以及...別忘了,主角與偶然邂逅的美麗女孩的愛情對手戲 (百用不爛的典型公式)!害我以為我在看電影劇本。

我這個人讀偵探小說,相當享受那種被當呆子耍的樂趣(就像偵探身旁的助手一樣),當然這個犯案的計畫必須夠高明,否則樂趣就減半了。說到「高爾夫案」這個劇情進展實在太曲折,直到結束前的末幾頁,我都以為要收尾叫警察抓人了,還來了一個一百八十度的絕地大迴轉,完全推翻之前所有推理,更別說之前就經數次劇情迴轉,心情整個就像雲霄飛車一樣。這感覺在我第二次邊讀邊回顧的過程中特別強烈,暗潮之下還藏暗潮,伏筆之中還埋伏筆,一絲不差在恰當的時機揭露開來,克嬸嬸的縝密的劇情組織能力,真的佩服。

不過我這個笨腦袋想不明白的是,到底什麼時候開始,白羅就已經掌握了整個複雜的案情呢?就算讀了兩次,我也還是不明白。

2010年12月21日 星期二

讀書心得: 東方快車謀殺案

More about 東方快車謀殺案
談到「東方快車謀殺案」,就要說起我還是個小大二時,在社辦偶然碰見老爹學長也在讀這本「東方快車謀殺案」,在我隨口探詢大概的故事內容之後,心裡第一個冒出來念頭是「老天,一定是本超無聊的書。」

幾年後,有機會翻開它,整個故事架構一如意料的單調:火車上死了一個人,神探白羅把車廂內的有嫌疑的乘客一個一個抓來問話,篇幅一人一章。思考後又重複訊問乘客一次,破案。當時年紀輕輕的我顯然不能瞭解整本都在問話與找不在場證明的書有什麼好看。所以之後我讀A.B.C謀殺案時,看到書裡白羅自己說道:『如果在第一章兇案就已經發生,而一直看到書中的倒數第二頁都只在追查每個人的不在場證明,這樣的故事實在太冗長乏味。』我看完這句話當場拍桌大笑,阿嘉莎阿姨幽了自己一默,因為白羅這句話正好拿來形容「東方快車謀殺案」,但結論恰恰相反,故事太精采了。

沒有飛車追逐或男女情愛妝點,單調的故事架構,反而凸顯了克莉絲蒂作品最純粹的趣味。白羅探案的特色就是一直對話,在對話中刺探每個人的想法,刺探人心中最微妙的部分。在我看來,阿嘉莎.克莉絲蒂無疑是個觀察入微,洞悉人性的人,光憑對話,就把每個人物形象的刻劃的生動精彩。整個車廂內十多個人,每個人都有不同的國籍,不同的個性,冷靜的英國小姐,聒噪的美國太太,剛毅的俄國公主,死板的德國女僕,以及精明又有些自戀的白羅等等,只消聽聽這些傢伙嘴巴說出的話,馬上整個角色的形象活起來,好像真的站在我眼前一樣。白羅一個一個向列車上的乘客詢問證詞,這樣互相對話就可以寫得讓人欲罷不能。

而推動劇情發展的要素,我想直接引用東方快車董事布克先生的話:「謊言,更多的謊言!」後半段白羅一一揭穿每個乘客的謊言,大概是全書最讓人拍案叫絕大喊痛快的橋段。每個人各懷鬼胎,與白羅嘴巴上你來我往,每次讀我都覺得真是有趣極了。反而最後精巧設計的結局,我印象沒那麼深刻。

讀書心得: Just for Fun : Linux 創始人托瓦茲自傳

More about Just for Fun

不平凡的平凡人

從封面來看,本書出版時是一定是重點企劃項目,不只號稱台美同步發行,還請了五個名人來寫推薦序呢。不過我向來對這種出版社力推的書沒什麼好感。

我想對此書有興趣的人,大多想瞭解兩個問題

一、Linux為什麼會成功 ?
二、Linus Torvalds此公到底是何等人物 ?

第一個問題我推薦大家去看「Rebel Code」(中譯: Linux傳奇) 寫的更全面,更深入。第二個問題嘛,我也推薦大家先去看Rebel Code ,哈哈,為什麼這樣說呢? 因為我自己的就是先讀了 Just for Fun 後,整個有看沒懂。我分析有兩個原因,第一是我不瞭解整個 Linux 開發的背景,所以很多時候 Linus 發表看法,我卻因為不了解時空背景而無法體會。第二個是 Linus 本人實在很謙虛,往往輕描淡寫的帶過自己的事蹟,如果你只聽他自己說的話,那麼很難看出精彩之處。

所以我讀完 Rebel Code 之後,又重讀此書才終於有抓到一些感覺。舉個例子來說,像是 Linus在書裡暢談他對 Linux 社群出現多頭馬車時的處理法,要了解 Linus 說的話,那就得先瞭解 Linux發展的過程中曾經出現過兩次分裂危機,一次是開發 TCP/IP 時,一次是vger事件。看完Rebel code 後我才搞懂整個來龍去脈,事實上,本書也只能知道 Linus 自己片面的說法。

Linus 這個人基本上就是個電腦宅宅,比起一些商場大人物的自傳整本吹噓自己,Linus 平易近人許多。Linus是個務實派駭客,沒有Stallman那種崇高的理念,除了喜歡玩電腦之外,跟一般人沒什麼兩樣。當初開發Linux的原因只是覺得好玩,想要搞懂386晶片的底細,某次陰錯陽差之下,就成了一個真正的作業系統。本書也可以看出 Linus 的帶領原則就是無為而治,而他這樣的個性正好適合Linux這個海納百川的大型開源專案。

Linux的成功固然有些機運,但是絕不僥倖。這位電腦宅宅12歲就開始寫組合語言的驚人事蹟,就別說了。Linus說影響他一生最大的一本書籍就是Tanenbaum寫的『Operating System』,他老媽說「他是個很好養的孩子,只要空出一個衣櫥,塞台電腦進去,外加一點乾麵餅,對他就是人間至樂了」當一個人能夠專心致志成這樣,那只是機會早到晚到的問題。

最近看了電影「三傻」,我赫然發現 Linus 不正是主角蘭切的真實世界版的寫照嗎? Just for Fun。

讀書心得: Linux傳奇 (Rebel Code)

More about Linux 傳奇

Rebel Code 開源革命史

報導文學的傑作!上一次在讀完書後,心中湧現出類似的激動已經是四五年前讀『宇宙的寂寞心靈』的時候,這兩本書的特色就是雖然主題是科學技術,但是內容卻不是側重在技術,而是發生於當中的故事與人物,想要瞭解Open Source發展的人,我認為本書是非讀不可。

原文書名叫做『Rebel Code』,直譯是『叛碼』(一定要吐槽一下糟糕的中文書名,尤其副標題比爾蓋茲云云可說完全搞錯方向)。這個書名非常有意思,因為這兒Code是個雙關,一個意思是程式碼,另一個意思是典律。恰恰代表了本書描寫的兩個對象,以Linux為首顛覆傳統開發方式大獲成功的開源軟體,以及一群奔放不羈、充滿理想的平凡人,運用自己的力量搖動世界成為典範的故事。

從自由軟體的開創者Stallman開始,直到最後Linux成為一方之霸,以Linux的發展作為主軸穿越時空展開了一個長達十年、可歌可泣的故事。看著只曾在課本封面上見過名字的資訊大頭們,例如Linus在討論群組上與Tanenbaum針對作業系統的設計架構針鋒相對的口水大戰,頓時覺得這些人不再是遙遠的天邊的神級人物,也曾是有血有肉有性格的人們。除了Linux之外,著名的開源項目GNU、GCC、Apache、Perl、Mozilla也都在書中占有一定篇幅,本書更可以說是一個全面的開放源碼運動的紀錄。

大教堂與市集

全書的結構分為兩大段,前八章是Linux篳路藍縷的成長過程,第十章後則是Linux一路攻城掠地。而位居中間的第九章是本書的一個高潮,全章以『大教堂和市集』一文為中心,深入淺出的分析了開源自由軟體成功的原因。大教堂與市集代表兩種相互衝突的軟體開發觀點,大教堂是傳統的軟體開發觀:『我相信最重要的軟體必須如建造一座教堂般,由個別的高手或一小群專家在光輝的孤立中小心翼翼地精雕細琢,時機未到之前,不會釋出測試版。』

但Linux完全顛覆了傳統,來自世界各地的烏合之眾打造了高品質的程式:『儘早並經常發表新版本,授權每一件可以委託的事,不拒絕幾乎到混亂程度的程式,...Linux 的同好們似乎組成了喧鬧的大市集,以這個風格發展出來的Linux既一致又穩定,表面上看來真是一連串的奇蹟。』大教堂和市集深切的探討了Linux成功的原因,並把成功的原因歸納成一系列的格言,每句格言都很有意思,不妨一讀。(大教堂與市集全文)

讀完書後,我自己的對開源帶來的軟體革命感想是,其實使用者並不想管軟體本身開不開放,真正關心的是軟體到底合不合乎需要。而開放比封閉更容易貼近使用者的需求。每個人都曾經想過「如果OO軟體有XX功能就好了!」而專利軟體最糟糕的一點就是使用者對這個問題幾乎無能為力,回報給開發者也充滿隔閡。開源軟體的架構下,每個人都可以自己動手添加功能或修復錯誤。當使用者同時也是開發者,兩個角色重疊,軟體最麻煩的需求分析的門檻就降到零了。

同時書中提到一個觀點,開源軟體的知識共享可以免去重複造輪子。Linux之前,很多版本的Unix擁技術各據山頭,收取高額權利金,結果因為Unix版本太多,每家公司都要重新開發一次類似的功能,消耗整個軟體界的能量。最後的下場是便宜的Windows NT一來,風吹樹倒,整個Unix伺服器佔有率掉光光。不過本書也說明開源不是萬靈丹,並不是什麼專案開源之後都會成功。

另外一點,Linux的成功與Torvalds本身個性有很大關係。Linux發展之初,其實有兩個開源Unix互相競爭,分別是Tanenbaum撰寫的Minix,以及Torvalds撰寫的Linux。而勝出的關鍵就在Torvalds的個性極為開放,幾乎任何人送來的patch都來者不拒,還鼓勵大家這麼做。反觀Tanenbaum對修改Minix一直機機歪歪,步調緩慢。群眾自然湧向願意聆聽大眾聲音並改變的Linux。

駭客精神

另外貫穿於全書之中令人敬佩的 - 駭客精神:把金錢擺到次位,一心追求最好的技術、最好的軟體。重視自由、分享、社群精神,關注軟體的創作、美、以及有趣。我覺得這才是整個開源運動最動人的地方。書中有句話『自由軟體即是關心社會』,讓我會心一笑。

本書出版於2000年左右,至今過了十年,有許多後續發展書中未提,像十一章Linux系統採用的版本控制軟體BitKeeper搞出風波後,最終導致git的出現。2001年時被認為是失敗的開源案例Mozilla,現在以Firefox之姿浴火重生,已經是鋒頭最健的開源項目之一。

最後有些問題不得不提,本書編輯很差,第一次看到書的目錄可以印成這樣糟糕。翻譯品質也很差,翻譯者似乎是資訊外行,很多專門的資訊名詞像GPL、CVS、micro-kernel、CSS、DOM,語句中看的出來連譯者自己都不知道在寫什麼,明顯的錯誤,如『妙不可言的人月』其實是著名的軟體工程著作『人月神話』,『HTML標識』應該叫『HTML標籤』,眾多關於作業系統內核的部分也錯誤迭出,我建議本書的翻譯稿也應該開源一下。

註:看完本書,我真的覺得GCC是這個世界上最偉大的軟體之一。

2010年11月29日 星期一

讀書心得: 精通 Objective-C 2.0 程式設計

More about 精通Objective

原文書名: Programming in Objective-C 2.0 (2nd Edition)

以一本程式語言教學的書來說,我給這本書的評價是:水準以上,但是差了那麼一點醍醐味兒。

先談談整體的寫作的風格,可以說平實八穩,依照語言的各種特性,按部就班一個個清楚而且詳細的解釋。內容上本書總共分為三大塊,主題分別是 Objetive-C語言、Foundation Framework (objc的標準函式庫) 以及 Cocoa and iPhone SDK。第三塊的Cocoa只能算淺嘗性質的示範了一個小巧的iPhone程式,全書大部分專注於闡述objc這個"語言",沒有特定侷限於某個平台,對於想快速上手iPhone/iPad開發的人,本書不是個好選擇。

閱讀的過程算相當順暢,除了objc 2.0新增的property我覺得範例過短,必須去網路上搜尋其他資料輔助,大部分都相當清楚作者要傳達的意思。偶爾有一兩句拗口的翻譯句子出現,但整體品質還算相當不錯。全書以數個範例貫穿頭尾,藉由不斷添加功能於其上,引出各式各樣的Objc語言特性,我認為相當好。

本書把Objc當作一個全新的語言來講,而不是C語言的延伸,這對沒學過C的人算是好消息。我個人是已經學了C好多年了,所以這本書到底適不適合完全的新手,我也說不個準。書完全以OO的方式來介紹objc,對於一些舊式C語言的東西如top-level function、pointer並不鼓勵使用。所以全書只留有一章把傳統C語言的特性收集起來做個介紹,算是選讀的章節,沒唸也無傷大雅。這章揭露了一些objc底層的實做,對於熟悉C的人倒是相當有趣的一段。

我說差了點醍醐味兒的原因是我掃完第一遍後,心中有個聲音響起:又一個程式語言!我學的程式語言還不夠多嗎?其實從這本書我對objc的第一印象並不太好,對API函數的命名尤其反感,比如說 Foundation Framework 裡的 NSArray (單純就是個Array class) 存取第三個元素的方法是 [array objectAtIndex 3]; 看到這個方法我差點沒把口中的咖啡噴出來,突然覺得operator overloading真是天上傳來的福音。類似例子多不勝數,例如字串的比對 [str1 isEqualToString str2]; 哎喲,我真的得說服自己在寫程式語言而不是英文作文。

扯遠了,咳,吐槽Objective-C的話題就此打住。總之我認為本書並沒有寫出Objective-C的靈魂來。圖靈獎得主 Alan Perlis 說:「如果一門語言不能影響你寫程式的思維,那它就不值得你去學。」各種語言形形色色,總有它們優秀獨特的地方。但從這本書我看不見Objc為什麼選擇這樣子的語言設計,或者說這樣的特性有什麼好處,比如書裡第九章標題是 Dynamic Typing、Dynamic Biding 書裡寫道『這使它成為很有威力的程式語言,以及辨別它與其他程式語言(如C++)不同之處』,但章節內容舉的例子有如玩具,完全感受不到威力何在。

直到我讀了維基百科的Objective-C條目,才知道原來objc留著Smalltalk的血液,這個程式語言史上赫赫有名的古董。objc採用smalltalk的訊息傳遞(message passing)模型,所以objc帶著一些今日動態語言才有的特性。這樣來看,本書教會了我大部分objc的語法,但維基百科才畫龍點睛般的讓我抓住objc的風格。

就算不傑出,也不能說這本書不好,就是本四平八穩的程式語言入門書吧。

相關連結: Wiki條目 Objective-C

2010年9月4日 星期六

讀書心得: 專業PHP 5程式設計

More about 專業PHP5程式設計

原文書名:Professional PHP 5

如果你受夠了一般坊間的書對PHP物件導向的膚淺介紹,喔,對,就像學生跟老師的class、或者狗跟貓繼承了動物所以都會叫,這種看了好像有點道理,但是完全無法瞭解與網頁程式有什麼相關的屁話,那麼這本書鐵定會給你不一樣的感受。該怎麼說呢,我看過的書裡,真的能「有效」利用物件導向來改善PHP網頁開發流程,這是第一本。

PHP的風格基本上就是大雜燴,html與程式碼夾雜一起。這也無可厚非,因為快速直覺就是PHP的特色。但是你可能很難想像,PHP也可以寫得有組織,有條理,很容易開發跟維護。就像本書的第一部份介紹的:PropertyObject,將資料以物件封裝起來,切開資料庫跟網頁的關聯,於是乎網頁的程式變得很簡潔,很好讀,資料部份的程式也因為集中在一起,很容易維護。這種工具封裝再利用恰巧展現了物件導向的威力,傳統的PHP鐵定做不到的,給當時的我很大的震撼。於是我照著書本的想法自己寫了一個輕巧的資料存取模組,用在網路程式課程的期末專題。起頭碰到很多困難,花了很多時間在調校物件,但一旦工具準備好後,倒吃甘蔗的感覺就來了,最後一天晚上甚至一口氣衝完好多個頁面功能,這是我人生第一次嚐到物件導向的甜頭,原來物件導向真的有用,而且很有用。

在今天PHP Framework滿天飛的狀況來看,這本書的內容其實有些過時了。比方說後來我發現我寫的資料存取小模組原來有個專有名詞叫做ORM,而且網路上有很多高手寫了更好用、更強大的ORM。一些知名框架像CakePHP、 CodeIgniter甚至提供了非常完善的解決方案來組織整個網站。回頭來看這本書的工具,是太陽春了。不過畢竟那都是別人寫好的工具,光使用也不會有什麼長進。有基本的PHP知識,想要一窺這些超級工具開發的秘密,那我認為這本書是非常好、非常難得的敲門磚。程式師圈子裡有句話叫做「Eat Your Own Dog Food」,意思是程式員必須要使用自己開發的工具來改善自己的工作,那本書就是這句話最好的實踐。

本書的內容其實不只這些小工具,還有很多內容像是Design Pattern、SOAP、MVC、專案管理等等,簡直就是包山包海了,個人認為Design Pattern的部份沒什麼有用的例子,後面我則是沒有細看,不好評論。

有些缺點不得不說:其一是code很長而解釋稍嫌不足,而且code實在寫得太醜了,閱讀來實在很痛苦。我想一本教學書把程式碼寫得簡潔清楚,可以大大地增進讀者的胃口。其二是本書讀來很明顯就是分成四塊,這也沒什麼,因為有四位作者嘛,但慘的是這四位顯然配合的不好,以致於書裡產生了 PropertyObject 與 GenericObject 這兩套明明目的差不多,但就是不同的兩套實做。我初讀還困惑了一下。

2010年7月28日 星期三

UVa 10013 Super long sums

解題策略

這題就是基本的大數加法,用一個長度1000000的字串來模擬加法。
由於題目有嚴格限制為M位數,所以字串頭可以直接放高位,省去一般大數反轉過來(str[0]放個位數)的麻煩。

注意

本題嚴格要求必須輸出M位數,即使有前導零也一樣: 例如M=6, 應輸出000123 而不僅僅是123。
每個輸出間都必須有一行空行間隔,這代表除了最後一個case,每個case後面都要多帶一個空行,算蠻常見的ACM格式要求。



2010年7月27日 星期二

UVa 10018 Reverse and Add

解題策略

這題是這樣的,要把輸入的數字反轉,例如1357變成7531,然後與原數相加。直到這個數字變成迴文(palindrome)為止,像是1357+7531=8888,8888就是一個迴文。本題只需要按照著要求計算即可,唯一比較技巧是反轉一個整數 int:reverse()

注意

需要注意變數範圍:至少要 unsigned long 才能容納題目的數字範圍。而printf()、scanf() 與 unsigned long 打交道的代號是%lu。

爭議點

這題有個爭議點是第一個數字到底需不需要判斷回文,舉個例子:
輸入2,那麼該輸出0 2或者1 4?舊版的UVa測資要求必須要輸出1 4,這有些不合常理,新版則是把爭議性測資都拿掉了,所以兩種寫法都能AC。但是在zerojudge.tw上就必須輸出1 4才行。

PS.這題我不小心把某個unsigned long打成int,抓了好久的bug。


2010年6月30日 星期三

讀書心得: 學習的王道

More about 學習的王道

本書的主人翁Josh Waitzkin,是美國一位著名的天才少年棋手,曾拿下多次全美冠軍,由於某些原因,長大後Josh對西洋棋倦勤,轉行打太極拳,令人訝異,他也拿下了一座世界冠軍。他自己發現兩個完全八竿子打不著邊的領域在學習過程中竟然有許多相似之處,於是寫下這本書紀錄他自己的學習方式與心得。

書的前半段我還蠻有共鳴的,一些訣竅像「習數以忘數」、教育者應該扮演引導者的角色而不是權威人士、支持學習論而不是天份論等等,也都是我自己常用的學習撇步。

不過讀到書的後半,我就發現我完全被Josh甩在後頭,連車尾燈都看不到。Josh身段柔軟,非常擅長根據狀況微調自己的心裡,不斷地從失敗中吸取教訓,每次都可以把自己往上昇華一個層次,好像超級賽亞人一、二、三一直變強。我喜歡這本書的一點,就是他很寫實的把學習碰到的困境一五一十的寫下來,所以讀得時候常常可以這樣問自己,如果是我,我會怎麼辦呢?

後半段花很多段落探討心的問題,許多一流選手不只是技藝精湛,而且都有一顆強韌的心,卡斯帕洛夫、麥可喬登都很擅長利用情緒來激發自己表現,高手過招時候心理上微妙的攻防戰,寫得實在精彩。

我沒有很多這種必須跟對手一決死戰的經驗,不過每當我讀到西洋棋賽的時候,我腦子裡浮現的竟然是ACM題,或許是那種緊繃的氣氛吧,哈哈。還有本書最後josh寫他參加台灣世界推手大賽的經歷,我一邊看一邊苦笑,台灣的愛國裁判完全不輸韓國人呀。

其實書裡說,Josh的每盤棋,每場太極拳,他老爸都會錄影起來,說不定充足的自省材料,才是他成功的關鍵?

2010年4月28日 星期三

UVa 548 Tree

解題策略

典型的Binary Tree的題目,牽涉到兩個跟Binary Tree相關的動作
  1. 我們知道只要有 inorder + postorder 就可得唯一的一棵 binary tree。那該怎麼把樹建起來呢 ? 我寫在 build_tree()裡。
  2. 樹建起來之後,該怎麼走這顆樹,才能找出最小路徑呢? 這我寫在 do_summing( ) 函數,遞迴往下累加總和,再回傳最小的樹葉回來。
Tree 天生就是遞迴結構,用遞迴來寫再自然不過了。

注意

Tree原本應該是NULL的地方,我都掛了外部點(External Node),這樣會讓程式碼清爽一些。

2010年4月24日 星期六

UVa 490 Rotating Sentences

解題策略

相當有趣的題目,要旋轉字串90度再印出。注意字串不足的部份要自行補白。
提供一個測資:
aaa    aaa
 bbb  bbb
  cccccc
   dddd
    ee
   f  f
  g    g
   h  h

2010年4月23日 星期五

UVa 455 Periodic Strings

解題策略

這題要找出字串中的最小週期,我的作法比較好玩一些。
首先用兩個指針i,j分別指向字串的頭兩個字母,像這樣:
abcdabcd
↑↑
我的基本想法很簡單,讓i,j之間保持一個固定間距,如果這個間距就是週期,那麼且同步往後移動指針,比對字母,i,j指的兩字母應該要一直都相同。
# 例子:不管何時,兩指針的字母皆同。
abcabcabc
↑  ↑
abcabcabc
 ↑  ↑
abcabcabc
  ↑  ↑

那麼我們的任務就是找出i, j 的間距啦。初始從週期值1開始比對兩字,不同表示尚未找到週期,拉開指針的間距一格 (++j) 。直到兩字相同 buf[i]==buf[j],這時候可能就是字串中的週期出現了,同步移動指針 (++i,++j) 持續往後比對。

這個作法有兩個Special case要考慮
  1. 字串只有一個字母的時候(長度為1),兩根指針還能指去哪,直接return 1。
  2. 有時候字串尾巴會出現一些破壞週期的字母,例如:abcabcabcd,或者hohaho。所以最後必須檢查找到的週期,跟字串長度是否恰好是倍數關係。若不能整除就表示有這種討人厭的破壞字母出現了,週期值直接等於字串長度。

2010年4月21日 星期三

UVa 10082 WERTYU

解題策略

慶祝新書入手,解了書中第一題噴題。盯著鍵盤建好Ascii對應表:如 map['W'] = 'Q',注意空格跟換行不需要換字。


2010年4月18日 星期日

Ruby 快速筆記: Block and Iterator

Block

Block是相當特別的東西,在某些語言裡block被稱做closure,
先看個例子,我需要連續打印"hello"五次,那麼這樣寫就行:
5.times { print "hello" }
# hellohellohellohellohello
Ruby是個純OO語言,所以數字5也有函數可以呼叫,times就是其中之一。
這個例子最常被拿來說嘴Ruby有多麼簡潔。

Block可以看作某種匿名的函數,或者是...一沱程式碼。
{ print "hello" }    # 這就是一個block
Block不能單獨存在,必須掛在function call後面,以供function使用,
例如它附掛在times這個函數後面,而5.times的功用就是連續執行這個block五次!
這程式可讀性實在高。(有什麼比5.times更接近五次?)

Iterator

那這個Block有什麼實際的用途呢?
Ruby裡的Iterator就是用Block來達成。
例如
a = ["apple", "banana", "orange"]  
這是一個字串Array,我們想要遍訪a的各個元素,該怎麼做呢?
a.each { |s| puts s+'is fruit' }

# 執行結果
# apple is fruit
# banana is fruit
# orange is fruit
a.each 這個方法會遍訪array的各個元素(此處就是水果的名稱),並且對每個元素就都調用一次Block。Block開頭處的 |變數| ,就代表當下的的陣列元素,例如上例的 |s|就是各個水果的名稱。這個例子我們將陣列內水果的名稱都打印出來。

以下還有很多例子
(1..100).each { |i| puts i }    # 依序印出數字1~100
('a'..'z').each { |c| puts c }  # 依序印出26個英文字母
[1,2,3,4,5].map { |e| e*e }     # [1,4,9,16,25] 陣列每個元素都取平方

open('aaa.txt').each do |line|  # 檔案逐行讀取
    puts line
end
Block算是相當便捷的用法。

最後一提,Block其實有兩種寫法:
1. do ... end
2. {...}
當然效果是一模一樣。
a.each { |e| puts e }

a.each do |e|
    puts e
end
慣例是block內有多行程式碼用do end,若單行則用{}較緊湊。

2010年4月17日 星期六

Ruby 快速筆記: 流程控制

流程控制都差不多,一般語言該有的都有

if-else 敘述

if weight > 80
    puts "You are too fat!"
elsif weight > 60
    puts "You are ok"
else
    puts "You are too thin!"
end

While範例

Echo程式,會重複你輸入的字句
while line = gets
    puts line
end

For Loop

印出1~10的平方,形式相當簡潔
for i in 1..10
    print i*i
end

# 1 4 9 16 25 ...

倒裝句

比較特別的一點,就是從Perl借來的倒裝句法(後置條件)
可以創造出近似英文敘述的語句,相當漂亮。
puts "Good Job" if price<100
puts "Level Up!" if exp>10000
例如我們想把陣列內元素全部依序pop出來
array = [1,3,5]
while not array.empty?
    puts array.pop
end

#上面那幾行意義完全等同這一句
puts array.pop while not array.empty?
事實上還有個 until loop,剛好判斷條件跟while相反
所以這樣寫效果也一樣
puts array.pop until array.empty?

Ruby 快速筆記: 一個簡單的函數

一個簡單的函數叫 say_hi ,很容易理解。
def say_hi ( name )
    s = "Hello, "+ name
    return s
end
也可以像php一樣把變數嵌到字串裡,用法是 #{變數} 。
但只有""雙引號夾住的字串才會解析,''單引號不會,這點也像php。
def say_hi ( name )
    s = "Hello, #{name}"
    return s
end
Ruby會自動回傳最後出現的變數值,所以return也可以省略。
def say_hi ( name )
    "Hello, #{name}"   #這樣寫效果一樣
end
呼叫的效果
puts say_hi("David")    # "Hello, David"
puts say_hi "Mary"      # "Hello, Mary" 括號也可以省略
省略括號的用法自己看狀況斟酌
如果參數很多,易搞混順序,還是加一下比較好。

Ruby 快速筆記: Hello Ruby

Hello Ruby

不可免俗得來一下 Hello Ruby
puts "Hello Ruby!"  # 螢幕印出 Hello Ruby!
puts跟C/C++的用法一樣,輸出字串到螢幕上並附上一個換行\n。

Ruby有一個蠻有趣的特性,就是呼叫函數時若不會造成歧義,可省略括號。
puts("Hello Ruby")  
puts "Hello Ruby"  # 這兩行意思一樣

這有什麼好處呢?除了少敲幾下鍵盤外,可以讓code看起來更簡單清爽
例如Ruby 的 setter
s = Song.new
s.title="星晴"     # 這行原本是 s.title=("星晴") 
s.singer="周滷蛋"  # 看似直接存取成員變數,其實是透過setter函數
                  # 兼顧了物件的封裝性跟程式碼的可讀性

Ruby Way

Ruby允許函數使用少數幾個特殊符號作為的結尾。
而這些符號都有特殊的意義,例如上面提到的等號(=)通常就拿來作為setter
還有問號(?) 以問號結尾的函數會回傳True/False
2.zero?    # falsev  (是零嗎?)
[].empty?  # true    (陣列是空的嗎?)

驚嘆號(!)代表危險,或者會改動原本的變數值
s = "DAVID"
s.downcase    # 回傳"david" ,但s依然是"DAVID"。
s.downcase!   # s變成"david"

這種規則就叫做 Ruby way

Ruby 快速筆記: Everything is Object

Ruby裡所有的東西都是物件。
包括數字、陣列、字串都是物件。
所以會生出一些看似神奇的用法

# 數字是物件
-55.abs          # 55       (取絕對值)
2.zero?          # false    (是零否?)
10.to_f          # 10.0     (轉成浮點數)
20.to_s          # "20"     (轉成字串)
1.2.round        # 1        (四捨五入)

# 字串也是物件
"KERKER".length  #  6       (取字串長度)
"hello".upcase   # "HELLO"  (轉成大寫)

# Array也是物件
[1,5,2].sort     # [1,2,5]  (陣列排序)
[1,2,3].reverse  # [3,2,1]  (陣列反轉)
a.push("f")      # 作為stack使用

這些用法都很簡單,也很直覺。

2010年4月1日 星期四

UVa 10405 Longest Common Subsequence

Dynamic Programming的基本題 LCS

DJWS的LCS筆記
洪朝貴老師的動態規劃講義

這題我寫了兩種解法
LCS() 是一般的作法,最清楚直接。
LCS_save_memory() 是針對記憶體優化過的算法。

這題唯一要小心的點就是UVa的字串中包含空格。

2010年3月22日 星期一

UVa 587 There's treasure everywhere!

解題策略

給一張藏寶圖,記載著如何找到寶藏的指令,要算出最終寶藏的確切位置跟及離出發點的距離。這題是典型的模擬題,照著題目要求在平面座標上四處移動就行了。

我在兩個地方稍微傷了點腦筋
  1. 這題的input parsing不好做,或者說用c++ std IO有點麻煩。
    operator>>切字串時不能選擇delimeter,用getline 來切也不能設定超過一個delimeter,可是這題偏偏就有兩個-逗點跟句點。我不想自己切,最後就把字串內的逗點跟句點都換成空白,這樣就能用上stringstream了。
  2. 浮點數誤差:這題送去ZJ後,我拿到一個WA結果如下
您的答案為: The treasure is located at (0.000,-0.000).
正確答案為: The treasure is located at (0.000,0.000).
怎麼會有負零呢!?  應該不是負零,是個非常非常小的負數,因為浮點數不夠精確才產生的誤差,加上一個EPS修正就行了。(不過事實上我對EPS的觀念還不是很懂..orz)

解決這兩項大概就沒問題了,AC get。


2010年3月18日 星期四

UVa 371 Ackermann function

解題策略

爛題目,首先光題目就誤導人了,這題不是Ackermann function ,是 3n+1 ,我還特別跑去確認 Ackermann function 的樣子。

然後兩個很爛的陷阱 (題目敘述沒明說)
1. 有可能 L>H。而最後輸出時必須交換成L<=H ,這跟UVa 100 3n+1不一樣。
2. 題目說範圍不會超過long的真正的意思是unsigned long,所以一般 int 會吃WA。

被細節弄得很火。

提供測資
==input==
2000 3000
3000 2000
0 0

==Output==
Between 2000 and 3000, 2919 generates the longest sequence of 216 values.
Between 2000 and 3000, 2919 generates the longest sequence of 216 values.

UVa 10125 Sumsets

解題策略

這題的解法很直接,要找d=a+b+c
用四層迴圈下去跑a,b,c,d就好了 XDDDD

我犯了幾個錯誤
  1. 要找最大符合d (意思是數列中可能出現好幾個符合要求的解),所以迴圈應該由最大元素往下找,第一個找到的解就是答案,我一開始由最小元素往上遞增尋找,拿了WA。
  2. 沒找到解就回傳0,殊不知0也有可能是解: 0 = -5 + 3 + 2,這裡也吃了一個WA,所以我後來改回傳 INT_MAX 作為無解。
這題有負值,所以 -5 = -10 + -2 + 7 ,這樣算一組合法的解。
是比較需要小心的地方。

官網論壇上的(a+b)=(d-c)法,方法複雜很多,卻沒有比較快。


2010年3月1日 星期一

UVa 357 Let Me Count The Ways

147674同樣的題目,順便就吃下來啦
我發現IE會讓我的程式碼排版亂掉,真讓人困擾@_@

UVa 674 Coin Change

典型的DP題,沒有玩什麼花招..
Sagit's C++ 動態規劃
我想我就不需要多解釋了




2010年2月11日 星期四

讀書心得: 線性代數的世界

More about 線性代數的世界
「你不能把蘋果跟橘子加在一起」從某種觀點來說,就是為了想要做這種事,我們才需要向量。」


這是本書第一章第一句話,我一翻開書就噗呲笑了出來,我想我準會愛上這本書。Gilbert Strang 教授貫穿全書的風格,就是用幽默卻精準的語言,娓娓述說線性代數這門學科。

以我個人學習線性代數的經驗,認為學習線性代數必須要從兩方面著手,一是證明,這是前後貫通這們學科的唯一方法,特別是線性代數這座層層相疊,環環相扣的高塔,這讓人學會嚴謹。另一方面則是直覺,你如何從大堆頭的數學式子中看出意義,直搗核心,這讓人思考靈活,學會應用。

有些線性代數的教學太過於偏重證明,我叫它金字塔教學法,從最底層一塊一塊磚慢慢往上蓋、慢慢往上證明。於是乎有這樣的現象:學生知道證明的東西,證明每一步都懂,但是就是無法在腦中成型,或者看不見這些式子的意義,這是因為數學證明的抽象性、嚴謹性犧牲了直覺性(例如線性獨立的證明),若沒有良好的引導,學生往往在真正看清定理的意義之前就先被繁雜的證明打敗了。「我認為線性代數的教學已經變得太抽象了。」這是Strang教授在序裡說的另一句話,我舉雙手同意。

Strang教授說自己在寫書的時候努力做到:致力於解釋,而不是演繹。我研讀下來的感覺也是這樣,Strang教授會先像箭一樣射穿核心觀念,然後佐以例子慢慢的向旁邊擴張解釋,最後才用證明結尾。我舉個例子,固有向量(Ax=ℷx),章節裡是這樣寫:『我們用A去乘時,幾乎所有的的向量都會改變方向,但是有些特殊的非零向量,它的方向仍然跟Ax相同,只是拉長、縮短、翻轉方向或絲毫未動。... 而固有值就是看進矩陣核心的新途徑。』於是乎學習者從一開始就有一個清楚的圖像浮在腦海中,以此作為往下學習的基礎,比抽象的數學式子好太多啦。我認為這是本書的魅力。

優點同時也是缺點,Strang教授把線性代數處理的滑順可口,無可避免的本書的證明就顯得相對虛弱,偏偏證明是線性代數不可或缺的重要部份。書中大多是以歐式空間為基礎來講解,歐式空間容易學習,容易舉例,但是線性代數可以處理的範圍遠超過歐式空間。這種證明帶來的抽象性,正是線性代數的威力所在,但本書很少提到這部分。

不管怎樣,瑕不掩瑜,這是一本少見的優秀又有趣的數學教科書,我相信你也可以在這本書裡找到學習數學的樂趣。:D

2010年2月6日 星期六

UVa 11044 Searching for Nessy

....

UVa 10499 The Land of Justice

解題策略

有關圓形體積的小題目,稍微推導一下即可。

注意

n==1 是特例要處理。變數記得開long long。

UVa 147 Dollars

之前解的,忘了貼上來。
這是個典型的Dynamic Programming問題。
可是我忘記遞迴式是什麼了..囧 改天補上

UVa 492 Pig-Latin

這題的名字也太好笑XDDDD

用finite state machine下去寫蠻容易的。

UVa 414 Machined Surface

睡個覺,突然就想通了。
15分鐘KO! 一次AC,KERKER!

小小地感想




我幾年資工讀下來對電腦這個領域粗淺的了解。
其實每個方塊都是一門必修課,左邊是理論,右邊對應實做,我沒有列網路跟數學。

照理說一個訓練完整的資工系學生有辦法把 

int main(){
    printf("hello world");
    return 0;
}

這樣一段程式,從程式語言語意上的意義,經過編譯器變成機器語言什麼樣子,然後OS如何啟動這支程式,載入,呼叫執行,將觸發哪些機制從靜態執行檔變成活跳跳的Process,在記憶體空間內的位置分配,再進入CPU內部結構,原理,指令集,機器碼怎麼樣在Datapath裡流動,記憶體、磁碟機,最後從Datapath下到基本的加法器、多工器、邏輯閘再到最底層的電子學,環環相扣。

如果能解釋到這裡,那麼電腦的黑盒子之謎也就解開了。
資工系的必修課表其實貫穿天地,萬象歸一。(說穿了都是同一台鬼電腦)

對我來說,CS、魔獸跟0、1從來沒有這麼接近過。


ps.  雖然話說很大,但我還是個嫩咖,偏硬以下實做能力都很差。
ps2. 沒修過compiler實為一大憾事。
ps3. 關鍵是承上啟下的OS跟計組,可惜....?

2010年2月3日 星期三

UVa 114 Simulation Wizardry

難度不高,規則一堆。必須很細心去應付的題目,光是題目敘述就落落長了。
唯一的小陷阱是:不管有沒有撞到牆,每一步ball life都要減一。
剛剛一看Last Modified才發現這題從開始到結束拖了兩個月之久...我的媽呀
繼續朝著連號解題之路邁進 100~114

UVa 11185 Ternary

一魚四吃...哈哈= ="

UVa 488 Triangle Wave

終於寫到傳說中的簡單題:三角波
本題I/O量極大,使用cin/cout者請小心TLE....

2010年2月1日 星期一

Amel Bent - Eye of the tiger



雖然我沒看過洛基
不過這首歌完全展現了氣勢


Risin' up, back on the street
Did my time, took my chances
Went the distance, now I'm back on my feet
Just a man and his will to survive

So many times, it happens too fast
You change your passion for glory
Don't lose your grip on the dreams of the past
You must fight just to keep them alive

Chorus:
It's the eye of the tiger, it's the cream of the fight
Risin' up to the challenge of our rival
And the last known survivor stalks his prey in the night
And he's watchin' us all in the eye of the tiger

Face to face, out in the heat
Hangin' tough, stayin' hungry
They stack the odds 'til we take to the street
For we kill with the skill to survive

chorus

Risin' up, straight to the top
Have the guts, got the glory
Went the distance, now I'm not gonna stop
Just a man and his will to survive

chorus

The eye of the tiger (repeats out)...

2010年1月31日 星期日

UVa 382 Perfection

Special case 1 = DEFICIENT

試著把一些特例抽出來做最佳化,結果反而更糟:(
所以還是回歸最一般的狀況來解了。

2010年1月30日 星期六

Bizarre Love Triangle - by Frente!




中譯歌詞

Bizarre Love Triangle (Everytime i see you falling)


Every time I think of you
I get a shot right thought
Into a bolt of blue
It's no problem of mine
But it's a problem I find
Living the life that I can't leave behind

There's no sense in telling me
The wisdom of a fool won't set you free
But that's the way that it goes
And it's what nobody knows
And every day my confusion grows

Every time I see you falling
I get down on my knees and pray
I'm waiting for the final moment
You'll say the words that I can't say


I feel fine and I feel good
I feel like I never should
Whenever I get this way
I just don't know what to say
Why can't we be ourselves like we were yesterday

I'm not sure what this could mean
I don't think you're what you seem
I do admit to myself
That if I hurt someone else
Then I'll never see
Just what we're meant to be

Every time I see you falling
I get down on my knees and pray
I'm waiting for the final moment
You'll say the words that I can't say

Every time I see you falling
I get down on my knees and pray
I'm waiting for the final moment
You'll say the words that I can't say

UVa 10929 You can say 11

解題策略

數學常識老梗題,快速判斷11的倍數,把奇數位和偶數位相減,結果必為11的倍數。

注意

請通過這個心機測資 00011

UVa 10591 Happy Number

解題策略

所有的Happy Number從第二步開始就一定會降到729以下,也就是999999999的各位數平方和。
所以建個表來儲存計算過的結果完全可行。

我採用的方法比較極端,預先建好一張size=1000的表。
這樣保證找尋Happy Number的過程一定不會超過兩步,有點作弊就是了。

閒聊

一次AC 科科,也不是什麼很難的題目啦。

2010年1月29日 星期五

[推薦] 組合數學系列教學 "點算的奧秘"

偶然發現一個不錯的網站

http://chowkafat.net/Mathtopic.html

「點算組合學」是本人喜愛的數學分支之一,本專題將以循序漸進,由淺入深的方式介紹「點算組合學」的基 本知識和解題技巧。由於本人學識有限,本專題只擬介紹該學科最基礎的知識,包括「排列和組合」、「容斥 原理」、「母函數」、「遞歸關係」等題目。 
本專題旨在介紹筆者所認識的「點算組合學」的有趣知識,因此著重對該學科最基礎定理的直觀理解,而無意 包羅該學科的所有定理,亦無意進行嚴謹的數學推導。讀者如欲對該學科有更深入的認識,可參閱相關的教科 書。

作者用了一系列的文章,清晰淺顯的解釋了組合數學的精華

2010年1月28日 星期四

UVa 343 What Base is This?

一魚三吃
相似度85%的題目

目前是單純的暴力法,應該有辦法把算過的結果cache起來。

2010年1月27日 星期三

UVa 389 Basically Speaking

 一魚兩吃,跟355幾乎一樣的題目。
5分鐘AC。

UVa 355 The Bases Are Loaded

提醒自己,每次WA都要檢查的事情
1. Bounded Condition ex. 0
2. 變數有效範圍 ex. 是不是超出int的有效範圍,必須改用long long ?
不然很浪費時間 哭哭

這題的另外一個感想就是C++ string實在很難用,
從以前就這樣覺得,這次更加深我的印象。

關鍵測資
5 3 0
16 16 7FFFFFFFFFF
10 10 9999
上面這三個都是有效測資(not illegal)

UVa 294 Divisors

這題的加速關鍵就在於質因數分解

例如 360 = 2^3 + 3^2 + 5
那麼360的因數個數就是(3+1)*(2+1)*(1+1)

其實作到質因數分解就可以在UVa拿到AC了
不過ZeroJudge的測資顯然要嚴酷許多
所以我建了質數表增加質因數分解的效率。

我解題時相當程度上參考了Sagit's code
http://www.tcgs.tc.edu.tw/~sagit/acm/view.php?id=294
簡潔易讀的寫法,相當佩服

這題我還有個心得就是gcc -O2 這個參數
對vector的速度影響非常大
我跑這個測資
1
999990000 1000000000
不加-O2: 3.5 sec
有加-O2: 0.8 sec
加了O2後就極為逼近原生array的速度,幾乎看不出效能損失
只要有O2,我以後就可以開心的用vector啦 :D