您当前位置：首页 > 互联网 > 编程之美2.7 最大公约数，最小公倍数

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

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

书中的题目是求两个数的最大公约数，其实这个问题时当我们学习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); }

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

------分隔线----------------------------

上一篇 Java+Swing+SQL+Server2005开发酒店管理系统源代码下载

下一篇 eclipse新建Maven工程时Nexus Indexer为空问题

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点