第n个Fibonacci数的调用数

让 f(n) fib(n) .

• 如果 然后 .
• 否则, .

f 至少是 . 事实上, f(n) 是 2*fib(n)-1 . 我们通过归纳法证明:

• 基本情况( n<2 n=0 n=1 ):
  • .
• 诱导步骤( ):
  • f(n+1)=f(n)+f(n-1)+1
  • f(n+1)=2*fib(n)-1+2*fib(n-1)-1+1
  • f(n+1)=2*fib(n+1)-1

efficient ways 计算任何斐波那契项。因此同样适用于 f(n)

这个问题有什么关系吗 ?

第n个fibonacci数有一个封闭式方程: http://en.wikipedia.org/wiki/Fibonacci_number#Closed_form_expression

x(n) = x(n-1) + x(n-2) +1   # for n>=2
x(1) = 1
x(0) = 1

这与Fibonacci递归关系几乎相同。归纳证明表明,当n>=0时,fib(n)调用fib的次数等于2*fib(n)-1。

当然,通过使用闭式表达式,或者通过添加代码来存储先前计算的值,可以加快计算速度。

如上所述,您需要求解以下循环方程: K(n)=K(n-1)+K(n-2)+1

我们把它写成n-1:K(n-1)=K(n-2)+K(n-3)+1

现在,从第一个中减去第二个:

或

K(n)-2*K(n-1)+K(n-3)=0。

各自的特征方程为: x^3-2*x ^2+1=0。

因此,对于任何实数A,B,C,下面的函数 (^n*1+5)(平方英寸/平方英寸)

将是你方程的解。

要找到A,B,C,你需要定义几个初始值K(0),K(1),K(2)并求解方程组。

φ是一个常数

position = ceil(log((n - 0.5)*sqrt(5))/log(phi));

位置会给出哪个fibonacci数是n

例如给定13,位置将是7-0 1 1 2 3 5 8 13

使用这个位置,只需计算位置-1处的fibonacci数,或者任何你想要相对于给定fibonacci数的位置。

Previous Fibo Num = floor((pow(phi,position-1)/sqrt(5))+0.5);

floor((pow(phi, position)/sqrt(5))+0.5)

我把这个公式反过来计算位置,用位置-1来计算前面的斐波纳契数。

http://itpian.com/Coding/20951-Given-the-Nth-fib-no-and-find-the--N-1-th-fib-number-without-calculating-from-the-beginning---------.aspx

Recurrence Relations

具体来说,fibonacci问题有以下参数:

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

一旦你掌握了解决反复发生的问题,你就不会有任何问题达成解决方案(顺便说一句,它与 fib(n)

有趣的问题,我不能给你一个公式,但我写了一个Ruby程序来做,它能处理我在纸上算出的数字,而且对任何人都适用。

#!/usr/bin/ruby
#find out how many times fib() would need to be called

def howmany(n)
    a = [ ]
    a.push n-1
    a.push n-2
    while a.select{|n| n > 2}.length > 0
        a.map! do |n|
            n > 2 ? [n-1,n-2] : n
        end
        a.flatten!
    end
    a.length
end

>> howmany(10)
=> 55

太慢了。。我现在正在计算35,完成后我会编辑。

编辑:

>> howmany(35)
=> 9227465