golang实现Fibonacii的几种算法

前端之家收集整理的这篇文章主要介绍了golang实现Fibonacii的几种算法前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
  1. package fib
  2.  
  3. /**
  4. Fibonacii的几种算法实现
  5. */
  6.  
  7. // 直接循环计算
  8. func Fib(n int) int {
  9. f := [3]int{0,1,1}
  10. if n < 0 {
  11. return -1
  12. }
  13.  
  14. if n < 3 {
  15. return f[n]
  16. }
  17.  
  18. for i := 3; i <= n; i++ {
  19. f[0],f[1] = f[1],f[2]
  20. f[2] = f[0] + f[1]
  21. }
  22.  
  23. return f[2]
  24. }
  25.  
  26. // 略微修改,没有任何数据中间交换哦~~
  27. func Fib2(n int) int {
  28. f := [2]int{0,1}
  29. if n < 0 {
  30. return -1
  31. }
  32.  
  33. if n < 2 {
  34. return f[n]
  35. }
  36.  
  37. for i := 2; i <= n; i++ {
  38. f[i&1] += f[(i+1)&1]
  39. }
  40.  
  41. return f[n&1]
  42. }
  43.  
  44. //递归算法,效率低
  45. func FibRec(n int) int {
  46. if n < 0 {
  47. return -1
  48. }
  49. return fib_recursion(n)
  50. }
  51.  
  52. func fib_recursion(n int) int {
  53. if n < 3 {
  54. return 1
  55. }
  56. return fib_recursion(n-1) + fib_recursion(n-2)
  57. }
  58.  
  59. //尾递归算法
  60. func FibTail(n int) int {
  61. if n < 0 {
  62. return -1
  63. }
  64.  
  65. if n < 3 {
  66. return 1
  67. }
  68.  
  69. return fib_tail_recursion(n,3)
  70. }
  71.  
  72. func fib_tail_recursion(n int,a int,b int,begin int) int {
  73. if n == begin {
  74. return a + b
  75. }
  76. return fib_tail_recursion(n,b,a+b,begin+1)
  77. }
单元测试测试代码
  1. package fib
  2.  
  3. import (
  4. //"fmt"
  5. "testing"
  6. )
  7.  
  8. func TestFib(t *testing.T) {
  9. n := 10
  10. f := Fib(n)
  11. if f != 55 {
  12. t.Error("Fib() Failed. Got",f,"Expected 55 ")
  13. }
  14. }
  15.  
  16. func TestFib2(t *testing.T) {
  17. n := 10
  18. f := Fib2(n)
  19. if f != 55 {
  20. t.Error("Fib2() Failed. Got","Expected 55 ")
  21. }
  22. }
  23.  
  24. func TestFibRec(t *testing.T) {
  25. n := 10
  26. f := FibRec(n)
  27. if f != 55 {
  28. t.Error("FibRec() Failed. Got","Expected 55 ")
  29. }
  30. }
  31.  
  32. func TestFibTail(t *testing.T) {
  33. n := 10
  34. f := FibTail(n)
  35. if f != 55 {
  36. t.Error("FibTail() Failed. Got","Expected 55")
  37. }
  38. }
  39.  
  40. func BenchmarkFib(b *testing.B) {
  41. for i := 0; i < b.N; i++ {
  42. Fib(1000)
  43. }
  44. }
  45.  
  46. func BenchmarkFib2(b *testing.B) {
  47. for i := 0; i < b.N; i++ {
  48. Fib2(1000)
  49. }
  50. }
  51.  
  52. func BenchmarkFibTail(b *testing.B) {
  53. for i := 0; i < b.N; i++ {
  54. FibTail(1000)
  55. }
  56. }

直接递归实在太慢了,无法测试性能

可以明显看出,直接计算,无交换的算法是最快的。

猜你在找的Go相关文章