首页 > 试题广场 >

函数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(10),函数fib被调用的次数是：

```
117
```
```
137
```
```
157
```
```
177
```

推荐

yayamma

若C(n) 表示计算次数，则
C(0) = 1;
C(1) = 1;
C(n) = C(n-1) + C(n-2) + 1; n>=2;

故：
C(0) = 1;
C(1) = 1;
C(2) = 1 + 1 + 1 = 3;
C(3) = 3 + 1 + 1 = 5;
C(4) = 5 + 3 + 1 = 9;
C(5) = 9 + 5 + 1 = 15;
……

编辑于 2016-02-26 15:06:27 回复(2)

Icebins

这题相当于再求一次费波那奇数列。定义g(n)函数表示计算fib(n)而调用的fib函数的次数

则

g(10) = g(9) + g(8) + 1(1是调用fib(10)需要执行一次fib函数)

。。。。

g(2) = g(1) + g(0) + 1

g(1) = 1

g(0) = 1

可以求得g(10) = 177

发表于 2015-08-13 14:30:52 回复(3)

SKT.RUO

f[MAX]={1,1};

f(n) = f(n-1) + f(n-2) + 1;

推出f(10)=177

发表于 2017-08-20 23:58:32 回复(0)

牛客224540号

这道题可以这样来分析：

设f(n) 表示执行fib(n)函数的次数，那么显然地推公式： f(n) = f(n-1) + f(n-2) + 1 （1表示执行到了fib（n）的时候执行了一次fib函数）

f(10) = f(9) + f(8) + 1

。。。

f(0) = 1

f(1) = 1

f(2) = 3

f(3) = 5
f(4) = 9

f(5) = 15

f(6) = 25

f(7) = 41

f(8) = 67

f(9) = 109

f(10) = 177

问题就转化成求类斐波那契额数列的n项，直接手写都可以写的出来，没多少

发表于 2015-08-22 16:09:45 回复(1)

烟灰缸

根据数据结构里的观点，其实所有递归函数都可以用二叉树表示，只不过有的是只有一个节点，有的有两个节点。斐波那契数列是两个节点，用数据结构可以很好地表示。

发表于 2015-09-02 11:19:55 回复(1)

浅唱__梦

发表于 2016-03-03 16:33:21 回复(0)

剑刃风暴

f(10)=f(9)+f(8)+1

= 2f(8)+f(7)+2

=3f(7)+2f(6)+4

=5f(6)+3f(5)+7

...

=55f(1)+34f(0)+88

55+34+88=177

发表于 2015-08-19 14:53:13 回复(0)

Encore去了又丢

数学归纳法

n=0或1时， g(n) = 1

n>=2时， g(n) = g(n-1) + g(n-2) + 1，结果如下

0 1

1 1

2 3

3 5

4 9

5 15

6 25

7 41

8 67

9 109

10 177

发表于 2015-08-24 16:24:59 回复(0)

牛客228506号

写个main函数，用代码跑出来的。。。。。。。

发表于 2016-06-14 16:39:38 回复(0)

菩提旭光

执行了几次相当于又一次的斐波那契数列：
10->9+8+1
...
3->2+1+1 4
2->1+0+1 2
那么有：2 4 7 12 20 33 54 88 143

发表于 2015-08-21 11:13:22 回复(0)

薯条和番茄

fib(1)=1;

fib(2)=3;

fib(3)=5;

fib(4)=9;

fib(5)=15;

...........

由数学归纳法，不难看出从n=3开始往后每次调用都等于前两次调用次数加1。所以fib(10)为177

发表于 2021-07-09 19:54:38 回复(0)

千山鸟飞崛

为什么都要加1啊？这里没看懂

发表于 2015-10-16 15:25:05 回复(0)

牛客130365080号

gpt:

在斐波那契数列的递归实现中，每次调用fib(n)会导致两个递归调用：fib(n - 1)和fib(n - 2)，这两个调用分别对应着斐波那契数列中的前两个数。

当计算C(2)时，我们考虑了两个递归调用，即C(1)和C(0)，同时还要考虑当前函数fib(2)的一次调用。这一次的 "+1" 表示当前函数的调用。

所以，C(2) = C(1) + C(0) + 1表示：

C(1)表示计算fib(1)时的递归调用次数。
C(0)表示计算fib(0)时的递归调用次数。
"+1" 表示当前函数fib(2)的一次调用。

发表于 2023-09-25 14:37:54 回复(0)

miss_荼靡

若C(n) 表示计算次数，则
C(0) = 1;
C(1) = 1;
C(n) = C(n-1) + C(n-2) + 1; n>=2;

故：
C(0) = 1;
C(1) = 1;
C(2) = 1 + 1 + 1 = 3;
C(3) = 3 + 1 + 1 = 5;
C(4) = 5 + 3 + 1 = 9;
C(5) = 9 + 5 + 1 = 15;

发表于 2016-09-02 22:54:54 回复(0)

BrainerGao

函数被调用的次数相当于一波斐波那契数列，满足表达式：

num(0)=1，num(1)=1

num(n)=num(n-1)+num(n-2)+1，n>=2

发表于 2015-11-08 14:15:23 回复(0)

雄

这题有个小陷阱：它的第一个元素是f(0) 不是f(1)！！！

发表于 2015-09-02 12:28:49 回复(0)

那一抹代码

忘记算自身的调用了。

发表于 2015-08-28 06:04:15 回复(0)

Marico

还是得一个一个算..

发表于 2015-08-25 15:01:56 回复(0)

littlefuture

有谁知道调用了多少次F(0)多少次F(1)嘛？是不是分别为122次和55次？

发表于 2015-08-24 22:39:43 回复(0)

Mr.Yuan

首先题目让求的是fib函数调用的次数
fib（0）调用fib函数的次数为1
fib（1）调用fib函数的次数为1
fib（2）调用fib函数的次数为1 + fib（0）+ fib（1）=3
fib（3）调用fib函数的次数为1 + fib（1）+ fib（2）=5
fib（4）调用fib函数的次数为1 + fib（2）+ fib（3）=9
fib（5）调用fib函数的次数为1 + fib（3）+ fib（4）=15
fib（6）调用fib函数的次数为1 + fib（4）+ fib（5）=25
fib（7）调用fib函数的次数为1 + fib（5）+ fib（6）=41
fib（8）调用fib函数的次数为1 + fib（6）+ fib（7）=67
fib（9）调用fib函数的次数为1 + fib（7）+ fib（8）=109
fib（10）调用fib函数的次数为1 + fib（8）+ fib（9）=177
最后，谢谢Lakers32同学的指正。

编辑于 2015-08-19 16:40:01 回复(2)

提交观点

问题信息

复杂度

来自：360公司2016JA...

难度：

20条回答 958收藏 15777浏览

函数fib被调用的次数是

问题信息

热门推荐

相关试题