算法和程序有什么区别？
算法和程序有什么区别？
08-10-08 &
算法是对特定问题求解步骤的描述，它是指令的有限序列。 简单算法举例 例：求 1*2*3*4*5 步骤 1 ：先求 1*2 ，得到结果 2 。步骤 2 ：将步骤 1 得到的乘积 2 再乘以 3 ，得到结果 6 。步骤 3 ：将步骤 2 得到的乘积 6 再乘以 4 ，得到结果 24 。步骤 4 ：将步骤 3 得到的乘积 24 再乘以 5 ，得到最后结果 120 。 2 、算法与程序的关系 算法和程序都是指令的有限序列 ，但是：程序是算法，而算法不一定是 程序。 算法和程序的区别主要在于：(1) 在语言描述上，程序必须是用规定的程序设计语言来写，而算法很随意；(2) 在执行时间上，算法所描述的步骤一定是有限的，而程序可以无限地执行下去。所以： 程序 = 数据结构 + 算法
请登录后再发表评论!
算法是程序里的重要组成部分，没有算法没有程序的
请登录后再发表评论!
算法可以理解为就是一种函数，是程序的一部分。“算法该改写为程序”这种说法是不恰当的。
请登录后再发表评论!
算法只是一种理论 程序是算法的一种实现 2者是完全不同的概念
有很多的算法无法用程序精确的实现
请登录后再发表评论!
算法和程序的区别主要在于：(1) 在语言描述上，程序必须是用规定的程序设计语言来写，而算法很随意；(2) 在执行时间上，算法所描述的步骤一定是有限的，而程序可以无限地执行下去。所以： 程序 = 数据结构 + 算法简单算法举例 例：求 1*2*3*4*5 步骤 1 ：先求 1*2 ，得到结果 2 。步骤 2 ：将步骤 1 得到的乘积 2 再乘以 3 ，得到结果 6 。步骤 3 ：将步骤 2 得到的乘积 6 再乘以 4 ，得到结果 24 。步骤 4 ：将步骤 3 得到的乘积 24 再乘以 5 ，得到最后结果 120 。 2 、算法与程序的关系 算法和程序都是指令的有限序列 ，但是：程序是算法，而算法不一定是 程序。 算法和程序的区别主要在于：(1) 在语言描述上，程序必须是用规定的程序设计语言来写，而算法很随意；(2) 在执行时间上，算法所描述的步骤一定是有限的，而程序可以无限地执行下去。所以： 程序 = 数据结构 + 算法
请登录后再发表评论!
算法：是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。算法常常含有重复的步骤和一些比较或逻辑判断。
程序：实现预期目的而进行操作的一系列语句和指令。
说通俗一些 就是将，算法是解决一个问题的思路，程序，则是解决这些问题所具体好写的代码。 算法没有语言界限。他只是一个思路。为实现相同的一个算法，用不同语言编写的程序会不一样。 例如冒泡排序，就是一个很经典的循环算法。这个算法用javascript或者用c来实现，代码是不同的。而用这些语言写出来的代码，通过编译后就是程序。 就拿冒泡排序来说。算法是 设一个数组其单元格有N个， 循环执行N次以下操作 {循环执行N次以下操作
比较数组第i和第i+1个单元格的大小，如果前者大于后者则此两个单元格内容互换。i=i+1
} } 一般简单些算法通常用逻辑图来表示。复杂算法可能用某种语言的代码直接写。但不会涉及具体的实现过程。 以上算法用c来实现代码如下：
group int a[]={9,8,7,6,5,4,3,2,1,0}; int n=group. for（int i=0;i&n;i++） {
j=0;j&n;j++}
if(group[j]&group[j+1])
int temp=group[j];
group[j]=group[j+1];
group[j+1]=
用javacript实现的代码：
var int group[]={9,8,7,6,5,4,3,2,1,0}; var n=group. for（var i=0;i&n;i++） {
for{var j=0;j&n;j++}
if(group[j]&group[j+1])
var temp=group[j];
group[j]=group[j+1];
group[j+1]=
请登录后再发表评论!
算法就是解决该问题的思路,可以用自然语言描述,也可以用伪计算机语言描述,目的是分析出解决该问题的方法. 写程序就是根据分析出的算法编写出符合该编程语言语法规范的代码用来编译执行而得到结果.
请登录后再发表评论!
算法是写程序的思想,程序是算法的体现!
请登录后再发表评论!
算法，说白了就是你把你做一件事情的过程表达出来！！！这个过程有很多不同！！！ 而程序就是你用编程语言将其这个过程写出来，让程序按照算法所说的顺序执行！！ 算法可以说是你的思考过程，程序就是将它表达出来！！！
请登录后再发表评论!
算法，说白了就是你把你做一件事情的过程表达出来！！！这个过程有很多不同！！！ 而程序就是你用编程语言将其这个过程写出来，让程序按照算法所说的顺序执行！！ 算法可以说是你的思考过程，程序就是将它表达出来！！！
请登录后再发表评论!
算法，说白了就是你把你做一件事情的过程表达出来！！！这个过程有很多不同！！！ 而程序就是你用编程语言将其这个过程写出来，让程序按照算法所说的顺序执行！！ 算法可以说是你的思考过程，程序就是将它表达出来！！！
请登录后再发表评论!
算法只是一种理论 程序是算法的一种实现 2者是完全不同的概念。
算法等于是一种思维方法。
请登录后再发表评论!
算法简单说是解决一个问题的方法，程序是用程序设计语言，对算法的实现，确保能够按照算法得到预期结果。
请登录后再发表评论!五大常用算法之一：分治算法 - 文章 - 伯乐在线
& 五大常用算法之一：分治算法
一、基本概念
在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。
二、基本思想及策略
分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
如果原问题可分割成k个子问题，1&k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
三、分治法适用的情况
分治法所能解决的问题一般具有以下几个特征：
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；
第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、
第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
四、分治法的基本步骤
分治法在每一层递归上都有三个步骤：
step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
step3 合并：将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下：
Divide-and-Conquer(P)
1. if |P|≤n0
2. then return(ADHOC(P))
3. 将P分解为较小的子问题 P1 ,P2 ,…,Pk
4. for i←1 to k
5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
6. T ← MERGE(y1,y2,…,yk) △ 合并子问题
7. return(T)
其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解。
五、分治法的复杂性分析
一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：
T（n）= k T(n/m)+f(n)
通过迭代法求得方程的解：
递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当mi≤n&mi+1时，T(mi)≤T(n)&T(mi+1)。
六、可使用分治法求解的一些经典问题
（1）二分搜索
（2）大整数乘法
（3）Strassen矩阵乘法
（4）棋盘覆盖
（5）合并排序
（6）快速排序
（7）线性时间选择
（8）最接近点对问题
（9）循环赛日程表
（10）汉诺塔
七、依据分治法设计程序时的思维过程
实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。
1、一定是先找到最小问题规模时的求解方法
2、然后考虑随着问题规模增大时的求解方法
3、找到求解的递归函数式后（各种规模或因子），设计递归程序即可。
可能感兴趣的话题
关于伯乐在线博客
在这个信息爆炸的时代，人们已然被大量、快速并且简短的信息所包围。然而，我们相信：过多“快餐”式的阅读只会令人“虚胖”，缺乏实质的内涵。伯乐在线内容团队正试图以我们微薄的力量，把优秀的原创文章和译文分享给读者，为“快餐”添加一些“营养”元素。
新浪微博：
推荐微信号
（加好友请注明来意）
– 好的话题、有启发的回复、值得信赖的圈子
– 分享和发现有价值的内容与观点
– 为IT单身男女服务的征婚传播平台
– 优秀的工具资源导航
– 翻译传播优秀的外文文章
– 国内外的精选文章
– UI,网页，交互和用户体验
– 专注iOS技术分享
– 专注Android技术分享
– JavaScript, HTML5, CSS
– 专注Java技术分享
– 专注Python技术分享
& 2017 伯乐在线欧几里德算法_百度百科
声明：百科词条人人可编辑，词条创建和修改均免费，绝不存在官方及代理商付费代编，请勿上当受骗。
欧几里德算法
欧几里德算法又称，是指用于计算两个a，b的。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。欧几里德算法和扩展欧几里德算法可使用多种编程语言实现。
欧几里德算法简介
欧几里德算法是用来求两个正整数最大公约数的算法。是由古希腊数学家欧几里德在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里德算法。
扩展欧几里德算法可用于加密等领域。
假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里德算法，是这样进行的：
当被加的数为 0 时，就得出了 1997 和 615 的最大公约数 1。
欧几里德算法证明
其计算原理依赖于下面的定理：
定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。（Greatest Common Divisor）缩写为GCD。
gcd(a,b) = gcd(b,a mod b) (不妨设a&b 且r=a mod b ,r不为0)
欧几里德算法证法一
a可以表示成a = kb + r（a，b，k，r皆为正整数，且r&b），则r = a mod b
假设d是a,b的一个，记作d|a,d|b，即a和b都可以被d整除。
而r = a - kb，两边同时除以d，r/d=a/d-kb/d=m，由等式右边可知m为整数，因此d|r
因此d也是b,a mod b的公约数
假设d是b,a mod b的公约数, 则d|b,d|(a-k*b),k是一个整数。
进而d|a.因此d也是a,b的公约数
因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。
欧几里德算法证法二
第一步：令c=gcd(a,b)，则设a=mc，b=nc
第二步：可知r =a-kb=mc-knc=(m-kn)c
第三步：根据第二步结果可知c也是r的
第四步：可以断定m-kn与n互素【否则，可设m-kn=xd,n=yd,(d&1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数≥cd，而非c，与前面结论矛盾】
从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)，得证
注意:两种方法是有区别的。
欧几里德算法原理
Lemma 1.3.1 若 a,b 且 a = bh + r，其中 h,r，则 gcd(a,b) = gcd(b,r)。[1]
证 明. 假设 d1 = gcd(a,b) 且 d2 = gcd(b,r)， 我们证明 d1| d2 且 d2| d1，因而可利用 Proposition 1.1.3⑵ 以及 d1,d2 皆为得证 d1 = d2。
因 d1| a 且 d1| b 利用 Corollary 1.1.2 我们知 d1| a - bh = r. 因为 d1| b,d1| r 且 d2 = gcd(b,r) 故由 Proposition 1.2.5 知 d1| d2. 另一方面，因为 d2| b 且 d2| r 故 d2| bh + r = a. 因此可得 d2| d1。
Lemma 1.3.1 告诉我们当 a & b & 0 时，要求 a,b 的最大公我们可以先将 a 除以 b 所得余数若为 r，则 a,b 的最大公因数等于 b 和 r 的最大公因数. 因为 r & b & a，所以当然把计算简化了，接着我们就来看看辗转相. 由于 gcd(a,b) = gcd(- a,b) 所以我们只要考虑 a,b 都是正整数的情况。
Theorem 1.3.2 (The Euclidean Algorithm) 假设 a,b 且 a & b. 由除法原理我们知存在 h0,r0 使得
a = bh0 + r0，其中 r0 & b.
欧几里得算法
若 r0 & 0，则存在 h1,r1 使得
b = r0h1 + r1，其中 0r1 & r0.
若 r1 & 0，则存在 h2,r2 使得
r0 = r1h2 + r2，其中 0r2 & r1.
如此继续下去直到 rn = 0 为止，若 n = 0 （即 r0 = 0），则 gcd(a,b) = b. 若 n1，则 gcd(a,b) = rn - 1。
证 明. 首先注意若 r0 0，由于 r0 & r1 & r2 & ... 是严格递减的，因为 r0 和 0 之间最多仅能插入 r0 - 1 个正整数，所以我们知道一定会有 nr0 使得 rn = 0。
若 r0 = 0，即 a = bh0，故知 b 为 a 之因数，得证 b 为 a,b 的最大公因数。若 r0 & 0，则由 Lemma 1.3.1 知
gcd(a,b) = gcd(b,r0) = gcd(r0,r1） = ... = gcd(rn - 1,rn) = gcd(rn - 1,0) = rn - 1。
现在我们来看用辗转相除法求最大公因数的例子
Example 1.3.3 我们求 a = 481 和 b = 221 的最大公因数。首先由除法原理得 481 = 2 . 221 + 39，知 r0 = 39. 因此再考虑 b = 221 除以 r0 = 39 得 221 = 5 . 39 + 26，知 r1 = 26，再以 r0 = 39 除以 r1 = 26 得 39 = 1 . 26 + 13，知 r2 = 13。最后因为 r2 = 13整除r1 = 26 知 r3 = 0，故由 Theorem 1.3.2 知 gcd（481,221） = r2 = 13。
在利用辗转相除法求最大公因数时，大家不必真的求到 rn = 0，例如在上例中可看出 r0 = 39 和 r1 = 26 的最大公因数是 13，利用 Lemma 1.3.1 马上得知 gcd(a,b) = 13。
在上一节 Corollary 1.2.5 告诉我们若 gcd(a,b) = d，则存在 m,n 使得 d = ma + nb。当时我们没有提到如何找到此 m,n， 我们利用辗转相除法来介绍一个找到 m,n 的方法， 我们沿用 Theorem 1.3.2 的符号，看 r0 = 0 的情形，此时 d = gcd(a,b) = b 所以若令 m = 0,n = 1，则我们有 d = b = ma + nb. 当 r0 0 但 r1 = 0 时，我们知 d = gcd(a,b) = r0。 故利用 a = bh0 + r0 知，若令 m = 1,n = - h0，则 d = r0 = ma + nb。同理若 r0 0,r1 0 但 r2 = 0，则知 d = gcd(a,b) = r1。故利用 a = bh0 + r0 以及 b = r0h1 + r1 知
r1 = b - r0h1 = b - (a - bh0)h1 = - h1a + （1 + h0h1）b。
因此若令 m = - h1 且 n = 1 + h0h1，则 d = r1 = ma + nb. 依照此法，当 r0,r1 和 r2 皆不为 0 时，由于 d = gcd(a,b) = rn - 1 故由 rn - 3 = rn - 2hn - 1 + rn - 1 知 d = rn - 3 - hn - 1rn - 2. 利用前面推导方式我们知存在 m1,m2,n1,n2 使得 rn - 3 = m1a + n1b 且 rn - 2 = m2a + n2b 故代入
d = (m1a + n1b) - hn - 1(m2a + n2b) = (m1 - hn - 1m2）a + (n1 - hn - 1n2）b.
因此若令 m = m1 - hn - 1m2 且 n = n1 - hn - 1n2，则 d = ma + nb.
上面的说明看似好像当 r0 0 时对每一个 i {0,1,...,n - 2} 要先将 ri 写成 ri = mia + nib，最后才可将 d = rn - 1 写成 ma + nb 的形式，其实这只是论证时的方便，在实际操作时我们其实是将每个 ri 写成 mi'ri - 2 + ni'ri - 1 的形式慢慢逆推回 d = ma + nb. 请看以下的例子.
Example 1.3.4 我们试着利用 Example 1.3.3 所得结果找到 m,n 使得 13 = gcd（481,221） = 481m + 221n. 首先我们有 13 = r2 = 39 - 26 = r0 - r1. 而 r1 = 221 - 5 . 39 = b - 5r0，故得 13 = r0 - (b - 5r0) = 6r0 - b. 再由 r0 = 481 - 2 . 221 = a - 2b，得知 13 = 6(a - 2b) - b = 6a - 13b. 故得 m = 6 且 n = - 13 会满足 13 = 481m + 221n。
要注意这里找到的 m,n 并不会是唯一满足 d = ma + nb 的一组解，虽然上面的推演过程好像会只有一组解，不过只能说是用上面的方法会得到一组解，并不能担保可找到所有的解，比方说若令 m' = m + b,n' = n - a，则 m'a + n'b = (m + b)a + (n - a)b = ma + nb = d. 所以 m',n' 也会是另一组解，所以以后当要探讨唯一性时，若没有充分的理由千万不能说由前面的推导过程看出是唯一的就断言是唯一，一般的作法是假设你有两组解，再利用这两组解所共同满足的式子找到两者之间的关系. 我们看看以下的作法。
Proposition 1.3.5 假设 a,b 且 d = gcd(a,b)。若 x = m0,y = n0 是 d = ax + by 的一组解，则对任意 t,x = m0 + bt/d,y = n0 - at/d 皆为 d = ax + by 的一组整数解，而且 d = ax + by 的所有整数解必为 x = m0 + bt/d,y = n0 - at/d 其中 t 这样的形式。
证 明. 假设 x = m,y = n 是 d = ax + by 的一组解， 由于已假设 x = m0,y = n0 也是一组解，故得 am + bn = am0 + bn0. 也就是说 a(m - m0) = b(n0 - n). 由于 d = gcd(a,b），我们可以假设 a = a'd,b = b'd 其中 a',b' 且 gcd(a',b') = 1 （参见 Corollary 1.2.3）。因此得 a'(m - m0) = b'(n0 - n)。 利用 b'| a'(m - m0),gcd(a',b') = 1 以及 Proposition 1.2.7⑴ 得 b'| m - m0. 也就是说存在 t 使得 m - m0 = b't. 故知 m = m0 + b't = m0 + bt/d. 将 m = m0 + bt/d 代回 am + bn = am0 + bn0 可得 n = n0 - at/d，因此得证 d = ax + by 的整数解都是 x = m0 + bt/d,y = n0 - at/d 其中 t 这样的形式. 最后我们仅要确认对任意 t,x = m0 + bt/d,y = n0 - at/d 皆为 d = ax + by 的一组整数解， 然而将 x = m0 + bt/d,y = n0 - at/d 代入 ax + by 得 a(m0 + bt/d)+ b(n0 - at/d)= am0 + bn0 = d，故得证本定理。
利用 Proposition 1.3.5 我们就可利用 Example 1.3.4 找到 13 = 481x + 221y 的一组整数解 x = 6,y = - 13 得到 x = 6 + 17t,y = - 13 - 37t 其中 t 是 13 = 481x + 221y 所有的整数解。
欧几里德算法设计
是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
⒈ 若 r 是 a ÷ b 的余数，且r不为0， 则
gcd(a,b) = gcd(b,r)
⒉ a 和其倍数之最大公因子为 a。
另一种写法是：
⒈ 令r为a/b所得余数（0≤r&b）
若 r= 0，算法结束；b 即为答案。
⒉ 互换：置 a←b，b←r，并返回第一步。
欧几里德算法算法版本
Go语言版本
package&main
import&&fmt&
func&main()&{
&&&&var&x,&y&int&=&18,&12&
&&&&result&:=&gcd(x,y)&&
&&&&fmt.Printf(&x,&y&的最大公约数是&:&%d&,result)
func&gcd(x,y&int)&int{
&&&&&for&y&!=&0&&{&&&&&
&&&&&&&&&&&&x,&y&=&y,&x%y&
&&&&return&x
欧几里德算法Pascal语言版
var&&a,b,c:
&&readln(a,b);
&&c:=a&mod&b;
&&while&c&&0&do
&&&&a:=b;b:=c;c:=a&mod&b;
&&write(b);
欧几里德算法C语言版
欧几里德算法：辗转求余
原理：&gcd(a,b)=gcd(b,a&mod&b)
当b为0时，两数的最大公约数即为a
getchar()会接受前一个scanf的回车符
#include&stdio.h&
unsigned&int&Gcd(unsigned&int&M,unsigned&int&N)
&&&&unsigned&int&R
&&&&while(N&&&0)
&&&&&&&&Rem&=&M&%&N;
&&&&&&&&M&=&N;
&&&&&&&&N&=&R
&&&&return&M;
int&main(void)
&&&&int&a,b;
&&&&scanf(&%d&%d&,&a,&b);
&&&&printf(&the&greatest&common&factor&of&%d&and&%d&is&&,a,b);
&&&&printf(&%d\n&,Gcd(a,b));
&&&&return&0;
欧几里德算法Ruby语言版
#用欧几里得算法计算最大公约数(排版略）
def&gcd(x,&y)
return&gcd(y,&x&%&y)
欧几里德算法C++版
#include&&algorithm&&//&std::swap&for&c++&before&c++11
#include&&utility&&//&std::swap&for&c++&since&c++11
int&gcd(int&a，int&b)
&&&&if&(a&&&b)
&&&&&&&&std::swap(a,&b);
&&&&return&b&==&0&?&a&:&gcd(b,&a&%&b);
欧几里德算法Java版
int&divisor(int&m,int&n)
&&&&if&(m&%&n&==&0)&{
&&&&&&&&return&n;
&&&&else&{
&&&&&&&&return&divisor(n,m&%&n);
欧几里德算法JavaScript版
function&gcd(a,b){
&&&&var&t;
&&&&if(a&b)&t=b,b=a,a=t;
&&&&while(b!=0)&t=b,b=a%b,a=t;
&&&&return&a;
欧几里德算法Python版
def&gcd(a,&b):
&&&&while&a&!=&0:
&&&&&&&&a,&b&=&b&%&a,&a
&&&&return&b
对于整数a、p，如果存在整数b，满足ab mod p =1，则说，b是a的模p乘法逆元。
定理：a存在模p的乘法逆元的充要条件是gcd(a，p) = 1
首先证明充分性
如果gcd(a，p) = 1，根据，aφ（p) ≡ 1 mod p，因此
显然aφ（p)-1 mod p是a的模p乘法逆元。
再证明必要性
假设存在a模p的乘法逆元为b
ab ≡ 1 mod p
则ab = kp +1 ，所以1 = ab - kp
因为gcd(a，p) = d
所以d只能为1
欧几里德算法Stein算法
欧几里德算法是计算两个数的传统算法，他无论从理论还是从效率上都是很好的。但是他有一个致命的缺陷，这个缺陷只有在大时才会显现出来。
硬件平台，一般整数最多也就是64位，对于这样的整数，计算两个数之间的模是很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过 64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算 128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。
由J. Stein于1961年提出，这个方法也是计算两个数的最大公约数。和欧几里德算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。
为了说明Stein算法的正确性，首先必须注意到以下结论：
gcd(a,a) = a，也就是一个数和他自身的公约数是其自身
gcd(ka,kb) = k gcd(a,b），也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个的最大公约数必然能被2整除
C++/java 实现
// c++/java stein 算法
int gcd(int a,int b)
{if(a&b) //arrange so that a&b
{int temp =a =b=}
if(0==b) //the base case
if(a%2==0 && b%2 ==0) //a and b are even
return 2*gcd(a/2,b/2）；
if (a%2 == 0) // only a is even
return gcd(a/2,b);
if (b%2==0)// only b is even
return gcd(a,b/2）；
return gcd((a-b)/2,b);// a and b are odd
欧几里德算法算法扩展
不但能计算(a，b）的最大公约数，而且能计算a模b及b模a的乘法逆元，用C语言描述如下：
#include&&stdio.h&
unsigned&int&gcdExtended(&int&a,&&int&b,&&int&*x,&&int&*y);
int&main(void)&{
&&&&int&&a,&b,GCD;
&&&&int&&&x,&y;
&&&&a&=&1232,&b&=&573;
&&&&gcdExtended()时,&x&=&20&and&y&=&–43
&&&&1232x&+&573y&=&1
&&&&或者gcdExtended(&573,1232)&时,x=-43,&y=20
&&&&573x+1232y&=&1
&&&&-43*573+1232*20&=&-&=&1
&&&&gcdExtended()&时
&&&&x=2011,&y=-3180
&&&&GCD&=&&gcdExtended(a,&b,&x,&&y);
&&&&printf(&gcdExtended(%d,&%d)&=&%d,&x=%d,&y=%d\n&,&a,&b,&GCD,x,y);
&&&&return&0;
//&欧几里得扩展算法的C语言实现
//&ax+by=1
unsigned&int&gcdExtended(int&a,&int&b,&int&*x,&int&*y){
&&&&if&(a&==&0){
&&&&&&&&*x&=&0;
&&&&&&&&*y&=&1;
&&&&&&&&return&b;
&&&&int&x1,&y1;
&&&&int&gcd&=&gcdExtended(b%a,&a,&&x1,&&y1);
&&&&*x&=&y1&-&(b/a)&*&x1;
&&&&*y&=&x1;
&&&&return&
扩展欧几里德算法对于最大公约数的计算和普通欧几里德算法是一致的。计算乘法逆元则显得很难明白。我想了半个小时才想出证明他的方法。
首先重复拙作整除中的一个论断：
如果gcd(a，b)=d，则存在m，n，使得d = ma + nb，称呼这种关系为a、b组合整数d，m，n称为组合系数。当d=1时，有 ma + nb = 1 ，此时可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。
为了证明上面的结论，我们把上述计算中xi、yi看成ti的迭代初始值，考察一组数（t1，t2，t3），用归纳法证明：当通过扩展欧几里德算法计算后，每一行都满足a×t1 + b×t2 = t3
第一行：1 × a + 0 × b = a成立
第二行：0 × a + 1 × b = b成立
假设前k行都成立，考察第k+1行
对于k-1行和k行有
t1(k-1） t2(k-1） t3(k-1）
t1(k) t2(k) t3(k)
分别满足：
t1(k-1） × a + t2(k-1） × b = t3(k-1）
t1(k) × a + t2(k) × b = t3(k)
根据扩展欧几里德算法，假设t3(k-1） = j t3(k) + r
t3(k+1） = r
t2(k+1） = t2(k-1） - j × t2(k)
t1(k+1） = t1(k-1） - j × t1(k)
t1(k+1） × a + t2(k+1） × b
=t1(k-1） × a - j × t1(k) × a +
t2(k-1） × b - j × t2(k) × b
= t3(k-1） - j t3(k) = r
= t3(k+1）
因此，当最终t3迭代计算到1时，有t1× a + t2 × b = 1，显然，t1是a模b的乘法逆元，t2是b模a的乘法逆元。
Grossman JW. Discrete Mathematics. New York: Macmillan. . ISBN 0-02-.
本词条内容贡献者为
副教授审核
同济大学数学科学学院}