有多少额外的函数调用确实FIB(n)的要求,如果" LINE 3英寸被删除? [英] How many additional function calls does fib(n) require if "LINE 3" is removed?

查看:139
本文介绍了有多少额外的函数调用确实FIB(n)的要求,如果" LINE 3英寸被删除?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我刚在接受记者采访时这个问题,不知道怎么算出答案。
有多少额外的函数调用并FIB(n)的要求,如果LINE 3被删除?答案应该是无论在n个。

  INT FIB(INT N){
  如果(N == 0)返回0;
  如果(N == 1)返回1;
  如果(N == 2)返回1; //行3此处< ---

  返回FIB(N  -  1)+ FIB(N  -  2);
}
 

解决方案

它可以很容易地计算出来。旧的code:

 来(0)=(1)=(2)= 1
到(n)=到(n-1)+到(n + 2)+1
 

新的code:

  TN(0)= TN(1)= 1
TN(n)的TN =(N-1)+ TN(N-2)1
 

的差值中减去这两个简单地计算:

  D(0)= D(1)= 0
D(2)= 3-1 = 2
D(N)= TN(n)的-TO(n)的TN =(N-1)+ TN(N-2)+ 1-(到(N-1)+到(n + 2)1)
    =(TN(N-1)-TO(N-1))+(TN(N-2)-TN(N-2))+(1-1)
    = D(N-1)+ D(n-2个)
 

这意味着差为Fibonacci序列与0,0,2开始。另外,也可以计算出一个封闭的形式的前pression它

I just got this question on an interview and had no idea how to calculate the answer.
How many additional function calls does fib(n) require if "LINE 3" is removed? The answer should be in terms on n.

int fib(int n) {
  if(n == 0) return 0;
  if(n == 1) return 1;
  if(n == 2) return 1; //LINE 3 HERE <---

  return fib(n - 1) + fib(n - 2);
}

解决方案

It can be easily calculated. The old code:

TO(0)=TO(1)=TO(2)=1
TO(n)=TO(n-1)+TO(n+2)+1

The new code:

TN(0)=TN(1)=1
TN(n)=TN(n-1)+TN(n-2)+1

The difference is computed simply by subtracting those two:

D(0)=D(1)=0
D(2)=3-1=2
D(n)=TN(n)-TO(n)=TN(n-1)+TN(n-2)+1-(TO(n-1)+TO(n+2)+1)
    =(TN(n-1)-TO(n-1))+(TN(n-2)-TN(n-2))+(1-1)
    =D(n-1)+D(n-2)

Which means the difference is a Fibonacci sequence beginning with 0,0,2. It is also possible to calculate a closed form expression for it.

这篇关于有多少额外的函数调用确实FIB(n)的要求,如果&QUOT; LINE 3英寸被删除?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
相关文章
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆