歐幾里得演算法
歐幾里得演算法是用來求兩個正整數最大公約數的演算法，
古希臘數學家歐幾里得在其著作中《The Elements》中最早描述了這種演算法，所以叫歐幾里得演算法，
a*x + b*y = gcd(a, b);
存在唯一的x, y使得上面等式成立，
演算法原理
歐幾里得演算法主要就需要一個叫GCD遞回定理的支撐，
gcd(a,b) = gcd(b,a mod b);
gcd在這里指最大公約數，意思就是a與b的最大公約數與b與a mod b的最大公約數相同，
下面我們就來證明一下這個定理：
|在這里的意思是就是整除
歐幾里得演算法的代碼表示
int Gcd(int a, int b)
{
if(b == 0)
return a;
else
return Gcd(b, a % b);
}
用30和21這個例子來證明一下代碼的正確性：
Gcd(30, 21);-->
Gcd(21, 9);-->
Gcd(9, 3);-->
Gcd(3, 0);-->
Gcd = 3;
參考文獻
[1]演算法導論（第三版）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/22143.html
標籤：python