递归法求最大公约数和最小公倍数的实现代码

数学原理：

       设有两个数num1和num2，假设num1比较大。令余数r = num1 % num2。
       当r == 0时，即num1可以被num2整除，显然num2就是这两个数的最大公约数。
       当r != 0时，令num1 = num2（除数变被除数），num2 = r（余数变除数），再做 r = num1 % num2。递归，直到r == 0。
       以上数学原理可以用具体的两个数做一下分析，这样容易理解。

代码实现（求最大公约数）：


代码如下:

#include <iostream>
using namespace std;

int gcd(int a, int b);//声明最大公约数函数

int main()
{
    int num1 = 1;
    int num2 = 1;   
    cin >> num1 >> num2;
    while(num1 == 0 || num2 == 0)//判断是否有0值输入，若有则重新输入
    {
        cout << "input error !" << endl;
        cin >> num1 >> num2;
    }
    cout << "The gcd of " << num1 << " and " << num2 << " is: " << gcd(num1, num2) << endl;//调用最大公约数函数
    return 0;
}

int gcd(int a, int b)//函数定义
{
    int max = a > b ? a : b;
    int min = a < b ? a : b;
    a = max;
    b = min;
    int r = a % b;
    if(0 == r)//若a能被b整除，则b就是最大公约数。
        return b;
    else
        return gcd(b, r);//递归   
}

最小公倍数的求法建立在求最大公约数的方法之上。因为最小公倍数等于两个数的积除以最大公约数。

代码实现（求最小公倍数）：


代码如下:

#include <iostream>
using namespace std;

int gcd(int a, int b);//声明最大公约数函数

int main()
{
    int num1 = 1;
    int num2 = 1;   
    int lcm = 1;
    cin >> num1 >> num2;
    while(num1 == 0 || num2 == 0)//判断是否有0值输入，若有则重新输入
    {
        cout << "input error !" << endl;
        cin >> num1 >> num2;
    }
    lcm = num1 / gcd(num1, num2) * num2;//先除后乘可以在一定程度上防止大数
    cout << "The lcm of " << num1 << " and " << num2 << " is: " << lcm << endl;
    return 0;
}

int gcd(int a, int b)//函数定义
{
    int max = a > b ? a : b;
    int min = a < b ? a : b;
    a = max;
    b = min;
    int r = a % b;
    if(0 == r)//若a能被b整除，则b就是最大公约数。
        return b;
    else
        return gcd(b, r);//递归   
}

以上是仅仅限与求两个书的最大公约数和最小公倍数，当数字有很多时，该法是否依然适用，还有待考证。

赞 (0)

相关推荐

  • C++ 实现求最大公约数和最小公倍数

    C++ 实现求最大公约数和最小公倍数 最大公约数 辗转相除法: int maxDivisor(int a, int b) { int c = b; while (a%b != 0) { c = a%b; a = b; b = c; } return c; } 辗转相减法: int maxDivisor(int a, int b) { while (a != b) { if (a>b) a = a - b; else b = b - a; } return a; } 感谢阅读,希望能帮助到大家,谢

  • Java求两个正整数的最大公约数和最小公倍数

    题目:输入两个正整数m和n,求其最大公约数和最小公倍数. 程序分析:利用辗除法. 最大公约数: public class CommonDivisor{ public static void main(String args[]) { commonDivisor(24,32); } static int commonDivisor(int M, int N) { if(N<0||M<0) { System.out.println("ERROR!"); return -1; }

  • 详解C语言求两个数的最大公约数及最小公倍数的方法

    求两个正整数的最大公约数  思路:这是一个很基本的问题,最常见的就是两种方法,辗转相除法和辗转相减法.通式分别为 f(x, y) = f(y, x%y), f(x, y) = f(y, x - y) (x >=y > 0).根据通式写出算法不难,这里就不给出了.这里给出<编程之美>上的算法,主要是为了减少迭代的次数.      对于x和y,如果y = k * y1, x= k * x1,那么f(x, y) = k * f(x1, y1).另外,如果x = p * x1,假设p为素数

  • C#获取两个数的最大公约数和最小公倍数示例

    最大公约数:指两个或多个整数共有约束中最大的一个. 最小公倍数:如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数,对于两个整数来说,指该两数共有倍数中最小的一个. 复制代码 代码如下: /// <summary>/// 最大公约数/// </summary>/// <param name="a"></param>/// <param name="b"></param>/// &

  • 递归法求最大公约数和最小公倍数的实现代码

    数学原理:        设有两个数num1和num2,假设num1比较大.令余数r = num1 % num2.       当r == 0时,即num1可以被num2整除,显然num2就是这两个数的最大公约数.       当r != 0时,令num1 = num2(除数变被除数),num2 = r(余数变除数),再做 r = num1 % num2.递归,直到r == 0.       以上数学原理可以用具体的两个数做一下分析,这样容易理解.代码实现(求最大公约数): 复制代码 代码如下:

  • python辗转相除法求最大公约数和最小公倍数的实现

    python辗转相除法求最大公约数和最小公倍数的实现

    目录 辗转相除法求最大公约数和最小公倍数 辗转相除法数学原理 python代码实现 用递归的方式实现 Python3 20.辗转相除法 算法分析 源代码 结果截图 辗转相除法求最大公约数和最小公倍数 辗转相除法数学原理 辗转相除法也称欧几里得算法,是用来求两个正整数的最大公约数的算法.接下来我们用实例来解释一下.假如我们需要求12和21的最大公约数,用辗转相除法是这样实现的: 21 / 12 = 1 (余 9) 12 / 9 = 1(余 3) 9 / 3 = 3 (余 0) 至此,得到21与12

  • python求最大公约数和最小公倍数的简单方法

    python怎么求最大公约数和最小公倍数 一.求最大公约数 用辗转相除法求最大公约数的算法如下: 两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数.比如10和25,25除以10商2余5,那么10和25的最大公约数,等同于10和5的最大公约数. 具体代码如下: def gongyue(a, b): """ 欧几里得算法----辗转相除法 :param a: 第一个数 :param b: 第二个数 :return: 最大公约数 "

  • java递归法求字符串逆序

    本文实例讲述了java递归法求字符串逆序的方法.分享给大家供大家参考.具体实现方法如下: public static String reverseString(String x) { if(x==null || x.length()<2) return x; return reverseString(x.substring(1,x.length()))+ x.charAt(0); } 希望本文所述对大家的java程序设计有所帮助.

  • PHP编程求最大公约数与最小公倍数的方法示例

    本文实例讲述了PHP编程求最大公约数与最小公倍数的方法.分享给大家供大家参考,具体如下: //求最大公约数 function max_divisor($a,$b) { $n = min($a, $b); for($i=$n; $i>1; $i--) { if (is_int($a/$i)&&is_int($b/$i)) { return $i; //此处如果用echo $i;则输出结果为432:故应区分echo.return的区别 } } return 1; } //求最小公倍数 f

  • java求最大公约数与最小公倍数的方法示例

    java求最大公约数与最小公倍数的方法示例

    本文实例讲述了java求最大公约数与最小公倍数的方法.分享给大家供大家参考,具体如下: Gongyueshu.java文件: package math; public class Gongyueshu { public static void main(String[] args) { //从控制台输入两个数据 int m = Integer.parseInt(args[0]); int n = Integer.parseInt(args[1]); int y = 1 ; int b = 1;

  • ASP.NET递归法求阶乘解决思路

    前台: 复制代码 代码如下: <asp:TextBox ID="TextBox1" runat="server"></asp:TextBox> !<asp:Button ID="Button1" runat="server" onclick="Button1_Click" Text="=" /> <asp:TextBox ID="Tex

  • JavaScript求一组数的最小公倍数和最大公约数常用算法详解【面向对象，回归迭代和循环】

    本文实例讲述了JavaScript求一组数的最小公倍数和最大公约数常用算法.分享给大家供大家参考,具体如下: 方法来自求多个数最小公倍数的一种变换算法(详见附录说明) 最小公倍数的算法由最大公约数转化而来.最大公约数可通过如下步骤求得: (1) 找到a1,a2,..,an中的最小非零项aj,若有多个最小非零项则任取一个 (2) aj以外的所有其他非0项ak用ak mod aj代替:若没有除aj以外的其他非0项,则转到(4) (3) 转到(1) (4) a1,a2,..,an的最大公约数为aj 写

  • php递归法读取目录及文件的方法

    本文实例讲述了php递归法读取目录及文件的方法.分享给大家供大家参考.具体如下: 这里实例分析php递归法读取目录及文件的方法,代码中包含较为详尽的注释,如下所示: <?php function showdir($path){ $dh = opendir($path);//打开目录 while(($d = readdir($dh)) != false){ //逐个文件读取,添加!=false条件,是为避免有文件或目录的名称为0 if($d=='.' || $d == '..'){//判断是否为.

随机推荐