欧几里得算法又称为辗转相除法,是计算两个数a,b的最大公约数基本算法,这是我们每一本C语言书上都写得知识点,但是它的原理与推导过程又是怎样来的,很多人都不一定知道,尤其是许多和我一样才接触算法的菜鸟,下面是我对欧几里得算法以及扩展的理解与认识,写出来,分享一下,求交流,求指点!
1.原理
Gcd ( a, b )=Gcd ( b, a%b )
2. 证明
a可以表示为 a=k*b+r 则 r = a%b
假设 d是a , b的最大公约数
则有 a%d==0b%d==0
而 r = a – k*b
因此 d 为b 和r=a%b 的最大公约数
同理依次辗转相除,将a换为b,将b换为a%b
这样a,b必定减小,
当b减小到0时,它的前一步是a%b
所以上一步的a是b的倍数,b是我们所求的最大公约数
也就是这一步的a
代码如下:
3. 扩展
推荐题目:http://acm.nyist.net/JudgeOnline/problem.php?pid=144
(1)原理
对于与不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数那么存在唯一的整数 x,y ,使得 gcd(a,b)=ax+by
(2)证明
为了分析方便,我们设a>b
不难看出:a-b可被表示出来,且它也是gcd的倍数
因此gcd(a,b) = gcd(b,a-b) = gcd(a,a-b)
实际上如果a=n个b+余数,则可以把n个b都减去
再怎么减,都是gcd的倍数
当n足够大时:a-nb=a mod b
因此gcd(a,b)=gcd(b,a mod b)
欧几里德定理证明结束
从上边证明过程可以看出a-b,a-2b,a-3b,…a-nb都可以被表示出来,且x,y都是整数解
当n足够大时:a-nb=a mod b
即 a mod b可被表示出来,且x,y为整数解
gcd(a,b)=gcd(b,a mod b)等价,且x,y都为整数解
相同子问题 最终gcd都可以被表示出来
推荐题目代码:
欢迎交流,欢迎指导!!QQ:719354098
分享到:
相关推荐
欧几里得算法及扩展的欧几里得算法的C++实现。包括.cpp,.exe可执行文件。我的作业。对于密码学和C++初学者有用处,希望对大家有帮助。
扩展欧几里得算法求逆元
当a,b,且a互质时,计算ax+by=1的值, 是计算RSA密钥的基本步骤之一。
此为扩展欧几里得算法求乘法逆元的完整程序,图形界面,使用 vc6.0 完成,完全标准正式的格式,绝对值10积分,有完整的代码,请使用 vc6.0 打开 DSW 工程文件,然后就可完全执行。
欧几里得算法的应用 欧几里得算法的应用 欧几里得算法的应用
java语言实现的欧几里得算法,求最大公约数,以及满足(a,b)=x*a+y*b的x和y
欧几里得是数论中的一个最初步的概念,它用来判断两个数的最大公因子,扩展的欧几里得能够进一步实现在两个数互素情况下的乘法可逆元。求可逆元是一些算法的基础。
包括完整的c语言实现扩展的欧几里得算法代码截图和相关代码说明以及程序截图
信息安全入门基本必备,将基础的欧几里得扩展所得的扩展欧几里得算法。
本算法实现了用扩展欧几里得的方法求最大公因子和模逆元的方法,可以直接运行。
matlab的M函数文件,附带了函数的使用说明了
扩展欧几里得求逆-扩展欧几里得算法求乘法逆元
用扩展欧几里得算法求任意两个数字的最大公因数
菜鸟~~欧几里得算法的简单概述欧几里得算法的简单概述
通过欧几里得算法求到最大公约数,然后得出最小公倍数
35扩展欧几里得算法1
对欧几里得算法的全部思想简要描述,对不同阶段不同人对算法的不同优化,包括knuth大神的亚二次算法
辗转相除法求两个数的最大公约数是最早被数学家研究的算法之一,并且和数论中如连分数,...本文从基本的欧几里得算法谈起,涉及了几个数论问题的解法,并受其思想的启发,研究并解决了了几个看起来与数论不相关的问题。
介绍了扩展欧几里得算法的实现代码,有需要的朋友可以参考一下
MATLAB实现的扩展欧几里得算法