2010-11-16
最大公约数(gcd):Euclid算法证明及其它
在刚进大学学习C语言的时候，用的是谭浩强的那本“经典”教程（之所以加引号是在接触了更多的书籍和经过了高手的指点后，发现它算不上绝对的经典，但是是入门很好的书）。记得好像是在函数那一章的课后习题的第一题让写一个求两个数最大公约数的方法。因为当时是第一次接触C语言不知道这一个经典的题目，所以就直接翻阅答案去了。答案给出的提示就是用欧几里得的“辗转相除法”。当时把那个方法记了下来，只觉得太神奇了，会使用它但是一直没有理解，也不会证明它。
今年开始读研究生，选了Algorithm，相对于本科学习算法，在研究生阶段感觉很多是在复习这些内容，但也有更多的深入证明和学习。就拿gcd（Greatest Common Divisor）来说，在第0章就讲解了很多”模数”的知识和应用，在第三节课就证明了gcd的正确性。
因为gcd算法是一个经典的算法，所以在网上已经有很多关于它的证明方法和各种版本的实现方法。在此重述这些内容，只想巩固和积累一下自己所学到的知识，并方便将来的回顾。因为发现很多学过的内容在许久之后就会忘记，然后就要花很长的时间去找答案（比如大一的时候用得很熟练的求极限的各种公式，现在都想不太起来了，以致在解决问题的时候总是在怀疑做得是否正确）。
Read More →