首页 > 试题广场 >

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

[单选题] 
#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
添加回答
推荐
lonelylsy头像 lonelylsy
n=0和n=1时均计算一次，即cnt都会+1
令f(0)=1，f(1)=1
n f(n) 计算次数
2 f(1)+f(0)+1 3
3 f(2)+f(1)+1 5
4 f(3)+f(2)+1 9
5 f(4)+f(3)+1 15
6 f(5)+f(4)+1 25
7 f(6)+f(5)+1 41
8 f(7)+f(6)+1 67
编辑于 2016-10-09 11:00:37 回复(8)
蓝夕头像 蓝夕
这其实可以看做斐波那契数列的变形，相当于从第3个数开始，这个数等于前面两个之和加1.由于是从0开始，所以要数9个数：1，1，3，5，9，15，25，41，67
发表于 2016-04-28 22:51:46 回复(5)
YaoC头像 YaoC

本题递推很容易求出答案，这里再提供一种通过求解析解得到答案的方法 图片说明

发表于 2017-03-13 22:17:23 回复(12)
huixieqingchun头像 huixieqingchun
做这种题目最好的方式是写成树的形式，从而数树中的结点个数，即可得到相应的次数。
发表于 2016-05-20 14:40:38 回复(3)
牛客327918号头像 牛客327918号
f(8)------------- 1
f(7)-------------1
f(6)-------1+1=2
f(5)------2+1 = 3
f(4)-------------5
f(3)-------------8
f(2)-------------13
f(1)-------------21
f(0)-------------13
1+1+2+3+5+8+13+21+13=67
发表于 2016-04-15 20:15:37 回复(1)
一个达布刘头像 一个达布刘
cnt实际在统计斐波那契数列递归的次数
F0：1次 
F1：1次
F2：F0+F1=3次
F3：F2+F1=1+1+3=5次
F4：F3+F2=1+5+3=9次
F5：F4+F3=1+9+5=15次
F6：F5+F4=1+15+9=25次
F7：F6+F5=1+25+15=41次
F8：F7+F6=1+41+25=67次
发表于 2022-09-10 20:39:49 回复(0)
天佑lyp头像 天佑lyp
我觉得 这道题可以抽象成一个二叉树的节点的个数，看似有点多，但有规律
自底向上算：
0 --> 1个
1 --> 1个
2 --> 0和1 再加上本身 ---->3个
3 --> 1和2 再加上本身 ---->5个
4 --> 2和3 再加上本身 ---->9个
由此类推...
8 --> 7和6 再加上本身 ---->67个
发表于 2017-07-28 17:28:47 回复(0)
ﺭ并偷偷用脚摸了摸你的小脸ﺭ朱头像 ﺭ并偷偷用脚摸了摸你的小脸ﺭ朱
只需一秒，离8*8最近的那个数
发表于 2017-04-02 08:58:28 回复(3)
科笨头像 科笨
输出的是cnt, 和函数的返回值无关。
每调用一次函数cnt+1， 所以cnt的值就是函数一共调用的值。
可以设表达式   f（n）=f（n-1)+f(n-2)+1    //这里+1表示它自身调用一次
f（1）=1，f（0）=1   //表示之后它们无需再调用
发表于 2022-03-01 09:44:02 回复(0)
牛客845655896号头像 牛客845655896号

n＝8

cnt＝1

返回f（7）+f（6）

f(7)

cnt＝2

2F(6)＋f(5)

F(6)

Cnt＝4

3f(5)＋2f(4)

F(5)

Cnt＝7

5f(4)＋3f(3)

F(4)

Cnt ＝12

8f(3)＋5f(2)

F(3)

Cnt＝20

13f(2)＋8f(1)

F(2)

Cnt＝33

21f(1)＋13f(0)

Cnt ＝67

发表于 2020-02-24 22:13:47 回复(0)
怕喵吃的鱼头像 怕喵吃的鱼
n=0 执行一次 n=1 执行一次 n=2 fib(1)+fib(2)+1=3 执行三次 n=3 fib(2)+fib(1)+1=3+1+1=5 执行5次 n=4 fib(3)+fib(2)+1=5+3+1=9 执行9次 n=5 fib(4)+fib(3)+1=9+5+1=15 执行15次 n=6 fib(5)+fib(4)+1=25 执行25次 n=7 fib(6)+fib(5)+1=41 执行41次 n=8 fib(7)+fib(6)+1=67 执行67次
发表于 2017-03-09 08:48:48 回复(0)
jxc666头像 jxc666
从小到大走，这样只用算一遍，可以复用之前的值，甚至可以滚动数组
发表于 2016-11-15 18:06:06 回复(0)
大橘_已定头像 大橘_已定
注意看题问的是cnt值
发表于 2023-09-10 23:45:19 回复(0)
屏南吴彦祖头像 屏南吴彦祖
希望大家以后做递归函数的时候，能够从底层开始算，也就是知道结束条件，函数名(0)的值或函数名(1)的值这样往上累加
发表于 2022-03-26 10:36:23 回复(1)
星野老贼头像 星野老贼
这算法题，我等笨人只能一个一个算，
发表于 2021-07-18 18:03:33 回复(0)
麋鹿在迷雾里迷路头像 麋鹿在迷雾里迷路
<p>这道题目的最直接的意思就是让你求当他等于八时他要进行多少次自增 不妨画一个树状图来理解..虽然慢是真的 但起码自己看得懂</p><p><br></p>
发表于 2020-11-19 19:08:01 回复(0)
牛客143068号头像 牛客143068号
cnt变量是统计计算次数，规律是：1，1，3，5，9，15，25，41，67
发表于 2020-07-16 10:59:37 回复(0)
是清欢吖头像 是清欢吖
看清题目，是输出cnt的值… cnt的值—f（n）= f（n-1）+f（n-2）+1
发表于 2020-05-31 12:47:02 回复(0)
在北极开出租头像 在北极开出租
升级版斐波那契数列
发表于 2020-05-19 23:27:52 回复(0)
美团内推（专业正版）头像 美团内推（专业正版）
------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

发表于 2020-02-26 17:00:11 回复(0)
yangyugu头像 yangyugu
先算最小的，在递推
发表于 2019-03-10 21:14:18 回复(0)
提交观点

问题信息

C语言 算法工程师 京东 2016 运营
来自：京东2016算法工程师笔试题
难度：
29条回答 9628浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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