透彻理解辗转相除法

妖狐艹你老母 2021-09-21 19:12 501阅读 0赞

> ### 一、理解 ###

今天终于对辗转相除法有了一个透彻的理解！！！

接触过一些算法的应该都知道辗转相除法是求最大公约数的一个方法。

那么为什么这种方法可以求出来呢？

我们先来假设**a,b的最小公约数为g，**那么我们可以这样表示**a=m\*g,b=n\*g;(m,n为整数)（\*）**

**a=b\*k+r;（k,r为整数）（\*\*）**

现在我们用（\*）中的a,b替换（\*\*），得到**m\*g=n\*g\*k+r;**

上述式子变形得到**r=g\*(m-n\*k);**

此时可以看出a,b的最大公约数也是b,r的最大公约数。

然后不断缩小规模，直到其中一个数为0；即r得值为0；（还有一丢丢迷惑中。。。）

> ### 二、应用（最大公约数和最小公倍数） ###

#include<iostream>
    #include<cstdio>
    #include<vector>
    
    using namespace std;
    //辗转相处法 求最大公约数 
    int GCD(int a,int b){
    	if(b == 0){
    		return a;
    	}else{
    		return GCD(b,a%b);
    	}
    }
    int main(){
        int a,b;
    	while(scanf("%d%d",&a,&b)!=EOF) {
    		printf("%d\n",GCD(a,b));
    	}
    	return 0;
    }

#include<iostream>
    #include<cstdio>
    #include<vector>
    
    using namespace std;
    //求最小公倍数 
    int GCD(int a,int b){
    	if(b == 0){
    		return a;
    	}else{
    		return GCD(b,a%b);
    	}
    }
    int main(){
        int a,b;
    	while(scanf("%d%d",&a,&b)!=EOF) {
    		printf("%d\n",a*b/GCD(a,b));
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，501人围观）

还没有评论，来说两句吧...

相关阅读

相关 SYDZ 辗转相除法的原理与实现

辗转相除法又叫欧几里得辗转相除法，最早出现在公元前300年古希腊著名数学家欧几里得的《几何原本》》(第VII卷,命题i和ii)中。而在中国则可以追溯至东汉出现的《九章算术》。而

向右看齐/ 2022年08月21日 02:12/ 0 赞/ 187 阅读

相关欧几里得辗转相除法

欧几里德算法又称辗转相除法，是用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式 gcd (a, b) = gcd (b, a mod b)。(gr

秒速五厘米/ 2022年05月28日 05:07/ 0 赞/ 187 阅读

相关 C语言实现大整数的辗转相除法

辗转相除法，原理，先用小的一个数除大的一个数，得第一个余数；再用第一个余数除小的一个数，得第二个余数；又用第二个余数除第一个余数，得第三个余数；这

冷不防/ 2022年03月31日 14:52/ 0 赞/ 301 阅读

相关辗转相除法（求最大公约数）

主要是依据扩展欧几里德算法中gcd(a,b)=gcd(b,a mod b) 数学证明过程：（参考百科） ![在这里插入图片描述][watermark_type_ZmFu

青旅半醒/ 2022年03月09日 00:05/ 0 赞/ 261 阅读

相关 C实现辗转相除法

目标：求最大公约数方法：利用欧几里得算法（辗转相除法）思路：如果b=0,计算结束，a就是最大公约数否则，计算a除以b的余数，让a=b，而b=余数；回到第一步。

痛定思痛。/ 2022年02月15日 05:43/ 0 赞/ 224 阅读

相关【算法动画图解-5数学】：（1）辗转相除法

看到一个求两个数最大公约数的算法：辗转相除法，觉得很有意思，分享给大家。 1、背景（1）发明人：欧几里得 ![watermark_type_ZmFuZ3poZW5naG

快来打我*/ 2022年02月13日 16:27/ 0 赞/ 436 阅读

相关最小公倍数 //辗转相除法

include<stdio.h> include<string.h> void swap(int &x,int &y) { int

- 日理万妓/ 2021年11月02日 14:40/ 0 赞/ 370 阅读

相关辗转相除法

问题：给出两个数a和b，求出他们的最大公约数(greatest common divisor)。解法一：辗转相除法，又叫欧几里得算法。两个正整数a和b（a>b），他们的最大

不念不忘少年蓝@/ 2021年10月29日 09:50/ 0 赞/ 334 阅读

相关透彻理解辗转相除法

> 一、理解今天终于对辗转相除法有了一个透彻的理解！！！接触过一些算法的应该都知道辗转相除法是求最大公约数的一个方法。那么为什么这种方法可以求出来呢？我们先

妖狐艹你老母/ 2021年09月21日 19:12/ 0 赞/ 502 阅读

相关漫画算法：辗转相除法是什么鬼？

http://blog.jobbole.com/106315/ ![Center][] 小灰的思路十分简单。他使用暴力枚举的方法，试图寻找到一个合适的整数 i，看看这

素颜马尾好姑娘i/ 2021年06月10日 20:42/ 0 赞/ 459 阅读