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项数组，对于每一个可能的项，我们递归的计算所能得到的最大值，然后挑出那些值中的最大项返回。
需要说明的是，上面的代码不应该成为正式的代码，如果按上面的代码画出每次函数调用的二叉树图，就会发现有大量重复的计算来处理同一个问题，其结果就是耗费指数级的时间，因而是低效的。