有些朋友早就向我推荐这本书了，今天下载了第4期的内容看了看。感触还是很大的。不仅启发我们解决问题的思路，而且也培养我们发现问题的意识。不错的书！
1 先看了“瓷砖铺地板”的问题，上一阵去北京看到了希格玛大厦，呵呵，看到这个题目还是蛮亲切的：）“问题出于实际”我们学了这么多年的数学、微积分等，又解决过什么实际问题呢？认识不到一门知识的具体用途时，是学不好这门知识的。这道题建立的差分方程，使我回忆了一大阵当年学过的差分方程的完整解法。本道题目解法不难想到，给我最深的感触就是“学问来自实践”，门捷列夫小时候在玻璃厂工作，看到工人们将不同的物质加入玻璃中形成了不同的颜色与性能，才激发出他认识化学元素的念头，我们很多人从小就被送进学校，有多少人学的都是纸上谈兵的功夫？
现在那么多吊天花板、镶地板砖的工作者，恐怕没有想到这么多，莫非就是从一个角开始铺，到最后铺不开的话就砸成半个？
想到一本”Ruby“的书序中，大致意思是程序员都喜欢做有兴趣的事情，最讨论枯燥的开会，一开会就打瞌睡，趁机休息下，或者在脑子里想刚才编程中遇到的问题。而该书的作者却会想：为什么开会这么枯燥呢？难道不能让它设计得有趣吗？
2 链表相交的问题中指出“实际编程设计工作中，有时需要相交的链表，在释放之前需要我们慎重”。虽然暂时想不到什么情况时需要设计相交的链表，但这个问题无疑是在实际研究开发中提出来的,而且我们以后的开发设计工作中可能也会用到相交链表。同样说明，没有实践，没有深入到动手，发现不了新的问题，甚至新的理论、方法。“相交链表”难道不是一项创新么？厚积而薄发，空想是不会掉馅饼的。
by the way，楼上的朋友谈的寻找两个无环链表的第一个交点的思路好像不是正确的？。
以遍历的方法在O（length（h1）*length（h2）*）的时间复杂度内是可以解决的。在看了“计算字符串相似度”问题后，可以考虑：这个问题如何用分治法或动态规划法实现？
3 从“字符串的相似度”看分治法与动态规划法
文中给除了分治法的解决方法，同时提出了问题：如何解决重复计算问题？这无疑指出了该问题适合于动态规划法的一个特征：子问题重叠。很多朋友都搞不清楚分治与动态规划的区别。我谈谈自己的一点看法。
两者都是把大问题分割成子问题，但分治把问题分成的子问题是独立的，而动态规划不是独立的。我们可以理解为分治用递归实现，动态规划用递推实现，后者的显著特征就是“以空间换时间"，记录了中间的计算结果。
假设strA=（A1,A2,...Am）strB=（B1,B2,...Bn），以c[i,j]表示strA[i..m]和strB[j..m]之间的距离，即问题求解c[1,1]。
由该文中叙述的思路得到
c[i,j]=0 如果i=m+1或j=n+1;
c[i,j]=c[i+1,j+1]如果i<m+1,j<n+1和strA[i]=strB[j]
c[i,j]=max(c[i+1,j+2],c[i+2,j+1],c[i+2,j+2])+1 如果i<m+1,j<n+1和strA[i]！=strB[j]
由此建立算法：
m<-length(strA)
n<-length(strB)
for i<-1 to m
do c[i,n+1]=0
for j<-1 to n
do c[m+1,j]=0
for i<-m downto 1
do for j<-n downto 1
do if str[i]=str[j]
then c[i,j]=c[i+1,j+1]
else c[i,j]=max(c[i+1,j+2],c[i+2,j+1],c[i+2,j+2])+1
c[1,1]即为所求
[此贴子已经被作者于2008-5-11 19:09:34编辑过]
[返回] 计算机科学论坛 →
计算机技术与应用 → 『 编程心得 』 → (第四期获奖名单公布，最新4节的电子版pdf已开放下载) 预览电子版，写书评，赢取《编程之美—微软技术面试心得》(微软亚洲研究院邹欣等主编)，每周送出3本，机会多多！，欢迎参加由博文视点和本站联合举办的有奖征集书评活动
(订阅本版)
2008/5/10 12:58:00
新浪微博
顶端