首页 > 试题广场 >

下列程序执行后，输出的结果为( )

[单选题]
下列程序执行后，输出的结果为( ) 
#include <stdio.h>
int cnt=0;
int fib(int n){
　　cnt++;
　　if(n==0) 
　　　　return 1; 
　　else if(n==1) 
　　　　return 2; 
　　else 
　　　　return fib(n-1)+fib(n-2);
}
void main()
{
　　fib(8);
　　printf("%d",cnt);
}
  • 41
  • 67
  • 109
  • 177
查看正确选项
添加回答
追逐者头像 追逐者
------f(n)-----------cnt的值------
------f(0)-----------1------------------
------f(1)-----------1------------------
------f(2)-----------3------------------1+1+1
------f(3)-----------5------------------1+3+1
------f(4)-----------9------------------ 3+5+1
------f(5)-----------15-----------------5+9+1
*****************************************************
=====>f(6)=9+15+1=25
=====>f(7)=15+25+1=41
=====>f(8)=25+41+1=67

发表于 2016-04-15 16:14:50 回复(2)
peach头像 peach
F(1)的时候为1
F(2)的时候为3
...
规律为
F(n) = F(n - 1) + F(n - 2) + 1
由此可知
F(8) = 41 + 25 + 1
发表于 2016-04-07 14:57:31 回复(2)
zhaoying头像 zhaoying
本题考察Fibonacci sequence，可将fib函数的计算过程构造一棵平衡二叉树（AVL数），F(n) /*AVL数的总结点数*/= F(n - 1)/*左结点个数*/ + F(n - 2) /*右结点个数*/+ 1 /*根结点*/，AVL树的总结点个数就是递归函数的调用次数。
发表于 2016-04-12 11:01:19 回复(0)
神奇航海士头像 神奇航海士

递归通用树形结构，每个节点都执行+1操作，相同数字的节点具有相同的cnt值。
如
节点0,cnt=1
节点1,cnt=1
节点2,cnt=3
节点3,cnt=3+1+1=5
节点4,cnt=5+3+1=9
以此类推
节点8,cnt=41+25+1=67
总之，类似的小题都可以如此，毕竟数不大，图也好画，结果就很清楚了。有图有真相！
发表于 2016-08-01 18:06:51 回复(2)
青豆组合头像 青豆组合
注意审题，输出的不是 fib(8)
发表于 2017-10-26 19:44:48 回复(0)
miaopass头像 miaopass
调用次数g(n) = g(n-1) + g(n-2) + 1,g(0) = g(1) = 1,用这个关系便可递推出来
发表于 2016-04-07 12:40:38 回复(1)
如何打个盹头像 如何打个盹
当n=0和1时，函数执行次数为1
当n=2时，函数执行次数为f(1)执行次数+f(0)执行次数+1，为3
当n=3时，函数执行次数为f(2)执行次数+f(1)执行次数+1，为5
当n=4时，函数执行次数为f(3)执行次数+f(2)执行次数+1，为9
当n=5时，函数执行次数为f(4)执行次数+f(3)执行次数+1，为15
当n=6时，函数执行次数为f(5)执行次数+f(4)执行次数+1，为25
当n=7时，函数执行次数为f(6)执行次数+f(5)执行次数+1，为41
当n=8时，函数执行次数为f(7)执行次数+f(6)执行次数+1，为67
发表于 2018-10-30 23:06:59 回复(0)
Cxx🍉头像 Cxx🍉
F(1)  为什么还等于1啊 不应该等于2么？

发表于 2018-01-31 20:03:07 回复(3)
97城市猎人头像 97城市猎人
0       1     2       3      4      5     6      7    8  
1       1    3        5      9      15    25    41   67
发表于 2016-09-05 00:49:20 回复(0)
乖乖的学插花头像 乖乖的学插花
fib(0)时 cnt=1； fib(1)时 cnt=1; fib(2)时 自己执行一次cnt++；，再调用fib(0),fib(1),所以这时cnt为3 fib(8)可以直接推出来，找规律就再自己找
发表于 2016-04-07 10:52:22 回复(0)
youaregenius头像 youaregenius

需要注意结果并不是求f(8)的值，而是吊用这个函数的次数

发表于 2018-08-22 15:20:05 回复(0)
为你扣下F键头像 为你扣下F键
我一个个数的😂
发表于 2018-07-31 12:51:11 回复(0)
念城、离归头像 念城、离归
没懂，大佬们
发表于 2018-06-08 09:07:56 回复(0)
章鱼🐙头像 章鱼🐙
通用表达式
发表于 2017-12-13 10:44:29 回复(0)
huixieqingchun头像 huixieqingchun
可以用树的方式来表示函数的调用次数。从而数树中的结点来得到相应的函数调用次数。
发表于 2016-05-22 15:26:20 回复(0)
提交观点

问题信息

C语言 递归
来自：京东2016实习生招聘...
难度：
15条回答 8142浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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