Lotplace

用輾轉相除法取兩數之間的最大公因數(GCD)

條件歸納:

gcd(a,b) = 
\begin{cases}
a,\ where\ a\ mod\ b = 0\\
gcd(b,a\ mod\ b),otherwise
\end{cases}

Golang

遞迴版本:

package main

import "fmt"

func swap(a, b int) (int, int) {
    return b, a
}

//遞迴版本GCD(輾轉相除法)
func gcd(a, b int) int {
    fmt.Println(a, b)
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

func main() {
    fmt.Println("input a,b:")
    var a, b int
    fmt.Scanf("%d,%d", &a, &b)
    fmt.Printf("gcd(%d, %d) = %d\n", a, b, gcd(a, b))
}

Kidian Liu

好想ㄘ爆甜點RRR

Filed under: 演算法 - @ 2021 年 7 月 1 日 下午 2:20

標籤: algo, recursive