国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > 互联网 > 编程之美2.7 最大公约数,最小公倍数

编程之美2.7 最大公约数,最小公倍数

来源:程序员人生   发布时间:2014-10-10 08:00:00 阅读次数:1927次

      书中的题目是求两个数的最大公约数,其实这个问题时当我们学习C语言的时候老师就讲过的算法,和教学中的求素数是一个类型的问题。

      我们当时学的方法是 “辗转相除法”,即利用公式: f(x, y) = f(y, x % y),直到 x % y == 0,取x就是两个数的最大公约数。

      但是书中说道,乘除运算太浪费时间了,所以,我们可以换一种方法去思考这个问题,乘除不能用,就只能是加减了,所以,书中利用如果一个数能够同时整除x和y,则必能同时整除x-y和y,所以我们定义x和y的最大公约数是f(x,y),那么依据上面的思想,可以得到f(x,y) = f(x-y,y)。

      函数声明如下:

int DutTheGreatestCommonDivisor(int, int);

      源代码如下:

/* *这里的思想是:如果一个数能够同时整除x和y,则必能同时整除x-y和y,所以 *我们定义x和y的最大公约数是f(x,y),那么依据上面的思想,可以得到f(x,y) = f(x-y,y) */ int DutTheGreatestCommonDivisor(int m, int n) { /*当m小于n时,需要交换两个数字*/ if (m < n) return DutTheGreatestCommonDivisor(n, m); /*当n等于0,时,那么返回m就是最大公约数*/ if (n == 0) return m; else return DutTheGreatestCommonDivisor(m - n, n); }

      既然说到了最大公约数,那么和它相对应的是最小公倍数,不记得是上几年级的时候,我们就学过一个公式,两个数的最小公倍数计算方法是 : (x * y) / 最大公约数(x, y)。

      函数声明如下:

int DutTheLeastCommonMultiple(int, int);

      源代码如下:

/* *最小公倍数可以利用最大公约数得到,数学推导可以看看这个: *http://baike.baidu.com/view/341375.htm */ int DutTheLeastCommonMultiple(int x, int y) { return (x * y) / DutTheGreatestCommonDivisor(x, y); }



生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生