单元测试测试代码:
- package fib
- /**
- Fibonacii的几种算法实现
- */
- // 直接循环计算
- func Fib(n int) int {
- f := [3]int{0,1,1}
- if n < 0 {
- return -1
- }
- if n < 3 {
- return f[n]
- }
- for i := 3; i <= n; i++ {
- f[0],f[1] = f[1],f[2]
- f[2] = f[0] + f[1]
- }
- return f[2]
- }
- // 略微修改,没有任何数据中间交换哦~~
- func Fib2(n int) int {
- f := [2]int{0,1}
- if n < 0 {
- return -1
- }
- if n < 2 {
- return f[n]
- }
- for i := 2; i <= n; i++ {
- f[i&1] += f[(i+1)&1]
- }
- return f[n&1]
- }
- //递归算法,效率低
- func FibRec(n int) int {
- if n < 0 {
- return -1
- }
- return fib_recursion(n)
- }
- func fib_recursion(n int) int {
- if n < 3 {
- return 1
- }
- return fib_recursion(n-1) + fib_recursion(n-2)
- }
- //尾递归算法
- func FibTail(n int) int {
- if n < 0 {
- return -1
- }
- if n < 3 {
- return 1
- }
- return fib_tail_recursion(n,3)
- }
- func fib_tail_recursion(n int,a int,b int,begin int) int {
- if n == begin {
- return a + b
- }
- return fib_tail_recursion(n,b,a+b,begin+1)
- }
- package fib
- import (
- //"fmt"
- "testing"
- )
- func TestFib(t *testing.T) {
- n := 10
- f := Fib(n)
- if f != 55 {
- t.Error("Fib() Failed. Got",f,"Expected 55 ")
- }
- }
- func TestFib2(t *testing.T) {
- n := 10
- f := Fib2(n)
- if f != 55 {
- t.Error("Fib2() Failed. Got","Expected 55 ")
- }
- }
- func TestFibRec(t *testing.T) {
- n := 10
- f := FibRec(n)
- if f != 55 {
- t.Error("FibRec() Failed. Got","Expected 55 ")
- }
- }
- func TestFibTail(t *testing.T) {
- n := 10
- f := FibTail(n)
- if f != 55 {
- t.Error("FibTail() Failed. Got","Expected 55")
- }
- }
- func BenchmarkFib(b *testing.B) {
- for i := 0; i < b.N; i++ {
- Fib(1000)
- }
- }
- func BenchmarkFib2(b *testing.B) {
- for i := 0; i < b.N; i++ {
- Fib2(1000)
- }
- }
- func BenchmarkFibTail(b *testing.B) {
- for i := 0; i < b.N; i++ {
- FibTail(1000)
- }
- }
直接递归实在太慢了,无法测试性能。
可以明显看出,直接计算,无交换的算法是最快的。