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