Golang 使用动态编程返回斐波那契数列中的第n个数字

在本文中，我们将编写Go语言程序，使用动态编程返回斐波那契数列中的第n个数字。这是一种将复杂问题分解为较小子问题来解决的技术。

记忆化 是将函数调用的输出存储在某些数据结构中的过程，下次调用时无需再次计算输出，而是可以使用该值进行计算，从而减少执行时间。

语法

func make ([] type, size, capacity)

make 函数在go语言中用于创建数组/映射，它接受要创建的变量的类型、大小和容量作为参数。

步骤

• 这个程序导入了 main 和 fmt 包。

• 创建一个名为 fibo(n int) int 的函数，它接受一个整数 n 作为输入参数，并返回所需的 Fibonacci 数字。

• 使用 make 内置函数创建一个大小为 n+1 的切片 fib 来存储 Fibonacci 数字。

• 设置第 0 个和第 1 个 Fibonacci 数字。

• 在这个步骤中，使用 for 循环从 2 到 n 做迭代，每次迭代计算第 i 个 Fibonacci。

• 循环终止后，将 fib[n] 作为输出返回。

• 创建一个主函数，在其中设置要计算 Fibonacci 值的第 n 个数字。

• 然后，调用 fibo() 函数，将 n 作为参数来计算输出。

• 使用 fmt 包的 printf 函数，在控制台上打印输出。

示例1

在这个例子中，我们将编写一个 Golang 程序，通过将两个前面的 Fibonacci 数相加来找到第 n 个 Fibonacci 数，并将其存储在使用 make 函数创建的切片中。

package main
import "fmt"

func fibo(n int) int {
    fib := make([]int, n+1)
    fib[0] = 0
    fib[1] = 1

    for i := 2; i <= n; i++ {
        fib[i] = fib[i-1] + fib[i-2]
    }
    return fib[n]
}
func main() {
    n := 6
    output := fibo(n)
    fmt.Printf("The %dth number in this Fibonacci sequence is: %d\n", n, output)
}

输出

The 6th number in this Fibonacci sequence is : 8

示例2

在这个例子中，我们将编写一个Golang程序，通过使用一个使用递归计算得到的Fibonacci数列的Map来返回第n个数字。

package main
import "fmt"
var store map[int]int
func fibo(n int) int {
    if val, ok := store[n]; ok {
        return val
    }
    if n == 0 {
        store[n] = 0
        return 0
    } else if n == 1 {
        store[n] = 1
        return 1
    }
    fib := fibo(n-1) + fibo(n-2)
    store[n] = fib
    return fib
}
func main() {
    n := 8
    store = make(map[int]int)
    output := fibo(n)
    fmt.Printf("The %dth number in the Fibonacci sequence is: %d\n", n, output)
}

输出

The 8th number in the Fibonacci sequence is: 21

结论

我们利用两种方法编写并执行了使用动态规划返回斐波那契数列中第n个数的程序。在第一种方法中，我们使用了动态规划，在第二种方法中，我们利用了备忘录和动态规划。