/**
* 本程序用于求解兩個正整數的最大公約數
* 求解最大公約數往往可以用的有三種方法:
* eg: 求正整數x和y的公約數
* 1. 遍歷, 從1遍歷到min(x, y)為止, 找到能夠同時被兩數整除的最大整數
* 2. 輾轉相除法, 取k = x/y, b = x % y, 則 x = k * y + b; 如果一個數能同時整除x和y, 則其一定能同時整除b和y, 即x和y的公約數與b和y的公約數是相同的, 其最大公約數也相同. 所以f(x, y) = f(y, x % y) (x >= y > 0)
* 輾轉相除法證明:
* If x和y, 其最大公約數為d, 則 x = k1 * d, y = k2 * d; 令k = x / y, b = x % y, 則x = k * y + b. 代入, 則k1 * d = k * k2 * d + b, 等號左右相等, 且等式中所有的字符均代表一個整數, 因此等式左右兩側均能被d整除.
* 等號右側中, k * k2 * d本身可以被d整除, 因此b也一定能被d整除, 因此d也一定是b和y的公因數.
* 現在證明d是b和y的最大公因數.
* 假設b和y存在更大的公因數D > d,
* 則在等式x = k * y + b中, b / D和k * y / D的結果均為整數, 因此x / D也為整數, 即x / D = k * y / D + b / D. 則此時x和y均能被D整除, 因此D為x和y的公因數, 又因d為x和y的最大公因數, 而假設D > d, 互相矛盾了, 所以假設不成立
* 即, b和y不存在更大的公因數, 即b和y的最大公因數也是d.
*/
#include<stdio.h>

int Division(int x, int y) {
if (!y)
return x;
else
return Division(y, x % y);
}

/**
* 3. 相減法. 如果一個數能同時整除x和y, 則其一定能同時整除x - y和y(x > y), 即f(x, y) = f(x - y, y).
* 與輾轉相除法相比, 相減法可以用減法運算代替求模運算, 相對開銷要小一些, 但是程序迭代的次數卻多了很多, 尤其是在f(10000, 1)這種類型的運算時.
* 相減法證明:
* 與輾轉相除法相同, f(x, y) = d, x = k1 * d, y = k2 * d, x = k * y + b.
* 則: x - y = k * y - y + b, 兩邊同時除以d, 得到, k1 - k2 = (k - 1) * k2 + b / d, 上文中已經證明b可以被d整除因此等式成立, 且左右均為整數, 因此x - y可以被d整除.
* 與上文同樣方法可以證明d為x - y和y的最大公約數.
*/
int Minus(int x, int y) {
if (x < y) {
x = x ^ y;
y = x ^ y;
x = x ^ y;
}
if (y == 0)
return x;
return Minus(x - y, y);
}

/**
* 4. 改進算法, 結合輾轉相除法和相減法
* 此算法的主要依據為兩個公式:f(x, y) = f(k * x1, k * y1) = k * f(x1, y1), f(x, y) = f(p * x1, y) = f(x1, y)(p是素數且y不能被p整除)
* 對于x和y, 如果x = k * x1, y = k * y1, 則f(x, y) = f(k * x1, k * y1) = k * f(x1, y1).
* 證明:
* 假設d = f(x, y), 即d為x和y的最大公約數. 因此x = d * x2, y = d * y2.
* 假設k不能整除d, 則如下所示:
* d * x2 = k * x1, d * y2 = k * y1. 等號兩邊同時除以k, 由于d不能被k整除, 則x2和y2必然能被k整除, 因此x2和y2必然存在公因子k, 因此d不為x和y的最大公因數, 與假設不相符所以k能整除d.
* 等式兩邊同時提取k, 得到d1 * x2 = x1, d1 * y2 = y1, d1 = f(x1, y1), 且d = d1 * k. 等式成立.
* 對于第二個公式f(x, y) = f(p * x1, y) = f(x1, y)(p是素數且y不能被p整除)
* 證明:
* 令 x = p * x1(p是素數且y不能被p整除), d = f(x, y)
* 因為y不能被p整除, 所以p不能整除d(如果p能整除d, 則y必然能整除p), 又p為素數, 則d不能整除p, 因此d和p是x的兩個獨立的因數, 即p和d的最大公因數為1,
* 所以x = p * x1 = p * d * x2, 即x1能被d整除.
* x1 < x且為x的因子, 所以d同時為x1和y的公因子(同樣可用反證法來證明一下)
*/
/**
* 將改進算法用于求解最大公因子, 由于需要做除法運算, 而在計算機的表達中, 對2做除法運算可通過右移一位來輕松實現, 因此p可以取2.
* 因此對于x和y, 求最大公約數f(x, y), 便可優化為:
* x, y均為偶數, return 2 * f(x >> 1, y >> 1)
* x, y均為奇數, f(y, x - y)
* x為奇數, y為偶數, f(x, y >> 1)
* x為偶數, y為奇數, f(x >> 1, y)
*/
/**
* 此外對于判斷x和y是否為偶數的方法, 如果除法運算的話, 改進就沒有意義了, 因此可以通過與運算來實現
* 對于二進制表示中,偶數的最低位為0, 奇數為1, 可通過這一特性來判斷是否為偶數, 一個&運算即可.
*/

// 判斷x是否為偶數. 偶數返回1, 奇數返回0
int IsEven(int x) {
return (x & 1) ? 0 : 1;
}

int Improve(int x, int y) {
if (x < y)
return Improve(y, x);
if (y == 0)
return x;
if (IsEven(x)) {
if (IsEven(y))
return 2 * Improve(x >> 1, y >> 1);
else
return Improve(x >> 1, y);
} else {
if (IsEven(y))
return Improve(x, y >> 1);
else
return Improve(x - y, y);
}
}
int main() {
int x, y;
scanf("%d%d", &x, &y);
printf("%d和%d的最大公因數為%d\n", x, y, Division(x, y));
printf("%d和%d的最大公因數為%d\n", x, y, Minus(x, y));
printf("%d和%d的最大公因數為%d\n", x, y, Improve(x, y));
return 0;
}

轉載于:https://www.cnblogs.com/KingOfAlex/p/9144450.html

總結

以上是生活随笔為你收集整理的编程之美——2.7 求最大公约数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。