如何用编程来实现求最小公倍数和最大公约数？以下将为大家分享求出这一结果的各种简单方法（流程图+代码详解） |
您所在的位置：网站首页 › 最大公约数公式 › 如何用编程来实现求最小公倍数和最大公约数？以下将为大家分享求出这一结果的各种简单方法（流程图+代码详解） |
如何用编程来实现求最小公倍数和最大公约数？以下将为大家分享求出这一结果的各种简单方法（流程图+代码详解）
|
当我们初学某门编程语言时，如何用编程来求解最小公倍数和最大公约数，总是我们绕不过的一道经典的算法例题，下面我将为大家分享一些对于这两种问题各种简单方法，希望对大家有所帮助 文章目录 前言 一、什么是最小公倍数？ 计算公式：最小公倍数 = 两数乘积 / 两数的最大公因数 二、如何求解最小公倍数 1.方法一：连加整除法 2.方法二：遍历相乘法 方法三：定义法 三、什么是最大公约数&求解方法 方法一：辗转相除法（欧几里德算法） 方法二：穷举法 主函数main（仅供参考，大家也可自行设计） 总结 前言本文将为大家详细讲解求解最小公倍数和最大公约数的方法，并在每种方法下配有相关的测试代码，代码中附带的解释方便大家理解。此外各种方法都是以函数的方式来封装的，方便大家使用的时候进行测试 一、什么是最小公倍数？最小公倍数就是可以整除这两个数的最小的数。 计算公式：最小公倍数 = 两数乘积 / 两数的最大公因数例如：6和9的最小公倍数就是18，3和5的最小公倍数是15.也可以说是两个数相乘除以他们的最大公约数.最大公约数的概念和最小公倍数正好相反,就是两个数都可以整除的最大的数,如3和5的最大公约数就是1,而6和9的最大公约数就是3. 二、如何求解最小公倍数 1.方法一：连加整除法首先选出(x, y)中较大的那个数（max），将它视作最小公倍数，再用它来对两个操作数进行整除操作。若能整除，则输出这个数；若不能整除，则进行++操作 实现函数代码如下： //求解最小公倍数 int lcm(int x, int y) { //使用三元运算符，来进行筛选最大值 int max = x > y ? x : y; //如果x > y条件成立，则选择x，否则选择y while (1) { //判断是否为最小公倍数 if ((max % x == 0) && (max % y == 0)) return max; //满足条件，直接返回值 max++; } } 2.方法二：遍历相乘法首先随机选取(x, y)中任意一个数，再用它来除以另一个数。若能整除，则输出；若不能整除，则将它依次从1开始相乘，步长为1，遍历至刚好可以整除为止，输出结果 即：x(或y) * i % y(或 x)是否等于0，z = x(或y) * i，否：i++，是：输出x(或 y) * i 实现函数代码如下： //求最小公倍数 int lcm(int x, int y) { int i = 1; while (1) { if (x * i % y == 0) //从1开始查找 { return x * i; } i++; } } 方法三：定义法直接根据计算公式：最小公倍数 = 两数乘积 / 两数的最大公因数 首先先求出最大公约数（用到了辗转相除法），在带入计算公式（这一步中的求最大公约数的方法会在下面做详细阐述） 实现代码如下： //求最小公倍数 int lcm(x, y) { int z = x % y; //x需大于y int m = x; int n = y; while (z) //当z = 0时 循环结束；y是最大公约数 { x = y; y = z; z = x % y; } return (m * n / y); } 三、什么是最大公约数&求解方法两个或多个整数共有约数中最大的一个 方法一：辗转相除法（欧几里德算法）首先从(x, y)中任取其中一个数对另一个数进行取模运算，并将余数赋值给变量z 即：z = x % y ， z的取值结果可能有以下两种情况： z != 0：则x = y，y = zz == 0：运算出口，此时y的值就(x, y)两个数的最大公约数
代码如下： //求最大公约数 int gcd(x, y) { int z = x % y; while (1) { if (z != 0) { x = y; y = z; z = x % y; } else break; //如果z == 0 则循环终止 } return y; //返回最大公约数 }特点：方法简单，思路较难理解 如果大家想要进一步了解算法原理及证明过程，可以点击这个链接：(3条消息) 深入浅出理解欧几里得算法的原理_欧几里德算法原理_wl12346的博客-CSDN博客 方法二：穷举法首先选取(x, y)中较小的数，我们知道最大公约数一定是小于(x, y)中的任意一个数，所以最大公约数可以通过遍历较小的那个数，找出同时满足可以整除x和y的数，其中最大的那个就是我们所要求的最大公约数
代码如下： //求最大公约数 int gcd(x, y) { int ans = 1; int z = x >= y ? y : x; //三元运算符，取出(x, y)中最小值 for (int i = 1; i |
【本文地址】
今日新闻 |
推荐新闻 |