在我研究生的时候，我上了一门OpenGL的课程。我非常喜欢OpenGL，因为它让我写的程序从此不再只局限于黑白的终端界面，而变得艳丽多彩。从那么课上，我也第一次认识了“贝塞尔曲线Bézier Curve”，它是那么的神奇，仅仅用几个点通过一个公式就能表现出一条优美的曲线。
这让一直热爱数学的我无法自拔，仿佛又回到了高中，坐在课堂里听着彪哥（我的高中数学老师）给我们讲述着各种曲线方程：抛物线、椭圆、双曲线……可惜怎么就从来没有提到过贝塞尔曲线呢。好吧，不在高考考纲之中。
贝塞尔方程的优点在于可以利用较少的存储几个点就能描绘出光滑的曲线或者曲面。而方程的计算也不会消耗太多的时间，真可谓是图形学中的一把利器。虽然后来并没有继续学习和使用OpenGL，但是也在其它很多方面又再次接触到了贝塞尔曲线，比如CSS中的一些渐变方法(Timing Function)，iOS动画的时间方程。
Read More →
人类有十个手指，所以我们的算数都是10 进制的，而计算机的世界里，所有事物都只由0和1呈现出来，所以数字也只能用2进制表示。因为2进制的表示方式，在计算机里对于数字的运算，除了现实中常用的“加减乘除”，更多了“与非或”这些位运算。
在进行数学运算的过程中，我们经常会总结出一些技巧方法，而这些方法其实跟进制有很大的关系。比如小学老师就告诉我们：检查一个整数能否被3整除，只要派定各个数位上的数字加起来是否能被3；判定一个整数是否能被5整除，只要看最后一位是不是0或5。而这些规律却不能适用到2进制表示的数字上。
不过利用2进制的特殊性，我们也能从位运算上找到很多的技巧。比如一个常见的面试问题：
有一组数包含了1到100的整数，且每个整数只出现一次且随机出现于数组中，现在有一个数被从中删除，请找出被删除的数。
这是一道关于字符串的操作的问题，一开始思考的时候，感觉需要取出各种不同的子序列，如果是这样时间复杂度就会变成指数级别。不过在朋友的指示下，发现其实它是有规律可寻的，最后的算法时间负责度只要O(n)，而且代码极其简单。
虽然朋友是直接告诉了我其中的规律，但是我还是花了点时间思考和证明了一下，才放心的写下了代码。现在把它总结在这里。
整个问题的证明基本是使用数学归纳法，以及奇数和偶数的一些性质。感叹数学的世界真奇妙。也庆幸自己一直以来我十分喜欢数学。其实计算机的世界本来就是建立在各种数学理论之上，比如离散数学，模糊数学，逻辑数学。但是计算机又让数学的应该变得更加的广阔。
(你可以在看完题之后直接跳到红色的部分看这个问题的结论。)
Read More →
在刚进大学学习C语言的时候，用的是谭浩强的那本“经典”教程（之所以加引号是在接触了更多的书籍和经过了高手的指点后，发现它算不上绝对的经典，但是是入门很好的书）。记得好像是在函数那一章的课后习题的第一题让写一个求两个数最大公约数的方法。因为当时是第一次接触C语言不知道这一个经典的题目，所以就直接翻阅答案去了。答案给出的提示就是用欧几里得的“辗转相除法”。当时把那个方法记了下来，只觉得太神奇了，会使用它但是一直没有理解，也不会证明它。
今年开始读研究生，选了Algorithm，相对于本科学习算法，在研究生阶段感觉很多是在复习这些内容，但也有更多的深入证明和学习。就拿gcd（Greatest Common Divisor）来说，在第0章就讲解了很多”模数”的知识和应用，在第三节课就证明了gcd的正确性。
因为gcd算法是一个经典的算法，所以在网上已经有很多关于它的证明方法和各种版本的实现方法。在此重述这些内容，只想巩固和积累一下自己所学到的知识，并方便将来的回顾。因为发现很多学过的内容在许久之后就会忘记，然后就要花很长的时间去找答案（比如大一的时候用得很熟练的求极限的各种公式，现在都想不太起来了，以致在解决问题的时候总是在怀疑做得是否正确）。
Read More →