2012-05-03
画虎画皮难画骨，编程编码难编译
古语“画虎画皮难画骨”，是说画老虎时要画它的外表很容易，可要将老虎的气势画出来却很难。
对于现在的程序员来说，似乎也是这样子，可以写出整洁的代码，设计出优异的程序，但却不一定需要知道代码在编译之后的是如何运行的。
但是有时候，能了解表面背后的故事，知道一些程序编译过程，其实对写出一个正确的正确的程序会有很大的帮助，这起源自一段很简单的问题实现：两整数交换。
Read More →
2012-04-13
String Redution问题的分析
这是一道关于字符串的操作的问题，一开始思考的时候，感觉需要取出各种不同的子序列，如果是这样时间复杂度就会变成指数级别。不过在朋友的指示下，发现其实它是有规律可寻的，最后的算法时间负责度只要O(n)，而且代码极其简单。
虽然朋友是直接告诉了我其中的规律，但是我还是花了点时间思考和证明了一下，才放心的写下了代码。现在把它总结在这里。
整个问题的证明基本是使用数学归纳法，以及奇数和偶数的一些性质。感叹数学的世界真奇妙。也庆幸自己一直以来我十分喜欢数学。其实计算机的世界本来就是建立在各种数学理论之上，比如离散数学，模糊数学，逻辑数学。但是计算机又让数学的应该变得更加的广阔。
(你可以在看完题之后直接跳到红色的部分看这个问题的结论。)
Read More →
2012-04-01
二分查找法的实现和应用汇总
在学习算法的过程中，我们除了要了解某个算法的基本原理、实现方式，更重要的一个环节是利用big-O理论来分析算法的复杂度。在时间复杂度和空间复杂度之间，我们又会更注重时间复杂度。
时间复杂度按优劣排差不多集中在：
O(1), O(log n), O(n), O(n log n), O(n2), O(nk), O(2n)
到目前位置，似乎我学到的算法中，时间复杂度是O(log n),好像就数二分查找法，其他的诸如排序算法都是 O(n log n)或者O(n2)。但是也正是因为有二分的 O(log n), 才让很多 O(n2)缩减到只要O(n log n)。
Read More →
2010-11-16
最大公约数(gcd):Euclid算法证明及其它
在刚进大学学习C语言的时候，用的是谭浩强的那本“经典”教程（之所以加引号是在接触了更多的书籍和经过了高手的指点后，发现它算不上绝对的经典，但是是入门很好的书）。记得好像是在函数那一章的课后习题的第一题让写一个求两个数最大公约数的方法。因为当时是第一次接触C语言不知道这一个经典的题目，所以就直接翻阅答案去了。答案给出的提示就是用欧几里得的“辗转相除法”。当时把那个方法记了下来，只觉得太神奇了，会使用它但是一直没有理解，也不会证明它。
今年开始读研究生，选了Algorithm，相对于本科学习算法，在研究生阶段感觉很多是在复习这些内容，但也有更多的深入证明和学习。就拿gcd（Greatest Common Divisor）来说，在第0章就讲解了很多”模数”的知识和应用，在第三节课就证明了gcd的正确性。
因为gcd算法是一个经典的算法，所以在网上已经有很多关于它的证明方法和各种版本的实现方法。在此重述这些内容，只想巩固和积累一下自己所学到的知识，并方便将来的回顾。因为发现很多学过的内容在许久之后就会忘记，然后就要花很长的时间去找答案（比如大一的时候用得很熟练的求极限的各种公式，现在都想不太起来了，以致在解决问题的时候总是在怀疑做得是否正确）。
Read More →