Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3261895
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8557
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: LINUX

2013-11-12 23:20:23

    最近在学习golang这门语言。今天写了fibonacci number的计算:  熟悉一下基本的语法,function的写法。编程语言这种东西需要的是实践,多读多写,才能运用自如,希望自己能掌握这门语言。
    这个是快速的版本:
  1. package main

  2. import "fmt"

  3. func fib(n uint) (ret int64){
  4.     
  5.     var index uint = 0
  6.     
  7.     var i int64 = 1
  8.     var j int64 = 0
  9.     
  10.     for index < n {
  11.         index += 1
  12.         i,j = i+j,i
  13.     }
  14.     
  15.     return j
  16. }

  17. func main(){
  18.     
  19.     fmt.Printf("%d\n",fib(40))
  20. }
    下面这个版本是低效的版本:
  1. package main
  2. import "fmt"

  3. func fib(n uint) uint64{
  4.     
  5.     if n == 0{
  6.         return 0
  7.     }else if n == 1 {
  8.         return 1
  9.     }else {
  10.         return    fib(n-1)+fib(n-2)
  11.     }
  12. }


  13. func main(){
  14.     fmt.Printf("%d\n",fib(40))
  15. }
    低效的版本更好的反映了fibonacci number的特点,但是效率狂低,SICP(计算机程序的构造和解释)完美的解释了效率低的原因。所以建议使用第一个。
    实验证明,当计算fibnacci(60)的时候,fib_slow慢到不能忍受,fib的效率依然是O(n)。
  1. manu@manu-hacks:~/code/go/self$ time ./fib
  2. 102334155

  3. real    0m0.008s
  4. user    0m0.004s
  5. sys    0m0.000s
  6. manu@manu-hacks:~/code/go/self$ time ./fib_slow
  7. 102334155

  8. real    0m2.643s
  9. user    0m2.604s
  10. sys    0m0.004s
  11. manu@manu-hacks:~/code/go/self$

参考文献:
1 An introduction to programming in GO

阅读(3527) | 评论(0) | 转发(2) |
给主人留下些什么吧!~~