计算机科学论坛--(第四期获奖名单公布，最新4节的电子版pdf已开放下载) 预览电子版，写书评，赢取《编程之美—微软技术面试心得》(微软亚洲研究院邹欣等主编)，每周送出3本，机会多多！，欢迎参加由博文视点和本站联合举办的有奖征集书评活动

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

有些朋友早就向我推荐这本书了，今天下载了第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编辑过]

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

上一次写的书评没有得奖心里不平死了！！只能用一句话总结这本书，完美有味是一本好书！！

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

“子数组最大乘积”中体现的“抓住问题本质”的精神
  我觉得，这个题目并非受过高等教育，系统学习过算法等相关计算机理论的人才能理解或者解答；同时，即使是大学生也不一定能够解答小学数学寒假作业中的思考题！
  首先，谈谈中国对创新意识的忽略和扼杀。记得从高中时候开始，漫天喊着“发散思维，要创新”！正像有一年的高考作文题目“答案是丰富多彩的”，似乎也正是这个时候，国人开始逐渐肯定教育中的创新意识。有篇文章讲的故事：有一个寓言，主要是说小羊成功的识破了大灰狼的乔装打扮，没有被吃掉；有个学生说寓意是做一件事情要充分准备才能成功，而标准答案是要认真观察才能识破敌人的阴谋，该生不仅没得分，还受到了批评。我曾经有个小学同学，二年级的时候就在自己的小房间里安了个小灯泡，用打开门时角度的大小控制灯的亮度，就是这个一个动手能力强的奇才，因为考试成绩差而不得不在四年级时辍学，现在在家开了个修理摩托车的店。我的结论是，培养创新人才，教育至关重要，引导至关重要，一本好书也至关重要！读研以前，在我16年的学生生涯中，我还极少看到引人入胜的学习书籍，无不是在枯燥和应付中度过。这使我们失去的不仅是知识，而且还有自信。相信很多朋友虽然学了不少书，抑或也编了不少程，但谈起算法的考察仍然会心虚不已，也时常质疑：到底什么是算法？哪里才能用到算法？
  “子数组最大乘积”的解决中，症结直指时间复杂度和空间复杂度，这也是算法要解决的本质。能解决问题和能更好的解决问题，往往是凡人和高手的区别。对于高考数学来说，很多人都觉得时间不够用：如果在给我足够的时间的话，我能得到更高的分数。其实，在解题过程中，一般人都会按部就班的进行，而高手往往能静思继而发现问题的本质，从而后发而先至，提高了解题速度。显然“子数组最大乘积”能够在O（n^2）的时间复杂度内完成，但线性时间复杂度的解决方案不是更令人拍案惊奇么？
  这本书能够带领我们多角度的思考问题，是一种不可多得的收获。读者可否觉得：这些思路我也能看懂，但为什么我想不到呢？创新是一种意识，从而成功成为一种习惯。相信这本书能够有力的培养读者多角度的思考习惯，从症结看问题的思考习惯，提高读者“抓住问题本质”的习惯和能力。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

等待着，等待着……
我等待着我的奖品，一本有生以来第一次网络活动的奖品
——属于我的《编程之美》

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

心情同 Humphrey

另外 To DMman:
关于无环求交点的问题，你那个方法稍稍有点复杂吧，我那个思路的复杂度我觉得应该是
O(Length(m) + length(n) + ...), 这个是加号不是乘号呢。
大概思路为:

M:            －－－－－－－－
                             |
                               －－－－－－－－－－－－
                             |
N:    －－－－－－－－－－－－
N步进到这： ^ , 即 |length(m) - length(n)|.
然后同时步进，直到2个指针相等^
其中没有任何嵌套的操作，所以就不会有乘法运算了。
欢迎继续讨论。：）

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

恩你说得对我把相交的定义理解成交叉了

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

谢谢lz，一定好好看

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

多谢，多谢！！

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

感谢，今天已经收到书了。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	125.000ms