北京企业建设网站公司简介,三门县住房和城乡建设规划局网站,桐城市做网站,51推广平台转载自 玻璃猫 程序员小灰
大四毕业前夕#xff0c;计算机学院的小灰又一次顶着炎炎烈日#xff0c;
去某IT公司面试研发工程师岗位……
半小时后#xff0c;公司会议室#xff0c;面试开始…… 小灰奋笔疾书#xff0c;五分钟后……
小灰的思路十分简单。他使用暴力…转载自 玻璃猫 程序员小灰
大四毕业前夕计算机学院的小灰又一次顶着炎炎烈日
去某IT公司面试研发工程师岗位……
半小时后公司会议室面试开始…… 小灰奋笔疾书五分钟后……
小灰的思路十分简单。他使用暴力枚举的方法试图寻找到一个合适的整数 i看看这个整数能否被两个整型参数numberA和numberB同时整除。
这个整数 i 从2开始循环累加一直累加到 numberA 和 numberB 中较小参数的一半为止。循环结束后上一次寻找到的能够被两数整除的最大 i 值就是两数的最大公约数。
事后垂头丧气的小灰去请教同系的学霸大黄……
辗转相除法 又名欧几里得算法Euclidean algorithm目的是求出两个正整数的最大公约数。它是已知最古老的算法 其可追溯至公元前300年前。
这条算法基于一个定理两个正整数a和bab它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和2525除以10商2余5那么10和25的最大公约数等同于10和5的最大公约数。
有了这条定理求出最大公约数就简单了。我们可以使用递归的方法来把问题逐步简化。
首先我们先计算出a除以b的余数c把问题转化成求出b和c的最大公约数然后计算出b除以c的余数d把问题转化成求出c和d的最大公约数再然后计算出c除以d的余数e把问题转化成求出d和e的最大公约数……
以此类推逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算直到两个数可以整除或者其中一个数减小到1为止。
五分钟后小灰改好了代码……
更相减损术 出自于中国古代的《九章算术》也是一种求最大公约数的算法。
他的原理更加简单两个正整数a和bab它们的最大公约数等于a-b的差值c和较小数b的最大公约数。比如10和2525减去10的差是15,那么10和25的最大公约数等同于10和15的最大公约数。
由此我们同样可以通过递归来简化问题。首先我们先计算出a和b的差值c假设ab把问题转化成求出b和c的最大公约数然后计算出c和b的差值d假设cb把问题转化成求出b和d的最大公约数再然后计算出b和d的差值e假设bd把问题转化成求出d和e的最大公约数……
以此类推逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算直到两个数可以相等为止最大公约数就是最终相等的两个数。
五分钟后小灰重写了代码……
众所周知移位运算的性能非常快。对于给定的正整数a和b不难得到如下的结论。其中gcb(a,b)的意思是a,b的最大公约数函数
当a和b均为偶数gcb(a,b) 2*gcb(a/2, b/2) 2*gcb(a1, b1)
当a为偶数b为奇数gcb(a,b) gcb(a/2, b) gcb(a1, b)
当a为奇数b为偶数gcb(a,b) gcb(a, b/2) gcb(a, b1)
当a和b均为奇数利用更相减损术运算一次gcb(a,b) gcb(b, a-b) 此时a-b必然是偶数又可以继续进行移位运算。
比如计算10和25的最大公约数的步骤如下 整数10通过移位可以转换成求5和25的最大公约数 利用更相减损法计算出25-520转换成求5和20的最大公约数 整数20通过移位可以转换成求5和10的最大公约数 整数10通过移位可以转换成求5和5的最大公约数 利用更相减损法因为两数相等所以最大公约数是5
在两数比较小的时候暂时看不出计算次数的优势当两数越大计算次数的节省就越明显。
最后总结一下上述所有解法的时间复杂度
1.暴力枚举法时间复杂度是O(min(a, b)))
2.辗转相除法时间复杂度不太好计算可以近似为O(log(max(a, b)))但是取模运算性能较差。
3.更相减损术避免了取模运算但是算法性能不稳定最坏时间复杂度为O(max(a, b)))
4.更相减损术与移位结合不但避免了取模运算而且算法性能稳定时间复杂度为O(log(max(a, b))) 本文原本只写到辗转相除法就终告结束后来伯乐在线网友们指出还有更优化的解法看来自己还是才疏学浅很感谢大家指出问题。另外方法的参数默认必定是正整数所以在代码中省去了合法性检查。
文中描述的更相减损术是简化了的方式。在九章算术原文中多了一步验证如果两数都是偶数计算差值之前会首先让两个数都折半使得计算次数更少。这种方法做到了部分优化但古人似乎没想到一奇一偶的情况也是可以优化的。
由于篇幅所限本文省略了关于辗转相除法原和更相减损术的原理及证明。其实证明过程并不复杂细心的同学们也可以自己尝试研究一下。谢谢大家的捧场
