程序設(shè)計(jì)-求最大公因數(shù)
本文使用歐幾里得算法來求最大公因數(shù)。
最大公因數(shù)：能夠同時(shí)整除兩個(gè)整數(shù)的最大整數(shù)。
即饺汹，15和35的最大公因數(shù)為5。因?yàn)?5 = 3 x 5 35 = 7 x 5 = 35 它們能夠同時(shí)被5整除
歐幾里得算法：又稱輾轉(zhuǎn)相除法爆袍，通過對兩數(shù)連續(xù)應(yīng)用帶余除數(shù)首繁，每一步的除數(shù)和被除數(shù)都是上一步的除數(shù)和余數(shù)而來。運(yùn)算知道余數(shù)為0停止陨囊。 最大公因數(shù)為最后一個(gè)非0余數(shù)
例：使用歐幾里得算法求(36, 81)得最大公因數(shù)
81 = 2 * 36 + 9 (9, 36)
36 = 4 * 9 + 0 (0, 9)
此時(shí)余數(shù)為0 除數(shù)為9 則（36弦疮，81）得最大公因數(shù)為9.
程序設(shè)計(jì)
1?? 計(jì)算余數(shù)和除數(shù)
大數(shù)除小數(shù)得余 去放到下一層計(jì)算
if (a > b) {
return gcd(a % b, b);
} else {
return gcd(b % a, a);
}
2?? 確定終止條件
其中一個(gè)為0，則返回另一個(gè) 此數(shù)則為最大公因數(shù)
if (a == 0) return b
if (b == 0) return a
代碼實(shí)現(xiàn)
/**
* @method gcd 求最大公因數(shù)
* @params { number } 整數(shù)a
* @params { number } 整數(shù)b
* @return { number } 最大公因數(shù)
**/
let gcd = (a, b) => {
if (a == 0) return b
if (b == 0) return a
if (a > b) {
return gcd(a % b, b);
} else {
return gcd(b % a, a);
}
}
console.log(gcd(102, 999)) // 3
