首页 > 代码库 > openwrt教程 第一章 物联网&openwrt开发概述
openwrt教程 第一章 物联网&openwrt开发概述
转载请注明出处:http://blog.csdn.net/ns_code/article/details/28505569
序言
求两个正整数的最大公约数是一个很古老且很基本的问题,欧几里得在其著作《几何原本》中给出了高效的解法——辗转相除法,也叫做欧几里得算法。下面我们来看下求最大公约数的一些方法。
方法一
我们先来看欧几里得的辗转相除法。原理很简单,假设用f(x,y)表示x和y的最大公约数,我们令x>y,则有x=ky+b,如果一个数能够同时整除x和y,则必能同时整除b和y,而能够同时整除b和y的数也必能同时整除x和y,即x和y的公约数与b和y的公约数相同,因此二者的最大公约数也相同,则有f(x,y)=f(y,x%y),一直辗转相除,最终当其中一个为0时,剩下的另一个就是二者的最大公约数。一个例子如下所示:
f(42,30) = f(30,12) = f(12,6) = f(6,0) = 6
辗转相除法的代码实现如下:
/* 欧几里得算法,辗转相除求最大公约数 */ int MaxYue1(int a,int b) { //在辗转相除之前,确保a比b大 if(a<b) { int temp = a; a = b; b = temp; } //辗转相除法球最大公约数 while(b!=0) { int temp = a%b; a = b; b = temp; } return a; }该方法用到了取模运算,编译器在执行取模运算时,会转化为相应的除法运算,如:x%y = x - (x%y)*y,除法运算的开销很大,尤其对于大的整数。
方法二
为了避免除法运算带来的大的开销,我们可以用辗转相减法来实现,同样利用的原理如下:如果一个数能够同时整除x和y,则它必能同时整除x-y和y,因此最大公约数f(x,y) = f(y,x-y),注意要保证左边的数大于右边的数,如果小于,则将二者进行交换。
辗转相减法的实现代码如下:
/* 辗转相减法求最大公约数 */ int MaxYue2(int a,int b) { if(a<b) return MaxYue2(b,a); if(b==0) return a; else return MaxYue2(b,a-b); }该方法虽然避免了除法操纵带来的大的时间开销,但是对于大的整数,也要进行很多次的相减操作,尤其遇到两个数相差很大的情况,比如f(1000000,1)这样的情况,迭代相减的次数就会很多。
方法三
为了减少迭代的次数,我们考虑对上述算法进行改进,很明显,我们可以有如下结论:
1、当x、y都为偶数时,f(x,y) = 2*f(x/2,y/2)
2、当x为偶数,y为奇数时,f(x,y) = f(x/2,y)
3、当x为奇数,y为偶数时,f(x,y) = f(x,y/2)
4、当x,y多为奇数时,f(x,y) = f(y,x-y)
每一次的操作必然是以上四种情况的其中一种,且我们对乘2和除2的操作可以通过移位来完成,效率很高,很明显这种算法最坏情况下的时间复杂度为O(log2max(x,y))(以2为底,max(x,y)的对数),很适合对大的整数进行计算。
这种方法实现的代码如下;
/* 改进辗转相减法 */ int MaxYue3(int a,int b) { if(a<b) return MaxYue3(b,a); if(b==0) return a; else { if((a&1)==0) //a为偶数 { if((b&1)==0) //b也为偶数 return (MaxYue3(a>>1,b>>1)<<1); else //b为奇数 return MaxYue3(a>>1,b); } else //a为奇数 { if((b&1)==0) //b为偶数 return MaxYue3(a,b>>1); else //b也为奇数 return MaxYue3(b,a-b); } } }