首页 > 试题广场 >

计算斐波那契数列第n项的函数定义如下： int fib(

[单选题]
计算斐波那契数列第n项的函数定义如下： 
int fib(int n){ 
     if(n==0) 
        return 1; 
     else if(n==1) 
        return 2; 
     else 
        return fib(n-1)+fib(n-2);
}
若执行函数调用表达式fib(9),函数fib被调用的次数是：
  • 107
  • 109
  • 139
  • 177
查看答案及解析
添加回答
chris23521头像 chris23521
对于小数据量的n来说
f(1) 调用1次
f(2) 调用3次
f(3) 调用5次
f(4) 调用9次
发现一个规律：从n=3开开始，调用次数为前两次和加1
即：f(3) =f(2) +f(1) +1=5
      f(4) =f(3) +f(4) +1=9
      f(5) =f(4) +f(3) +1=15
      f(6) =f(5) +f(4) +1=25
      f(7) =f(6) +f(5) +1=41
       f(8) =f(7) +f(6) +1=67
       f(9) =f(8) +f(7) +1=109
发表于 2019-06-27 12:20:54 回复(2)
创始元灵头像 创始元灵
f(9)=f(8)+f(7)+1=109
f(8)=f(7)+f(6)+=67
f(7)=f(6)+f(5)+1=41
f(6)=f(5)+f(4)+1=25
f(5)=f(4)+f(3)+1=15
f(4)=f(3)+f(2)+1=9
f(3)=f(2)+f(1)+1=5
f(2)调用3次
f(1)调用1次


发表于 2019-07-10 11:32:32 回复(0)
李大胆🐈头像 李大胆🐈
对于小数据量的n来说
f(1) 调用1次
f(2) 调用3次
f(3) 调用5次
f(4) 调用9次
发现一个规律：从n=3开开始，调用次数为前两次和加1
即：f(3) =f(2) +f(1) +1=5
f(4) =f(3) +f(4) +1=9
f(5) =f(4) +f(3) +1=15
f(6) =f(5) +f(4) +1=25
f(7) =f(6) +f(5) +1=41
f(8) =f(7) +f(6) +1=67
f(9) =f(8) +f(7) +1=109
编辑于 2019-07-30 08:40:33 回复(0)
冰冰2020头像 冰冰2020
对于小数据量的n来说
f(1) 调用1次
f(2) 调用3次
f(3) 调用5次
f(4) 调用9次
发现一个规律：从n=3开开始，调用次数为前两次和加1
即：f(3) =f(2) +f(1) +1=5
      f(4) =f(3) +f(4) +1=9
      f(5) =f(4) +f(3) +1=15
      f(6) =f(5) +f(4) +1=25
      f(7) =f(6) +f(5) +1=41
       f(8) =f(7) +f(6) +1=67
       f(9) =f(8) +f(7) +1=109
发表于 2019-07-18 13:19:56 回复(0)
提交观点

问题信息

iHandy 算法工程师 2019 大数据开发工程师
上传者：小小
难度：
4条回答 4148浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号