2006年2月12日
#
今天開google主頁的時候看到這篇文章的，來源于http://blog.joycode.com/zhanbos/articles/67129.aspx。需要說明的是上面blog也是引用別人的，所以我也不知道這篇文章的具體來源，只知道作者是女子嫣然。感謝作者為大家帶來這優美的字句，情人節來臨前夕，貼上這篇詩意綿綿的文章，祝愿各位程序員朋友，各位生活中的朋友，各位尚單身的朋友，各位已擁有愛情的朋友，情人節快樂！
標題：但愿人長久 千里共嬋娟
作者：女子嫣然
又是一年中秋夜，不知又要惹起世人多少相思愁......
但愿人長長久 千里共嬋娟......
一個人來到這個未知的世上，要經歷多少呢？那些曾經經歷過的——曾經得到過的、曾經失去的、至今還陪伴在我們身邊的。想想吧，前世五百年的回眸才換來今生的擦肩而過，前世千年的等待、千年的柔情啊，才換來對方不知道的片刻溫存！！所以，我們該要何等的惜緣??！不要刻意追求那么多，不要苛求難實現的！就讓一切美麗著吧！
有人說，錯過的總是最好的，失去的都是最珍貴的，放棄的都是不忍的。
有人說，愛，不如相知，與其執著癡念，不如化為祝福。不要讓你愛的人，被你的愛所磨蝕；反過來，以你的愛，讓他得到力量，展翅高飛！就算分隔兩地，心仍會在一起。
有人說，真正愛一個人，必定以他的幸福，當作是你的幸福。若然有人，能比你給予他更大的幸福，你就把他送到那里去。
有人說，愛情是個模糊的概念，沒有人去測量過愛情的長度。也沒有任何人得到過具體的結果。如果假定愛情的全程為1公里。那么愛與不愛的距離只有四分之一米。短暫而遙遠的旅途。一堵墻的距離，一堵看不見摸不到卻實實在在的存在的墻，夾在愛與不愛之間。愛人就在眼前，但無力去擁抱。愛人就在隔壁，在空氣中隔離。半步的距離，那怎么也邁不出去的的半步。愛了，勇敢的去追尋，卻碰了壁。不愛，毅然的想離去，發現迷了路。原來愛與不愛同在一個屋檐下，如同長椅兩邊的坐客，只有短短的隔距，然而好象只是一場巧遇，因為疲憊找尋到同一個歇腳處。離去時相眸一眼，意識到這是莫名的緣分，卻走向相反的方向。也許面對愛的時候，不愛就站在背后注視著轉身的瞬間，當轉身與不愛相視的時候，愛依然佇立，流淚，惋惜……原來愛與不愛之間的四分之一米的距離就是自己的身軀……
只有前世有約的人，今生才能相隨。
這世上有誰在憑欄？盈盈橫塘畔的樓臺上，倚著朱紅的欄桿，不經意卻是很美地在笑，這個時候我便想起詩書上的話：巧笑倩兮，美目盼兮。說的，就是我罷？
這世上，有誰在走？也許，那就是你吧？蒼涼景物，滾滾紅塵，一襲青衫，奔波在如煙的暮雨中，斜斜的傘，遮著黃昏細雨。一條青色磚石路鋪就的深巷，由遠及近，獨自彷徨在悠長，悠長又寂寥的雨巷，希望飄過一個丁香一樣地結著愁怨的姑娘。
一種無從提問無從回答的感覺。
是一種預感的實現，是一種冥冥之中的昭示，不曾謀面，又似曾相識。
是永恒也是剎那，是真實也是虛幻，這世間有我不曾明白的神秘。
輪回中，終于不期然地遇見。在茫茫人海。心與心之間，一下子就沒了距離。 假如有一種時刻覺得美好，那一定是誰穿越時空的祝福。
緣，不是說來就來，卻是說走就走的！所以，隔岸而立，所有的美麗因相望而成緣，所有的無奈因相忘而失緣。我們最終都注定要迷失在永恒的輪回之中。
只有前世有約的人，今生才能相隨。
菩提樹下，也許終于有一天，我們會領悟這——如夢的塵緣。
前世積攢多少次的回眸啊，才能換得相識？甚至相知？甚至相愛？
2006年2月6日
#
貓撲上看到的一道面試題，大家討論討論：張老師的生日是M月N日，
2人都知道張老師的生日是下列10組中的一天，
張老師把M值告訴了小明，把N值告訴了小強，
張老師問他們知道他的生日是那一天嗎？
3月4日 3月5日 3月8日
6月4日 6月7日
9月1日 9月5日
12月1日 12月2日 12月8日
小明說：如果我不知道的話，小強肯定也不知道
小強說：本來我也不知道，但是現在我知道了
小明說：哦，那我也知道了
請根據以上對話推斷出張老師的生日是哪一天
看了一下貓撲上的分析，答案主要集中在6月4號和9月1號的爭論。個人認為是9月1號哈。
2006年1月4日
#
對UNIX程序設計很不了解，希望通過慢慢翻譯這本書，一方面學習UNIX系統程序設計，一方面鍛煉自己的英語能力！
歡迎大家指出我翻譯不正確的地方，哪怕是一小點點都十分感謝！
點擊這里查看《UNIX環境高級編程（第二版）》翻譯。
2006年1月3日
#
在上一篇《背包問題 －－ 1) 思路，遞歸求解》中，我們討論了用遞歸的方式來解決背包問題。但是，直接使用遞歸會造成大量的重復運算，就上一篇中的例子來說，對于容積為17的背包來說，其中兩種組合方案為：
方案一： 4(A) + 5(B) = 9 ，即背包中裝一個A物品和一個B物品；
方案二： 5(B) + 10(C) = 15 ，即背包中裝一個B物品和一個C物品；
注意，上面兩種方案都需要計算knap(space = cap - item[1].size)（注：1對應B物品）的情況，這就造成了重復計算，而且計算量是成指數增長的。如果我們在第一次計算knap(space = cap - item[1].size)時就保存其返回值，那么在下一次需要用到的時候只需要直接使用這個返回值就行了，而不必再去計算。
這里我們給出動態編程的定義，即遞歸程序中，在每一步遞歸調用前使用已計算的值來完成當前的遞歸調用。
對于背包問題，我們用一個數組knowKnap[M]來保存每一個可能的space值。按動態編程改進后的程序源代碼如下：
最近看了《算法I－IV（C++語言描述）》中關于動態編程求解背包問題的部分，感覺書中描述的不是很詳細，在這里通過我個人的理解再加上書中的描述，再重溫下這一經典問題的動態編程求解方法。
所謂的背包問題，可以描述如下：一個小偷打劫一個保險箱，發現柜子里有N類不同大小與價值的物品，但小偷只有一個容積為M的背包來裝東西，背包問題就是要找出一個小偷選擇所偷物品的組合，以使偷走的物品總價值最大。我們可以定義以下結構：
struct Item {
int size; //保存物品大小
int val; //保存物品價值
};
例如有下表中的物品：
|
Index |
0 |
1 |
2 |
3 |
4 |
|
Item |
A |
B |
C |
D |
E |
|
Size |
3 |
4 |
7 |
8 |
9 |
|
Val |
4 |
5 |
10 |
11 |
13 |
上表中第一行（Index）是物品在程序中的索引號，第二行（Item）是物品的標示，第三行（Size）是物品的大小，第四行（Val）是物品的價值，而每一列又對應了一類物品。假設小偷背包的容積為17，則小偷能夠拿走5個A價值為20的物品，或者1個D和1個E，價值為24的物品，等等。
為了使小偷在背包容積為cap的情況下，能夠偷走最大價值的物品，我們可以假設小偷足夠聰明，無論背包容積cap為多少，小偷總能找到最優的組合使背包中所裝物品的價值最大。
倘若我們定義函數：
int knap( int cap );
該函數的返回值為容積為cap的背包所裝物品的最大價值。對于cap為17的背包，因為有5類物品，所以所裝物品的價值有以下組合：
1） 4 + knap( 17 - 3 )，即 item[0].val + knap(cap - item[0].size);
2) 5 + knap( 17 - 4 )，即 item[1].val + knap(cap - item[1].size);
3) 10 + knap( 17 - 7 )，即 item[2].val + knap(cap - item[2].size);
4) 11 + knap( 17 - 8 )，即 item[3].val + knap(cap - item[3].size);
5) 13 + knap( 17 - 9 )，即 item[4].val + knap(cap - item[4].size);
因為小偷已經幫助我們找到了cap = cap - item[i].size的最優組合，所以我們只需要找到item[i].val + knap(cap - item[i].size)的最大值也就完稱了我們的任務了。
下面的程序代碼是按以上的思路編寫的：
我么定義了一個類型為Item的N項數組，對于每一個可能的項，我們遞歸的計算所能得到的最大值，然后挑出那些值中的最大項返回。
需要說明的是，上面的代碼不應該成為正式的代碼，如果按上面的代碼畫出每次函數調用的二叉樹圖，就會發現有大量重復的計算來處理同一個問題，其結果就是耗費指數級的時間，因而是低效的。