题目:求两个正整数的最大公约数Greatest Common Divisor (GCD)。如果两个正整数都很大,给定两个数1 100 100 210 001, 120 200 021.
辗转相除
<pre><code>func gcd(a:Int,b:Int)->Int { if b == 0 { return a } else { return gcd(a: b, b: a % b) } }</code></pre>
更相减损
<pre><code>` func gcd1(a:Int,b:Int) -> Int {
if a < b {
return gcd1(a: b, b: a)
}
if b == 0 {
return a
} else {
return gcd1(a: a - b, b: b)
}
}`</code></pre>
两种解法结合
<pre><code>` func gcd2(a:Int,b:Int) -> Int {
if a < b {
return gcd2(a: b, b: a)
}
if b == 0 {
return a
} else {
if isEven(num: a) { // 偶数
if isEven(num: b) {
return gcd2(a: a >> 1, b: b >> 1) << 1
} else {
return gcd2(a: a >> 1, b: b)
}
} else {
if isEven(num: b) {
return gcd2(a: a, b: b >> 1)
} else {
return gcd2(a: b, b: a - b)
}
}
}
}
func isEven(num:Int)->Bool {
return num % 2 == 0 ? true : false
}`</code></pre>
测试代码:
<pre><code>`var commonResult:Int = commonNumber.gcd(a: 720, b: 1248)
var commonResult2:Int = commonNumber.gcd1(a: 720, b: 1248)
var commonResult3:Int = commonNumber.gcd2(a: 720, b: 1248)
print("FlyElephant---最大公约数---(commonResult)----公约数---(commonResult2)--公约数--(commonResult3)")`</code></pre>
