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