词条 | 辗转相除 |
释义 | 辗转相除法辗转相除,又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至公元前300年。它首次出现于欧几里德的《几何原本》(第VII卷,命题i和ii)中,而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。 辗转相除法的证明证明: 令c=gcd(a,b),a>=b, 令r=a mod b 设a=kc,b=jc,则k,j互素,否则c不是最大公约数 据上,r=a-mb=kc-mjc=(k-mj)c 可知r也是c的倍数,且k-mj与j互素,否则与前述k,j互素矛盾, 由此可知,b与r的最大公约数也是c,即gcd(a,b)=gcd(b,a mod b),得证。 辗转相除法的算法算法 辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的: 1. 若 r 是 a ÷ b 的余数, 则 gcd(a,b) = gcd(b,r) 2. a 和其倍数之最大公因子为 a。 另一种写法是: 1. a ÷ b,令r为所得余数(0≤r<b) 若 r = 0,算法结束;b 即为答案。 2. 互换:置 a←b,b←r,并返回第一步。 辗转相除法的计算机代码虚拟码 这个算法可以用递归写成如下: function gcd(a, b) { if a mod b<>0 return gcd(b, a mod b); else return b; } 或纯使用循环: function gcd(a, b) { define r as integer; while b ≠ 0 { r := a mod b; a := b; b := r; } return a; } 其中“a mod b”是指取 a ÷ b 的余数。 例如,123456 和 7890 的最大公因子是 6, 这可由下列步骤看出: a b a mod b 123456 7890 5106 7890 5106 2784 5106 2784 2322 2784 2322 462 2322 462 12 462 12 6 12 6 0 只要可计算余数都可用辗转相除法来求最大公因子。这包括多项式、复整数及所有欧几里德定义域(Euclidean domain)。 辗转相除法的运算速度为 O(n2),其中 n 为输入数值的位数。 |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。