2010年11月22日
最近看完《C++ Primer》和《Agile Java》，课上学过数据结构和设计模式，有一些了解。现在想学习一些图形，界面相关的知识，想了解游戏是怎么实现的，以及做一些有UI的小程序。但不知道从何处下手，请高手能否给些建议，下一步应该看些什么书，注意些什么问题。另外 要想理解windows等图形操作系统的运行机制，又需要看些什么呢？
谢谢了
posted @
2010-11-22 23:02 yenchieh 阅读(1983) |
评论 (22) |
编辑 收藏
2010年11月19日
Knuth大神酷爱将算法的效率推向极致。今天看在网上看到一个牛人分析KMP算法，写的蛮好，总结一下。
我们知道普通的模式匹配算法，最差情况下复杂度是O(m*n)的（其中n为母串长度，m为子串长度)，因为需要逐一按位匹配。而KMP算法的优越处在于它利用了如下事实：
白色区域为母串A
彩色区域为子串B
我们假设图中子串的淡蓝色区域的数列与母串匹配，下一项（图中灰色区域）与母串当中的下一项不匹配。一般情况下，我们会让母串指针回到原位置然后加一，然后寻求新的可能最大匹配。
好，我们假设上述过程进行顺利，我们找到了第一处长度不小于蓝色区域长度的序列与子串匹配(因为只有在长度不小于才有意义，即可能完成匹配)。现在图中实线双箭头的区域必然与子串虚线双箭头区域匹配。而在上次匹配中，母串与子串的实现双箭头区域是匹配的。
这说明了什么?——子串前后必然存在相等的序列！倘若我们能利用这一事实，则不用让母串指针回到原位置，而是move on.这样就大大简少“不可能完成任务”的比较次数，提高效率，实现优化。
自然，我们就会问，那岂不是要知道子串任意位置的最大前后匹配长度?
对，为了能在遇到不匹配项的时候能有效找到新的起始匹配位置，我们需要事先记录，自此假设用数列P[]记录。但如何高效的找到任意位置的这个值呢?
我们来观察一下可能的情形:
若前一次能够匹配的子串序列为:abab ， 显然P[1] = 0; P[2] = 0; P[3] = 1 ; P[4] = 2;
现假设序列的第五位为a，那么P[5]等于多少呢?由于P[4] = 2 (意味着前面刚好可以划分为相等的两端)，而B[5](数列以1开始记录) = B[1]；所以P[5] = P[4] + 1;
若序列的第五位为b,那我们要怎么找寻P[5]? 既然B[ P[4]+1 ]<>B[5]（意味着新加入的项将导致前后匹配的变短，但至少为0，因为单个数据项a的P[1] = 0），那么我们只能看B[P[P[4]]+1]是否等于B[5].并以此递归进行下去。结果没有一个满足，所以P[5] = 0.
上述过程是一个递归寻找最大匹配的过程。举一个特殊的例子：
已找到abcdeeabcd abcdeeabcd，显然当前最大前后匹配项为abcdeeabcd 若现在加入的为e，显然根据上述递归过程结果最大的前后匹配项伟abcde，满足条件。
小小的总结一下：巧妙处在于注意到存在前后相等的事实以及新的查找能够成功的匹配必然比前一次未成功的匹配长度长。
由于只需要对B进行预处理，所以在给定一个B和一群不同A的情况下，该算法将大大减少执行效率。该算法时间复杂度为O(n)
具体分析过程，将用到时间复杂度的摊还分析中的主要策略，简单地说就是通过观察某一个变量或函数值的变化来对零散的、杂乱的、不规则的执行次数进行累计。可以参考给出的链接地址。
posted @
2010-11-19 01:04 yenchieh 阅读(2247) |
评论 (0) |
编辑 收藏
2010年11月15日
摘要: 晚自习后半段，写了一道数据结构里的练习题——求最大子序列和。其实，一般我们解决问题，为了让思路有条理，总会将问题划分，可以是大问题划分成子问题的形式，也可以是对问题所有结果的一些分类，然后一一解决。由于最近没有使用Java，所以代码用Java实现。依算法效率递增的顺序，其实亦是人本能思考递减的顺序，分别如下：1.以子序列起始元素为划分，寻找该起始元素对应的最大子序列和，然后一一比较，得出最大值。2...
阅读全文
posted @
2010-11-15 00:23 yenchieh 阅读(2000) |
评论 (1) |
编辑 收藏
2010年11月11日
微积分的积分思想，应该是架构在高阶无穷小基础这上。即，虽然划分区块变小，单一区块误差变小，而同时区块数目变多，但是仍然能有效逼近，根本原因在于区块误差是区块变化的高阶无穷小，即，误差比划分缩小得更快，但划分却是与真实对应的。实例便是，函数导数的阶数比函数本身要低，而误差则由高的那一部分产生。
posted @
2010-11-11 15:16 yenchieh 阅读(231) |
评论 (0) |
编辑 收藏
中午，写了一个数据结构的习题：已知前序遍历和中序遍历求该二叉树的后序遍历。总的来说，引出关于递归设计以及二叉树结构上的一些性质的思考。
先说递归的设计，如果说程序设计是数学思想的代码实现（当然，代码有独有的艺术性），那么递归的函数参数的设计则是体现数学思想的关键之一（例如迭代器参数可以清晰体现递归的方法的作用域，并且也可以将递归入口的特殊性和中间过程的调用一体化）。
再说为什么只能由前序（后序），中序推导出后序（前序），而不能由前后序推中序。先看一个简单例子：
上图二叉树与其对折之后对应相同的前序与后序，而中序遍历的结果与二叉树是一一对应的，所以两者对应不同的中序遍历，故前后序无法确定中序。但是更一般化的理由在于，前序，中序，后序都能表述树中的层次关系（或者同一层的左右关系），但是中序以其在顺序上的特殊性，还能蕴含树中不同层次的左右关系，而这对唯一确定一棵树来说是必要条件。
posted @
2010-11-11 14:56 yenchieh 阅读(2263) |
评论 (1) |
编辑 收藏