注意事项:
- 百科给出的解释是F(1)=1, F(2)=1,不是F(1)=0, F(2)=1
- 最好定义为int64类型,避免数据过大而异常
- 为了精确显示测试时间,统一用纳秒,转换单位前注意转换为float64类型,否则可能只显示0
- 函数
package main
import (
"fmt"
"time"
)
// 方法一:递归
func Fibonacci1(n int64) int64 {
if n == 0 || n == 1 {
return n
} else if n > 1{
return Fibonacci1(n-2) + Fibonacci1(n-1)
} else {
fmt.Println("输入错误,请重新输入!")
return 0
}
}
// 方法二:利用中间值传递循环,效率更高
func Fibonacci2(n int64) int64 {
if n == 0 || n == 1 {
return n
} else if n > 1 {
var first int64 = 0
var second int64 = 1
var i int64
var sum int64
for i = 1; i <= n-1; i++ {
sum = first + second
first = second
second = sum
}
return second
} else {
fmt.Println("输入错误,请重新输入!")
return 0
}
}
func main() {
var n int64
fmt.Println("请输入序列号n: ")
fmt.Scanln(&n)
//测试时间
beginTime1 := time.Now().UnixNano()
fmt.Println("result1=",Fibonacci1(n))
endTime1 := time.Now().UnixNano()
costTime1 := endTime1 - beginTime1
fmt.Printf("测试函数1花费时间costTime1=%v秒
",float64(costTime1)/1000000000)
beginTime2 := time.Now().UnixNano()
fmt.Println("result2=",Fibonacci2(n))
endTime2 := time.Now().UnixNano()
costTime2 := endTime2 - beginTime2
fmt.Printf("测试函数2花费时间costTime2=%v秒",float64(costTime2)/1000000000)
fmt.Println()
}
- 切片
package main
import (
"fmt"
)
func Fibonacci(n int64) (fibonacci []uint64) {
fibonacci = make([]uint64, n)
// 这里下标减一是因为切片,而不是因为数列第0项,即fibonacci[0]还是f(1)
fibonacci[0] = 1
fibonacci[1] = 1
var i int64
var first uint64 = 1
var second uint64 = 1
for i = 2; i < n; i++ {
fibonacci[i] = first + second
first = second
second = fibonacci[i]
}
return fibonacci
}
func main() {
var n int64
fmt.Println("请输入数列长度:")
fmt.Scanln(&n)
fibonacci := Fibonacci(n)
// 打印切片
fmt.Println("fibonacci=",fibonacci)
fmt.Println()
// 打印数列,访问数组仍要从0开始,输出下标可以加1
for i := 0; i < len(fibonacci); i++ {
fmt.Printf("f(%d)=%v
",i+1,fibonacci[i])
}
}