今天在做一个很简单的算法题目，“求最大公约数和最小公倍数”。一看，太tm容易。
思考过程是这样的：
1.最大公约数，有两个个极端，一个是最大公约数是1，一个最大公约数是两个数之间较小的那个数。
2.我就理所当然地认为，so easy。不就一个for循环吗？从较小的那个数到1的这一段范围就，如果其中一个数能被较大的数整除不就ok罗，然后返回到那个数，不就得到最大公约数啦。
3.然后兴致冲冲地写下下列的代码
public static void commonDivisor(int n,int m) { //其中n,m是所求的数字,当n%i取模等于0的时候,再判断m%i等于0的时候,i就是m和n的最大公约数 for(int i=n;i>0;i--) { if(n%i==0&&m%i==0) { System.out.println(n+"和"+m+"的最大公约数是:"+i); break; } } }
--------------------------------------------------羞耻的分割线--------------------------------------------------------------
我看到网上的答案整个人都醉了,这tm是什么意思？
public static int gcd(int m,int n) { while(true) { if((m=m%n)==0) return n; if((n=n%m)==0) return m; } }
看到这个代码，猛然发现这个是我之前学过一个数学定理---欧几里得算法（辗转相除法），可以最快得到最大公约数，具体的推导过程就不说了。http://baike.baidu.com/view/1241014.htm?fr=aladdin
以前觉得好像数学在编程的用处不是很大（原谅我其实一直菜鸟来着）。现在两段简单代码里面蕴含的思想就差别很大了。我写的是从时间复杂度是O（n），网上的是5log(N)。
一个用蛮力，一个巧用劲。
一个简单粗暴，一个站在巨人的肩上。
一个时间复杂度大，一个如此的快乐单一。