一根点燃的香烟图片:一步一步写算法（之 最大公约数、最小公倍数）

来源：百度文库 编辑：偶看新闻 时间：2024/04/30 01:44:00

一步一步写算法（之 最大公约数、最小公倍数）

分类： 数据结构和算法 2011-11-19 21:04 265人阅读 评论(5) 收藏 举报

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】


    求解最小公倍数和最大公约数是我们开始编程的时候经常需要练习的题目。从题面上看，好像我们需要求解的是两个题目，但其实就是一个题目。那就是求最大公约数？为什么呢？我们可以假想这两个数m和n，假设m和n的最大公约数是a。那么我们可以这样写：

    m = b *a；

    n = c * a;

    所以m和n的最小公倍数就应该是a*b*c啊，那不就是m * n / a，其中m和n是已知的，而a就是那个需要求解的最大公约数。所以就有了下面的代码，

view plaincopy to clipboardprint?

  1. int GetMinCommonMultiple(int m, int n)  
  2. {  
  3.     assert(m && n);  
  4.   
  5.     return m * n / GetMaxCommonDivide(m, n);  
  6. }  
    下面就可以开始最大公约数的求解。其实，关于最大公约数的求解，大家看到的更多是各种捷径，比如说欧几里得法。欧几里得法构思十分巧妙，它利用了m、n和n、m%n之间的最大公约数是相等的这一重要条件，充分利用替换的方法，在 m%n等于0的那一刹那，获得我们的最大公约数。然而，我们平时自己所能想到的方法却不多，下面的方法就是具有典型意义的一种：

    a） 首先对数据m和n判断大小，小的赋值给smaller，大的赋值给larger

    b）index索引从2开始到smaller遍历，发现有没有数据可以同时被两者整除，有则更新数据

    c）循环结束后，获取最大的公约数

view plaincopy to clipboardprint?

  1. int GetMaxCommonDivide(int n, int m)  
  2. {  
  3.     int index;  
  4.     int smaller;  
  5.     int larger;  
  6.     int value;  
  7.     assert(n && m);  
  8.   
  9.     if(n > m){  
  10.         larger = n;  
  11.         smaller = m;  
  12.     }else{  
  13.         larger = m;  
  14.         smaller = n;  
  15.     }  
  16.   
  17.     value = 1;  
  18.     for(index = 2; index <= smaller; index++){  
  19.         if(0 == (smaller % index) && 0 == (larger % index))  
  20.             value = index;  
  21.     }  
  22.   
  23.     return value;  
  24. }  
    上面的代码看似没有问题，但是还是留下了一个遗憾，如果m和n的数据都大于32位，那怎么办？也许有的朋友会说，现在有64位的cpu。但是如果我们此刻没有64位的cpu，那该怎么办呢？


总结：

    （1）看似最大公约数、最小公倍数是个小问题，但是要写好不容易，算法、参数判断、逻辑都要注意，

    （2）如果m和n的数据都比较大，有没有可能利用多核降低计算的复杂度，

    （3）如果m和n中有数据大于32位，那该怎么办？

    （4）小问题看似简单，但是在不同的场景下却可以变得非常复杂，作为面试题可以充分考察面试者的沟通能力和应变能力。



分享到：
求两个最大公约数的算法 什么是最大公约数，什么是最小公倍数，有没有算法 使用欧几里得算法，求给定两个整数的最大公约数。 请问gcd算法求最大公约数的时间复杂度是多少 210和330的最小公倍数是最大公约数多少倍 我想知道最大公约数与最小公被数的求法 最大公约数 直角堆垛最小通道宽度算法 递推最小二乘算法 prim算法求最小生成树 最小生成树两种算法有何区别 甲数的12倍和乙数的15倍的最大公约数是1440，甲数和乙数的最大公约数是几？ 甲数的12倍和乙数的15倍的最大公约数是1440，甲数和乙数的最大公约数是几？ 甲乙两数的最小公倍数是最大公约数的20倍，且甲比乙多7，甲乙各是多少？ a 是b的3倍,那么a与b的最大公约数是( ),最小公倍数是( ) 512内存的虚拟1.5倍是什么意思？怎么算法？ 怎样才能把算法写好啊？ 写者问题的算法 有两个自然数,它们的最大公约数是12,最小公倍是360,求这两个数? 算法：大于M能被N整除的最小正整数 递推最小二乘算法的simulink实现 介绍一下greedy+MFset算法构造最小生成树 如何一步一步的提高写公文材料的水平？ 甲,乙两数的最大公约数是75,最小公倍数是450,若它们的差最小,则两个数为?和?