求最大公约数和最小公倍数，辗转相除法，递归

求最大公约数和最小公倍数，辗转相除法，递归 最大公约数：采用，辗转相除法，也为欧几里得算法。 最小公倍数：两数之积 / 最大公约数。

如：求16和24的最大公约数

24 / 16 = 1 ......8

16 / 8 = 2 ...... 0

8  / 0 ,除数为0，结束运算

当能整除时，停止运算，求出最大公约数，就是8

最小公倍数：24 * 16 / 8 = 48 

c++代码：

#include

using namespace std;

//找重复，即子问题
//找变化，变化的量做参数
//找边界

int gcd(int m,int n){   //求最大公约数
    int t;
    while(n!=0){    //除数n不为0，就继续运算
        t=m%n;
        m=n;        //原除数-->被除数
        n=t;        //余数-->除数
}
    return m;
}

int main(){
    int m,n;
    cin>>m>>n;  //输入两个整数，求两数最大公约数
    if(m>=n)    //确保大值在前面
        cout<n的情况了
    cout< 
 
 
 
递归算法：
 
#include

using namespace std;

//找重复，即子问题
//找变化，变化的量做参数
//找边界


int gcd(int m,int n){   //递归求最大公约数
    if(n==0)
        return m;
    return gcd(n,m%n);
}

int main(){
    int m,n;
    cin>>m>>n;  //输入两个整数，求两数最大公约数
    if(m>=n)    //确保大值在前面
        cout<n的情况了
    cout< 
 
 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5703324.html