当前位置：首页 > news >正文

go 中的斐波那契数实现以及效率比较

news 2025/7/28 0:47:40

package mainimport ("fmt""math/big""time"
)// FibonacciRecursive 使用递归方法计算斐波那契数列的第n个数
func FibonacciRecursive(n int) *big.Int {if n <= 1 {return big.NewInt(int64(n))}return new(big.Int).Add(FibonacciRecursive(n-1), FibonacciRecursive(n-2))
}// FibonacciIterative 使用迭代方法计算斐波那契数列的第n个数
func FibonacciIterative(n int) *big.Int {if n <= 1 {return big.NewInt(int64(n))}a := big.NewInt(0)b := big.NewInt(1)for i := 2; i <= n; i++ {a, b = b, new(big.Int).Add(a, b)}return b
}func main() {n := 30 // 计算第100个斐波那契数// 测量递归方法的执行时间startRecursive := time.Now()resultRecursive := FibonacciRecursive(n)durationRecursive := time.Since(startRecursive)// 测量迭代方法的执行时间startIterative := time.Now()resultIterative := FibonacciIterative(n)durationIterative := time.Since(startIterative)// 打印结果和执行时间fmt.Printf("第%d个斐波那契数（递归）: %s\n", n, resultRecursive)fmt.Printf("递归方法执行时间: %v\n", durationRecursive)fmt.Printf("第%d个斐波那契数（迭代）: %s\n", n, resultIterative)fmt.Printf("迭代方法执行时间: %v\n", durationIterative)// 验证两种方法的结果是否相同if resultRecursive.Cmp(resultIterative) == 0 {fmt.Println("两种方法的结果相同")} else {fmt.Println("错误：两种方法的结果不同")}
}