数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学使用动态规划返回斐波那契数列中第 n 个数的 Golang 程序
在本文中，我们将编写 Go 语言程序，使用动态规划返回斐波那契数列中的第 n 个数。这是一种通过将复杂问题分解成更小的子问题来解决复杂问题的技术。
记忆化是将函数调用的输出存储在某些数据结构中的过程，这样下次调用时就不需要再次计算输出，它可以使用该值进行计算，从而减少执行时间。
语法
func make ([] type, size, capacity)
Go 语言中的make函数用于创建数组/映射，它接受要创建的变量类型、大小和容量作为参数。
算法
此程序导入 main 和 fmt 包。
创建一个名为 fibo(n int) int 的函数，该函数接受整数 n 作为输入参数并返回所需的斐波那契数。
使用 make 作为内置函数创建一个大小为 n+1 的切片 fib 来存储斐波那契数。
设置第 0 个和第 1 个斐波那契数。
在此步骤中，使用 for 循环从 2 迭代到 n，在每次迭代中计算第 i 个斐波那契数。
循环终止后，返回 fib[n] 作为输出。
创建一个 main 函数，在其中设置要计算其斐波那契值的第 n 个数。
然后，使用 n 作为参数调用 fibo() 函数来计算输出。
使用 fmt 包中的 printf 函数在控制台上打印输出。
示例 1
在此示例中，我们将编写一个 Golang 程序，通过将前两个斐波那契数相加来找到第 n 个斐波那契数以获得当前数，并将其存储在使用 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 程序，通过使用存储使用递归计算的斐波那契数的映射来返回斐波那契数列中的第 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 个数的程序。在第一种方法中，我们使用了动态规划，在第二种方法中，我们使用了带动态规划的记忆化。
更新于: 2023 年 8 月 4 日
1K+ 浏览量
广告