Lotplace

歸納:

fib(n)=
\begin{cases}
0,\ where\ n = 0\\
1,\ where\ n = 1\\
fib(n - 2) + fib(n - 1),\ where\ n > 1
\end{cases}

Golang

遞迴版本:

package main

import "fmt"

//遞迴版本fib(n)
func fib(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    return fib(n-1) + fib(n-2)
}

func main() {
    fmt.Println("input n:")
    var n int
    fmt.Scanln(&n)
    fmt.Printf("fib(%d) = %d\n", n, fib(n))
}

改寫成迭代版本:

//迭代版本fib(n)
func fib(n int) int {
    if n == 1 {
        return 1
    }
    prev2 := 0
    prev1 := 1
    result := 0
    for i := 2; i <= n; i++ {
        result = prev2 + prev1
        prev2 = prev1
        prev1 = result
    }
    return result
}

Kidian Liu

好想ㄘ爆甜點RRR

Filed under: 演算法 - @ 2021 年 6 月 25 日 下午 1:51

標籤: algo, recursive